Abstract
A colouring of a graph G = (V,E) is a mapping c: V → {1,2,…} such that c(u) ≠ c(v) if uv ∈ E; if |c(V)| ≤ k then c is a k-colouring. The Colouring problem is that of testing whether a given graph has a k-colouring for some given integer k. If a graph contains no induced subgraph isomorphic to any graph in some family \({\cal H}\), then it is called \({\cal H}\)-free. The complexity of Colouring for \({\cal H}\)-free graphs with \(|{\cal H}|=1\) has been completely classified. When \(|{\cal H}|=2\), the classification is still wide open, although many partial results are known. We continue this line of research and forbid induced subgraphs {H 1,H 2}, where we allow H 1 to have a single edge and H 2 to have a single non-edge. Instead of showing only polynomial-time solvability, we prove that Colouring on such graphs is fixed-parameter tractable when parameterized by |H 1| + |H 2|. As a byproduct, we obtain the same result both for the problem of determining a maximum independent set and for the problem of determining a maximum clique.
Research Supported by EPSRC (EP/G043434/1), ERC (267959) and ANR (TODO ANR-09-EMER-010).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Brandstädt, A., Engelfriet, J., Le, H.-O., Lozin, V.V.: Clique-Width for 4-Vertex Forbidden Subgraphs. Theory Comput. Syst. 39, 561–590 (2006)
Brandstädt, A., Kratsch, D.: On the structure of (P 5, gem)-free graphs. Discrete Applied Mathematics 145, 155–166 (2005)
Brandstädt, A., Le, H.-O., Mosca, R.: Gem- and co-gem-free graphs have bounded clique-width. Internat. J. Found. Comput. Sci. 15, 163–185 (2004)
Broersma, H.J., Golovach, P.A., Paulusma, D., Song, J.: Determining the chromatic number of triangle-free 2P 3-free graphs in polynomial time. Theoretical Computer Science 423, 1–10 (2012)
Broersma, H.J., Golovach, P.A., Paulusma, D., Song, J.: Updating the complexity status of coloring graphs without a fixed induced linear forest. Theoretical Computer Science 414, 9–19 (2012)
Couturier, J.F., Golovach, P.A., Kratsch, D., Paulusma, D.: List coloring in the absence of a linear forest. In: Kolman, P., Kratochvíl, J. (eds.) WG 2011. LNCS, vol. 6986, pp. 119–130. Springer, Heidelberg (2011)
Couturier, J.F., Golovach, P.A., Kratsch, D., Paulusma, D.: On the parameterized complexity of coloring graphs in the absence of linear forest. Journal of Discrete Algorithms 15, 56–62 (2012)
Dabrowski, K., Lozin, V., Müller, H., Rautenbach, D.: Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number. Journal of Discrete Algorithms 14, 207–213 (2012)
Dabrowski, K., Lozin, V., Raman, R., Ries, B.: Colouring vertices of triangle-free graphs without forests. Discrete Mathematics 312, 1372–1385 (2012)
Diestel, R.: Graph Theory, Electronic Edition. Springer (2005)
Golovach, P.A., Paulusma, D.: List coloring in the absence of two subgraphs. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 288–299. Springer, Heidelberg (2013)
Golovach, P.A., Paulusma, D., Song, J.: 4-Coloring H-free graphs when H is small. Discrete Applied Mathematics 161, 140–150 (2013)
Golovach, P.A., Paulusma, D., Song, J.: Closing complexity gaps for coloring problems on H-free graphs. In: Chao, K.-M., Hsu, T.-s., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 14–23. Springer, Heidelberg (2012)
Gravier, S., Hoáng, C.T., Maffray, F.: Coloring the hypergraph of maximal cliques of a graph with no long path. Discrete Mathematics 272, 285–290 (2003)
Gyárfás, A.: Problems from the world surrounding perfect graphs. Zastosowania Matematyki Applicationes Mathematicae XIX(3-4), 413–441 (1987)
Hoàng, C.T., Kamiński, M., Lozin, V., Sawada, J., Shu, X.: Deciding k-colorability of P 5-free graphs in polynomial time. Algorithmica 57, 74–81 (2010)
Hoàng, C.T., Maffray, F., Mechebbek, M.: A characterization of b-perfect graphs. Journal of Graph Theory 71, 95–122 (2012)
Král’, D., Kratochvíl, J., Tuza, Z., Woeginger, G.J.: Complexity of coloring graphs without forbidden induced subgraphs. In: Brandstädt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 254–262. Springer, Heidelberg (2001)
Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed clique-width. Discrete Applied Mathematics 126, 197–221 (2003)
Maffray, F., Preissmann, M.: On the NP-completeness of the k-colorability problem for triangle-free graphs. Discrete Mathematics 162, 313–317 (1996)
Randerath, B.: 3-colorability and forbidden subgraphs. I., Characterizing pairs. Discrete Mathematics 276, 313–325 (2004)
Randerath, B., Schiermeyer, I.: A note on Brooks’ theorem for triangle-free graphs, Australas. J. Combin. 26, 3–9 (2002)
Randerath, B., Schiermeyer, I.: Vertex colouring and forbidden subgraphs - a survey. Graphs and Combinatorics 20, 1–40 (2004)
Randerath, B., Schiermeyer, I.: On maximum independent sets in P 5-free graphs. Discrete Applied Mathematics 158(9), 1041–1044 (2010)
Schindl, D.: Some new hereditary classes where graph coloring remains NP-hard. Discrete Mathematics 295, 197–202 (2005)
Tuza, Z.: Graph colorings with local restrictions - a survey, Discuss. Math. Graph Theory 17, 161–228 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dabrowski, K.K., Golovach, P.A., Paulusma, D. (2013). Colouring of Graphs with Ramsey-Type Forbidden Subgraphs. In: Brandstädt, A., Jansen, K., Reischuk, R. (eds) Graph-Theoretic Concepts in Computer Science. WG 2013. Lecture Notes in Computer Science, vol 8165. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45043-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-45043-3_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45042-6
Online ISBN: 978-3-642-45043-3
eBook Packages: Computer ScienceComputer Science (R0)