Geodesic
On the complexity of the vertex $3$-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 4, pp. 112-130.

Voir la notice de l'article provenant de la source Math-Net.Ru

The $3$-coloring problem for a given graph consists in verifying whether it is possible to divide the vertex set of the graph into three subsets of pairwise nonadjacent vertices. A complete complexity classification is known for this problem for the hereditary classes defined by triples of forbidden induced subgraphs, each on at most $5$ vertices. In this article, the quadruples of forbidden induced subgraphs is under consideration, each on at most $5$ vertices. For all but three corresponding hereditary classes, the computational status of the $3$-coloring problem is determined. Considering two of the remaining three classes, we prove their polynomial equivalence and polynomial reducibility to the third class. Illustr. 4, bibliogr. 20.
Keywords: $3$-colorability problem, hereditary class, computational complexity. 
@article{DA_2018_25_4_a7,
     author = {D. V. Sirotkin and D. S. Malyshev},
     title = {On the complexity of the vertex $3$-coloring problem for the hereditary graph classes with forbidden subgraphs of small size},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {112--130},
     publisher = {mathdoc},
     volume = {25},
     number = {4},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2018_25_4_a7/}
}
TY  - JOUR
AU  - D. V. Sirotkin
AU  - D. S. Malyshev
TI  - On the complexity of the vertex $3$-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2018
SP  - 112
EP  - 130
VL  - 25
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2018_25_4_a7/
LA  - ru
ID  - DA_2018_25_4_a7
ER  - 
%0 Journal Article
%A D. V. Sirotkin
%A D. S. Malyshev
%T On the complexity of the vertex $3$-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
%J Diskretnyj analiz i issledovanie operacij
%D 2018
%P 112-130
%V 25
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2018_25_4_a7/
%G ru
%F DA_2018_25_4_a7
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. Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 4, pp. 112-130. http://geodesic.mathdoc.fr/item/DA_2018_25_4_a7/

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

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

[3] Brooks R. L., “On colouring the nodes of a network”, Proc. Camb. Philos. Soc., Math. Phys. Sci., 37:2 (1941), 194–197 | DOI | MR | Zbl

[4] Dabrowski K., Golovach P. A., Paulusma D., “Colouring of graphs with Ramsey-type forbidden subgraphs”, Theor. Comput. Sci., 522 (2014), 34–43 | DOI | MR | Zbl

[5] Dabrowski K., Lozin V. V., Raman R., Ries B., “Colouring vertices of triangle-free graphs without forests”, Discrete Math., 312:7 (2012), 1372–1385 | DOI | MR | Zbl

[6] Dailey D. P., “Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete”, Discrete Math., 30:3 (1980), 289–293 | DOI | MR | Zbl

[7] Golovach P. A., Paulusma D., Ries B., “Coloring graphs characterized by a forbidden subgraph”, Discrete Appl. Math., 180 (2015), 101–110 | DOI | MR | Zbl

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

[9] 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 (2010), 74–81 | DOI | MR | Zbl

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

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

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

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

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

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

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

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

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

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

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