Abstract
A list assignment of a graph G = (V,E) is a function \({\cal L}\) that assigns a list L(u) of so-called admissible colors to each u ∈ V. The List Coloring problem is that of testing whether a given graph G = (V,E) has a coloring c that respects a given list assignment \({\cal L}\), i.e., whether G has a mapping c: V → {1,2,…} such that (i) c(u) ≠ c(v) whenever uv ∈ E and (ii) c(u) ∈ L(u) for all u ∈ V. If a graph G has no induced subgraph isomorphic to some graph of a pair {H 1,H 2}, then G is called (H 1,H 2)-free. We completely characterize the complexity of List Coloring for (H 1,H 2)-free graphs.
This paper was supported by EPSRC (EP/G043434/1) and ERC (267959).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bienstock, D., Robertson, N., Seymour, P.D., Thomas, R.: Quickly excluding a forest. J. Comb. Theory, Ser. B 52, 274–283 (1991)
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)
Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23, 864–894 (1994)
Dabrowski, K., Lozin, V., Raman, R., Ries, B.: Colouring vertices of triangle-free graphs without forests. Discrete Mathematics 312, 1372–1385 (2012)
Golovach, P.A., Heggernes, P.: Choosability of P 5-free graphs. In: Královič, R., Niwiński, D. (eds.) MFCS 2009. LNCS, vol. 5734, pp. 382–391. Springer, Heidelberg (2009)
Golovach, P.A., Paulusma, D., Ries, B.: Coloring Graphs Characterized by a Forbidden Subgraph. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 443–454. Springer, Heidelberg (2012)
Golovach, P.A., Paulusma, D., Song, J.: Coloring graphs without short cycles and long induced paths. In: Owe, O., Steffen, M., Telle, J.A. (eds.) FCT 2011. LNCS, vol. 6914, pp. 193–204. Springer, Heidelberg (2011)
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)
Golovach, P.A., Paulusma, D., Song, J.: 4-Coloring H-free graphs when H is small. Discrete Applied Mathematics 161, 140–150 (2013)
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., Maffray, F., Mechebbek, M.: A characterization of b-perfect graphs. Journal of Graph Theory 71, 95–122 (2012)
Jansen, K.: Complexity Results for the Optimum Cost Chromatic Partition Problem, Universität Trier, Mathematik/Informatik, Forschungsbericht 96–41 (1996)
Jansen, K., Scheffler, P.: Generalized coloring for tree-like graphs. Discrete Appl. Math. 75, 135–155 (1997)
Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed clique-width. Discrete Applied Mathematics 126, 197–221 (2003)
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, p. 254. Springer, Heidelberg (2001)
Kratochvíl, J., Tsuza, Z.: Algorithmic complexity of list colorings. Discrete Applied Mathematics 50, 297–302 (1994)
Kratsch, S., Schweitzer, P.: Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG 2012. LNCS, vol. 7551, pp. 34–45. Springer, Heidelberg (2012)
Lozin, V.V.: A decidability result for the dominating set problem. Theoretical Computer Science 411, 4023–4027 (2010)
Maffray, F., Preissmann, M.: On the NP-completeness of the k-colorability problem for triangle-free graphs. Discrete Mathematics 162, 313–317 (1996)
Mertzios, G.B., Spirakis, P.G.: Algorithms and almost tight results for 3-colorability of small diameter graphs. In: van Emde Boas, P., Groen, F.C.A., Italiano, G.F., Nawrocki, J., Sack, H. (eds.) SOFSEM 2013. LNCS, vol. 7741, pp. 332–343. Springer, Heidelberg (2013)
Jensen, T.R., Toft, B.: Graph Coloring Problems. Wiley Interscience (1995)
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 Combin. 20, 1–40 (2004)
Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. STOC 1978, pp. 216–226 (1978)
Schindl, D.: Some new hereditary classes where graph coloring remains NP-hard. Discrete Math. 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
Golovach, P.A., Paulusma, D. (2013). List Coloring in the Absence of Two Subgraphs. In: Spirakis, P.G., Serna, M. (eds) Algorithms and Complexity. CIAC 2013. Lecture Notes in Computer Science, vol 7878. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38233-8_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-38233-8_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38232-1
Online ISBN: 978-3-642-38233-8
eBook Packages: Computer ScienceComputer Science (R0)