The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices

D. S. Malyshev

Sibirskie èlektronnye matematičeskie izvestiâ, Tome 11 (2014), pp. 811-822.

Résumé

We obtain a complete complexity dichotomy for the edge 3-colorability within the family of hereditary classes defined by forbidden induced subgraphs on at most 6 vertices and having at most two 6-vertex forbidden induced structures.

Détail

Keywords: computational complexity, edge 3-colorability, hereditary class
Mots-clés : efficient algorithm.

Bibliographie

[1] V. Alekseev, “On easy and hard hereditary classes of graphs with respect to the independent set problem”, Discrete Applied Mathematics, 132:1–3 (2003), 17–26 | DOI | MR | Zbl

[2] V. Alekseev, R. Boliac, D. Korobitsyn, V. Lozin, “NP-hard graph problems and boundary classes of graphs”, Theoretical Computer Science, 389:1–2 (2007), 219–236 | DOI | MR | Zbl

[3] V. Alekseev, D. Korobitsyn, V. Lozin, “Boundary classes of graphs for the dominating set problem”, Discrete Mathematics, 285:1–3 (2004), 1–6 | DOI | MR | Zbl

[4] V. Alekseev, D. Malyshev, “A criterion for a class of graphs to be a boundary class and applications”, Diskretnyi Analiz i Issledovanie Operatsii, 15:6 (2008), 3–10 (in Russian) | MR

[5] S. Arnborg, A. Proskurowski, “Linear time algorithms for NP-hard problems restricted to partial $k$-trees”, Discrete Applied Mathematics, 23:1 (1989), 11–24 | DOI | MR | Zbl

[6] H. Bodlaender, “Dynamic programming on graphs with bounded treewidth”, Lecture Notes in Computer Science, 317, 1988, 105–118 | DOI | MR | Zbl

[7] H. Bodlaender, A. Koster, “Combinatorial optimization on graphs of bounded treewidth”, J. Comput., 51:3 (2008), 255–269 | DOI | MR

[8] H. Broersma, F. Fomin, P. Golovach, D. Paulusma, “Three complexity results on coloring $P_k$-free graphs”, European Journal of Combinatorics, 34:3 (2013), 609–619 | DOI | MR | Zbl

[9] H. Broersma, P. Golovach, D. Paulusma, J. Song, “Updating the complexity status of coloring graphs without a fixed induced linear forest”, Theoretical Computer Science, 414:1 (2012), 9–19 | DOI | MR | Zbl

[10] M. Garey, D. Johnson, Computers and intractability: a guide to the theory of NP-completeness, Freeman, 1979 | MR | Zbl

[11] P. Golovach, D. Paulusma, J. Song, “$4$-coloring $H$-free graphs when $H$ is small”, Discrete Applied Mathematics, 161:1–2 (2013), 140–150 | DOI | MR | Zbl

[12] R. Halin, “$S$-functions for graphs”, Journal of Geometry, 8:1–2 (2004), 171–186 | MR

[13] C. Hoang, M. Kaminski, V. Lozin, J. Sawada, X. Shu, “Deciding $k$-colorability of $P_5$-free graphs in polynomial time”, Algorithmica, 57:1 (2010), 74–81 | DOI | MR | Zbl

[14] I. Holyer, “The NP-completeness of edge-coloring”, SIAM Journal on Computing, 10:4 (1981), 718–720 | DOI | MR | Zbl

[15] S. Huang, “Improved complexity results on $k$-coloring $P_t$-free graphs”, Lecture Notes in Computer Science, 8087, 2013, 551–558 | DOI | MR | Zbl

[16] N. Korpeilainen, V. Lozin, D. Malyshev, A. Tiskin, “Boundary properties of graphs for algorithmic graph problems”, Theoretical Computer Science, 412:29 (2011), 3544–3554 | MR

[17] D. Kral', J. Kratochvil, Z. Tuza, G. Woeginger, “Complexity of coloring graphs without forbidden induced subgraphs”, Lecture Notes in Computer Science, 2204, 2001, 254–262 | DOI | MR | Zbl

[18] V. Le, B. Randerath, I. Schiermeyer, “On the complexity of $4$-coloring graphs without long induced paths”, Theoretical Computer Science, 389:1–2 (2007), 330–335 | MR | Zbl

[19] D. Leven, Z. Galil, “NP-completeness of finding the chromatic index of regular graphs”, Journal of Algorithms, 4:1 (1983), 35–44 | DOI | MR | Zbl

[20] V. Lozin, “Boundary classes of planar graphs”, Combinatorics, Probability and Computing, 17:2 (2008), 287–295 | DOI | MR | Zbl

[21] V. Lozin, M. Kaminski, “Coloring edges and vertices of graphs without short or long cycles”, Contributions to Discrete Mathematics, 2:1 (2007), 61–66 | MR | Zbl

