Complete complexity dichotomy for~7-edge~forbidden subgraphs in~the~edge~coloring~problem

D. S. Malyshev

Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 4, pp. 104-130.

Résumé

The edge coloring problem for a graph is to minimize the number of colors that are sufficient to color all edges of the graph so that all adjacent edges receive distinct colors. The computational complexity of the problem is known for all graph classes defined by forbidden subgraphs with at most 6 edges. We improve this result and obtain a complete complexity classification of the edge coloring problem for all sets of prohibitions each of which has at most 7 edges. Illustr. 3, bibliogr. 36.

Détail

Keywords: edge coloring problem, strongly hereditary class, computational complexity.

Bibliographie

[1] M. R. Garey, D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, Freeman, New York, 1979, 338 pp. | MR | Zbl

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

[3] V. G. Vizing, “On estimation of the chromatic index of a p-graph”, Descrete Analysis, 3, Inst. Mat. SO AN SSSR, Novosibirsk, 1964, 25–30

[4] D. Král', J. Kratochvíl, Z. Tuza, G. J. Woeginger, “Complexity of coloring graphs without forbidden induced subgraphs”, Proc. 27th Int. Workshop Graph-Theoretic Concepts Comput. Sci. (Boltenhagen, Germany, June 14–16, 2001), Lect. Notes Comput. Sci., 2204, Springer, Heidelberg, 2001, 254–262 | DOI | MR | Zbl

[5] V. V. Lozin, D. S. Malyshev, “Vertex coloring of graphs with few obstructions”, Discrete Appl. Math., 216 (2017), 273–280 | DOI | MR | Zbl

[6] C. T. Hoàng, D. Lazzarato, “Polynomial-time algorithms for minimum weighted colorings of $(P_5, \overline{P}_5)$-free graphs and similar graph classes”, Discrete Appl. Math., 186 (2015), 105–111 | DOI | MR

[7] T. Karthick, F. Maffray, L. Pastor, “Polynomial cases for the vertex coloring problem”, Algorithmica, 81:3 (2017), 1053–1074 | DOI | MR

[8] D. S. Malyshev, “The coloring problem for classes with two small obstructions”, Optim. Lett., 8:8 (2014), 2261–2270 | DOI | MR

[9] D. S. Malyshev, “Two cases of polynomial-time solvability for the coloring problem”, J. Comb. Optim., 31:2 (2016), 833–845 | DOI | MR | Zbl

[10] D. S. Malyshev, “The weighted coloring problem for two graph classes characterized by small forbidden induced structures”, Discrete Appl. Math., 47 (2018), 423–432 | DOI | MR

[11] D. S. Malyshev, O. O. Lobanova, “Two complexity results for the vertex coloring problem”, Discrete Appl. Math., 219 (2017), 158–166 | DOI | MR | Zbl

[12] D. S. Malyshev, “Polynomial-time approximation algorithms for the coloring problem in some cases”, J. Comb. Optim., 33 (2017), 809–813 | DOI | MR | Zbl

[13] K. Cameron, S. Huang, I. Penev, V. Sivaraman, “The class of $(P_7, C_4, C_5)$-free graphs: Decomposition, algorithms, and $\chi$-boundedness”, J. Graph Theory, 93:4 (2020), 503–552 | DOI | MR | Zbl

[14] K. Cameron, M. da Silva, S. Huang, K. Vuskovic, “Structure, algorithms for (cap, even hole)-free graphs”, Discrete Math., 341 (2018), 463–473 | DOI | MR | Zbl

[15] Y. Dai, A. Foley, C. T. Hoàng, “On coloring a class of claw-free graphs: To the memory of Frédéric Maffray”, Electron. Notes Theor. Comput. Sci., 346 (2019), 369–377 | DOI

[16] D. J. Fraser, A. M. Hamela, C. T. Hoñg, K. Holmes, T. P. LaMantia, “Characterizations of $(4K_1, C_4, C_5)$-free graphs”, Discrete Appl. Math., 231 (2017), 166–174 | DOI | MR | Zbl

[17] P. Golovach, M. Johnson, D. Paulusma, J. Song, “A survey on the computational complexity of coloring graphs with forbidden subgraphs”, J. Graph Theory, 84 (2017), 331–363 | DOI | MR | Zbl

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

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

[20] F. Bonomo, M. Chudnovsky, P. Maceli, O. Schaudt, M. Stein, M. Zhong, “Three-coloring and list three-coloring of graphs without induced paths on seven vertices”, Combinatorica, 38:4 (2018), 779–801 | DOI | MR | Zbl

[21] S. Spirkl, M. Chudnovsky, M. Zhong, “Four-coloring $P_6$-free graphs”, Proc. 30th Annu. ACM-SIAM Symp. Discrete Algorithms (San Diego, USA, Jan. 6–9, 2019), SIAM, Philadelphia, PA, 2019, 1239–1256 | DOI | MR | Zbl

[22] C. T. Hoàng, M. Kamiñski, V. 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

[23] S. Huang, “Improved complexity results on $k$-coloring $P_t$-free graphs”, Eur. J. Comb., 51 (2016), 336–346 | DOI | MR | Zbl

[24] D. S. Malyshev, “The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs”, Discrete Math., 338:11 (2015), 1860–1865 | DOI | MR | Zbl

[25] D. S. Malyshev, “The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs”, Graphs Comb., 33:4 (2017), 1009–1022 | DOI | MR | Zbl

[26] D. V. Sirotkin, D. S. Malyshev, “On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size”, J. Appl. Ind. Math., 12 (2018), 759–769 | DOI | MR | Zbl

[27] E. Galby, P. T. Lima, D. Paulusma, B. Ries, “Classifying $k$-edge colouring for $H$-free graphs”, Inf. Process. Lett., 146 (2019), 39–43 | DOI | MR | Zbl

[28] D. S. Malyshev, “The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices”, Sib. Elektron. Mat. Izv., 11 (2014), 811–822 | MR | Zbl

[29] D. S. Malyshev, “Complexity classification of the edge coloring problem for a family of graph classes”, Discrete Math. Appl., 27:2 (2017), 97–101 | DOI | MR

[30] A. Schrijver, Combinatorial optimization Polyhedra and efficiency, Springer, Heidelberg, 2003, 1882 pp. | MR | Zbl

[31] D. König, “Gráfoks alkalmazásuk a determinánsok és a halmazok elméletére”, Matematikai és Természettudományi Értesitö, 34 (1916), 104–119 (Hungarian) | Zbl

[32] B. Courcelle, J. Makowsky, U. Rotics, “Linear time solvable optimization problems on graphs of bounded clique-width”, Theory Comput. Syst., 33:2 (2000), 125–150 | DOI | MR | Zbl

[33] R. Boliac, V. V. Lozin, “On the clique-width of graphs in hereditary classes”, Algorithms and Computation, Proc. 13th Int. Symp. (Vancouver, Canada, Nov. 21–23, 2002), Lect. Notes Comput. Sci., 2518, Springer, Heidelberg, 2002, 44–54 | DOI | MR | Zbl

[34] F. Gurski, E. Wanke, “Line graphs of bounded clique-width”, Discrete Math., 307:22 (2007), 2734–2754 | DOI | MR | Zbl

[35] D. Kobler, D. Rotics, “Edge dominating set and colorings on graphs with fixed clique-width”, Discrete Appl. Math., 126:2-3 (2003), 197–223 | DOI | MR

[36] V. V. Lozin, M. Kamiñski, “Coloring edges and vertices of graphs without short or long cycles”, Contrib. Discrete Math., 2:1 (2007), 61–66 | MR | Zbl