About Journal 
Editorial Board
Publishing Ethics
Author Guide 
Submission
Prepare Your Manuscript
Peer review
Archive
Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2020, 14:4, 706-721
Volume 27, No 4, 2020, P. 104-130
UDC 519.17
D. S. Malyshev
Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
Abstract:
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.
Keywords: edge coloring problem, strongly hereditary class, computational complexity.
DOI: 10.33048/daio.2020.27.682
Dmitry S. Malyshev 1
1. National Research University “Higher School of Economics”,
25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia
e-mail: dsmalyshev@rambler.ru
Received January 22, 2020
Revised June 1, 2020
Accepted June 11, 2020
References
[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979).[2] I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (4), 718–720 (1981).
[3] V. G. Vizing, On estimation of the chromatic index of a $p$-graph, in Descrete Analysis, Vol. 3 (Inst. Mat. SO AN SSSR, Novosibirsk, 1964), pp. 25–30.
[4] D. Král’, J. Kratochvíl, Z. Tuza, and G. J. Woeginger, Complexity of coloring graphs without forbidden induced subgraphs, in Proc. 27th Int. Workshop Graph-Theoretic Concepts Comput. Sci., Boltenhagen, Germany, June 14–16, 2001 (Springer, Heidelberg, 2001), pp. 254–262 (Lect. Notes Comput. Sci., Vol. 2204).
[5] V. V. Lozin and D. S. Malyshev, Vertex coloring of graphs with few obstructions, Discrete Appl. Math. 216, 273–280 (2017).
[6] C. T. Hoàng and 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, 105–111 (2015).
[7] T. Karthick, F. Maffray, and L. Pastor, Polynomial cases for the vertex coloring problem, Algorithmica 81 (3), 1053–1074 (2017).
[8] D. S. Malyshev, The coloring problem for classes with two small obstructions, Optim. Lett. 8 (8), 2261–2270 (2014).
[9] D. S. Malyshev, Two cases of polynomial-time solvability for the coloring problem, J. Comb. Optim. 31 (2), 833–845 (2016).
[10] D. S. Malyshev, The weighted coloring problem for two graph classes characterized by small forbidden induced structures, Discrete Appl. Math. 47, 423–432 (2018).
[11] D. S. Malyshev and O. O. Lobanova, Two complexity results for the vertex coloring problem, Discrete Appl. Math. 219, 158–166 (2017).
[12] D. S. Malyshev, Polynomial-time approximation algorithms for the coloring problem in some cases, J. Comb. Optim. 33, 809–813 (2017).
[13] K. Cameron, S. Huang, I. Penev, and V. Sivaraman, The class of ($P_7, C_4, C_5$)-free graphs: Decomposition, algorithms, and $\chi$-boundedness, J. Graph Theory 93 (4), 503–552 (2020).
[14] K. Cameron, M. da Silva, S. Huang, and K. Vuskovic, Structure and algorithms for (cap, even hole)-free graphs, Discrete Math. 341, 463–473 (2018).
[15] Y. Dai, A. Foley, and 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, 369–377 (2019).
[16] D. J. Fraser, A. M. Hamela, C. T. Hoàng, K. Holmes, and T. P. LaMantia, Characterizations of ($4K_1, C_4, C_5$)-free graphs, Discrete Appl. Math. 231, 166–174 (2017).
[17] P. Golovach, M. Johnson, D. Paulusma, and J. Song, A survey on the computational complexity of coloring graphs with forbidden subgraphs, J. Graph Theory 84, 331–363 (2017).
[18] H. J. Broersma, P. A. Golovach, D. Paulusma, and J. Song, Updating the complexity status of coloring graphs without a fixed induced linear forest, Theor. Comput. Sci. 414 (1), 9–19 (2012).
[19] P. A. Golovach, D. Paulusma, and J. Song, 4-coloring $H$-free graphs when $H$ is small, Discrete Appl. Math. 161 (1–2), 140–150 (2013).
[20] F. Bonomo, M. Chudnovsky, P. Maceli, O. Schaudt, M. Stein, and M. Zhong, Three-coloring and list three-coloring of graphs without induced paths on seven vertices, Combinatorica 38 (4), 779–801 (2018).
[21] S. Spirkl, M. Chudnovsky, and M. Zhong, Four-coloring $P_6$-free graphs, in Proc. 30th Annu. ACM-SIAM Symp. Discrete Algorithms, San Diego, USA, Jan. 6–9, 2019 (SIAM, Philadelphia, PA, 2019),
[22] C. T. Hoàng, M. Kaminski, V. V. Lozin, J. Sawada, and X. Shu, Deciding $k$-colorability of $P_5$-free graphs in polynomial time, Algorithmica 57 (1), 74–81 (2010).
[23] S. Huang Improved complexity results on $k$-coloring $P_t$-free graphs, Eur. J. Comb. 51, 336–346 (2016).
[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), 1860–1865 (2015).
[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), 1009–1022 (2017).
[26] D. V. Sirotkin and D. S. Malyshev, On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size, Diskretn. Anal. Issled. Oper. 25 (4), 112–130 (2018) [Russian] [J. Appl. Ind. Math. 12 (4), 759–769 (2018)].
[27] E. Galby, P. T. Lima, D. Paulusma, and B. Ries, Classifying k-edge colouring for H-free graphs, Inf. Process. Lett. 146, 39–43 (2019).
[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, 811–822 (2014).
[29] D. S. Malyshev, Complexity classification of the edge coloring problem for a family of graph classes, Discrete Math. Appl. 27 (2), 97–101 (2017).
[30] A. Schrijver, Combinatorial Optimization – Polyhedra and Efficiency (Springer, Heidelberg, 2003).
[31] D. König, Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére, Matematikai és Természettudományi Értesitö 34, 104–119 (1916) [Hungarian].
[32] B. Courcelle, J. Makowsky, and U. Rotics, Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst. 33 (2), 125–150 (2000).
[33] R. Boliac and 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) (Springer, Heidelberg, 2002), pp. 44–54 (Lect. Notes Comput. Sci., Vol. 2518).
[34] F. Gurski and E. Wanke, Line graphs of bounded clique-width, Discrete Math. 307 (22), 2734–2754 (2007).
[35] D. Kobler and D. Rotics, Edge dominating set and colorings on graphs with fixed clique-width, Discrete Appl. Math. 126 (2–3), 197–223 (2003).
[36] V. V. Lozin and M. Kaminski, Coloring edges and vertices of graphs without short or long cycles, Contrib. Discrete Math. 2 (1), 61–66 (2007).
