A complete complexity dichotomy of~the~edge-coloring problem for~all~sets~of~8-edge forbidden subgraphs

D. S. Malyshev ; O. I. Duginov

Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 4, pp. 91-109.

Résumé

For a given graph, the edge-coloring problem is to minimize the number of colors sufficient to color all the graph edges so that any adjacent edges receive different colors. For all classes defined by sets of forbidden subgraphs, each with 7 edges, the complexity status of this problem is known. In this paper, we obtain a similar result for all sets of 8-edge prohibitions. Illustr. 2, bibliogr. 38.

Détail

Keywords: edge-coloring problem, computational complexity
Mots-clés : monotone class.

Bibliographie

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

[2] V. G. Vizing, “On an estimate of the chromatic index of a $p$-graph”, Discrete Analysis, 3, Inst. Mat. SO AN SSSR, Novosibirsk, 1964, 25–30 (Russian)

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

[4] 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

[5] 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 | DOI | MR | Zbl

[6] D. S. Malyshev, “Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem”, J. Appl. Ind. Math., 14:4 (2020), 706–721 | DOI | MR | Zbl

[7] D. S. Malyshev, O. I. Duginov, “Some cases of polynomial solvability for the edge colorability problem generated by forbidden $8$-edge subcubic forests”, J. Appl. Ind. Math., 16:2 (2022), 276–291 | DOI | MR | MR | Zbl

[8] Barnaby M., Paulusma D., Siani S., “Colouring graphs of bounded diameter in the absence of small cycles”, Discrete Appl. Math., 314:15 (2022), 150–161 | MR | Zbl

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

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

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

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

[13] Dai Y., Foley A., Hoàng C., “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 | MR

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

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

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

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

[18] Hoàng C., Lazzarato D., “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

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

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

[21] Klimošová T., Malík J., Masařík T., Novotná J., Paulusma D., Slívová V., “Colouring $(P_r+P_s)$-free graphs”, Algorithmica, 82:7 (2020), 1833–1858 | DOI | MR | Zbl

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

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

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

[25] Malyshev D. S., “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

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

[27] Malyshev D. S., “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

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

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

[30] Malyshev D. S., “The vertex colourability problem for \{claw, butterfly\}-free graphs is polynomial-time solvable”, Optim. Lett., 15:2 (2021), 311–326 | DOI | MR | Zbl

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

[32] Malyshev D. S., Pristavchenko O. V., “An intractability result for the vertex 3-colourability problem”, Optim. Lett., 16 (2022), 1403–1409 | DOI | MR | Zbl

[33] Malyshev D. S., Razvenskaya O. O., Pardalos P. M., “The computational complexity of weighted vertex coloring for $\{P_5,K_{2,3},K_{2,3}^+\}$-free graphs”, Optim. Lett., 15:1 (2021), 137–152 | DOI | MR | Zbl

[34] O. O. Razvenskaya, D. S. Malyshev, “Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes”, J. Appl. Ind. Math., 15:1 (2021), 97–117 | DOI | MR | MR | Zbl

[35] 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:4 (2018), 759–769 | DOI | MR | Zbl

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

[37] Schrijver A., Combinatorial optimization: Polyhedra and efficiency, Algorithms Comb., 24, Springer, Heidelberg, 2003, 1882 pp. | MR | Zbl

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