[22] V. Lozin, D. Malyshev, “Vertex coloring of graphs with few obstructions”, Discrete Applied Mathematics (to appear)

[23] V. Lozin, C. Purcell, “Boundary properties of the satisfiability problems”, Information Processing Letters, 113:9 (2013), 313–317 | DOI | MR | Zbl

[24] V. Lozin, D. Rautenbach, “In the band-, tree- and clique-width of graphs with bounded vertex degree”, Discrete Mathematics, 18:1 (2004), 195–206 | MR | Zbl

[25] R. Machado, C. de Figueiredo, “Complexity separating classes for edge-colouring and total-colouring”, Journal of Brazilian Computer Society, 17:4 (2011), 281–285 | DOI | MR | Zbl

[26] R. Machado, C. de Figueiredo, N. Trotignon, “Chromatic index of graphs with no cycle with a unique chord”, Discrete Mathematics, 313:14 (2013), 1547–1552 | DOI | MR | Zbl

[27] R. Machado, C. de Figueiredo, K. Vuskovic, “Edge-colouring and total-colouring chordless graphs”, Theoretical Computer Science, 411:7–9 (2010), 1221–1234 | DOI | MR | Zbl

[28] Journal of Applied and Industrial Mathematics, 4:2 (2010), 213–217 | DOI | MR | Zbl

[29] D. Malyshev, “Boundary classes of graphs for some recognition problems”, Diskretnyi Analiz i Issledovanie Operatsii, 16:2 (2009), 85–94 (in Russian) | MR | Zbl

[30] D. Malyshev, “Continued sets of boundary classes of graphs for colorability problems”, Diskretnyi Analiz i Issledovanie Operatsii, 16:5 (2009), 41–51 (in Russian) | MR | Zbl

[31] Discrete Mathematics and Applications, 19:6 (2009), 625–630 | DOI | DOI | MR | Zbl

[32] Discrete Mathematics and Applications, 21:5–6 (2011), 645–649 | DOI | MR | Zbl

[33] Journal of Applied and Industrial Mathematics, 7:2 (2013), 221–228 | DOI | MR

[34] D. Malyshev, “Critical graph classes for the edge list-ranking problem”, Diskretnyi Analiz i Issledovanie Operatsii, 20:6 (2013), 59–76 (in Russian) | MR

[35] D. Malyshev, “Boundary graph classes for some maximum induced subgraph problems”, Journal of Combinatorial Optimization, 27:2 (2014), 345–354 | DOI | MR | Zbl

[36] D. Malyshev, The coloring problem for classes with two small obstructions, Working papers by Cornell University, 2013, arXiv: 1307.0278v1

[37] D. Malyshev, “The coloring problem for classes with two small obstructions”, Optimization Letters, 2014

[38] D. Malyshev, “Two cases of polynomial-time solvability for the coloring problem”, Journal of Combinatorial Optimization, 2014 | MR

[39] D. Malyshev, “The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs”, Discrete Mathematics (to appear)

[40] D. Malyshev, V. Alekseev, “Boundary classes for the list-ranking problems in subclasses of forests”, Diskretnyi Analiz i Issledovanie Operatsii, 18:6 (2011), 61–70 (in Russian) | MR | Zbl

[41] B. Randerath, I. Schiermeyer, “Vertex colouring and forbidden subgraphs — a survey”, Graphs and Combinatorics, 20:1 (2004), 1–40 | DOI | MR | Zbl

[42] N. Robertson, P. Seymour, “Graph minors. III: Planar tree-width”, Journal of Combinatorial Theory, Series B, 36:1 (1984), 49–64 | DOI | MR | Zbl

[43] N. Robertson, P. Seymour, “Graph minors. V: Excluding a planar graph”, Journal of Combinatorial Theory, Series B, 41:1 (1986), 92–114 | DOI | MR | Zbl

[44] A. Schrijver, Combinatorial optimization: polyhedra and efficiency, Springer, 2003

[45] J. Telle, A. Proskurowski, “Algorithms for vertex partitioning problems on partial $k$-trees”, SIAM Journal of Discrete Mathematics, 10:4 (1997), 529–550 | DOI | MR | Zbl

[46] Z. Tuza, “Graph colorings with local constraints — a survey”, Discussiones Mathematicae Graph Theory, 17:2 (1997), 161–228 | DOI | MR | Zbl

[47] V. Vizing, “On an estimate of the chromatic class of a $p$-graph”, Diskretnyi Analiz, 3 (1964), 25–30 (in Russian) | MR

[48] G. Woeginger, J. Sgall, “The complexity of coloring graphs without long induced paths”, Acta Cybernetica, 15:1 (2001), 107–117 | MR | Zbl