Geodesic
A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 22 (2020) no. 1, pp. 38-47.

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

The vertex 3-colourability problem for a given graph is to check whether it is possible to split the set of its vertices into three subsets of pairwise non-adjacent vertices or not. A hereditary class of graphs is a set of simple graphs closed under isomorphism and deletion of vertices; the set of its forbidden induced subgraphs defines every such a class. For all but three the quadruples of 5-vertex forbidden induced subgraphs, we know the complexity status of the vertex 3-colourability problem. Additionally, two of these three cases are polynomially equivalent; they also polynomially reduce to the third one. In this paper, we prove that the computational complexity of the considered problem in all of the three mentioned classes is polynomial. This result contributes to the algorithmic graph theory.
Keywords: vertex 3-colourability problem, hereditary graph class
Mots-clés : polynomial-time algorithm. 
@article{SVMO_2020_22_1_a2,
     author = {D. S. Malyshev},
     title = {A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions},
     journal = {\v{Z}urnal Srednevol\v{z}skogo matemati\v{c}eskogo ob\^{s}estva},
     pages = {38--47},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVMO_2020_22_1_a2/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
JO  - Žurnal Srednevolžskogo matematičeskogo obŝestva
PY  - 2020
SP  - 38
EP  - 47
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SVMO_2020_22_1_a2/
LA  - ru
ID  - SVMO_2020_22_1_a2
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
%J Žurnal Srednevolžskogo matematičeskogo obŝestva
%D 2020
%P 38-47
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SVMO_2020_22_1_a2/
%G ru
%F SVMO_2020_22_1_a2
D. S. Malyshev. A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions. Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 22 (2020) no. 1, pp. 38-47. http://geodesic.mathdoc.fr/item/SVMO_2020_22_1_a2/

[1] M. R. Garey, D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness, W. H. Freeman and Co. New York, NY, USA, 1979, 338 pp. (In English) | MR | Zbl

[2] H. J. Broersma, P. A. 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 (In English) | DOI | MR | Zbl

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

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

[5] 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 (In English) | DOI | MR | Zbl

[6] S. Spirkl, M. Chudnovsky, M. Zhong, “Four-coloring $P_6$-free graphs”, Simposium on Discrete Algorithims, 2019, 1239–1256 (In English) | MR | Zbl

[7] S. Huang, “Improved complexity results on $k$-coloring $P_t$-free graphs”, European Journal of Combinatorics, 51:1 (2016), 336–346 (In English) | DOI | MR | Zbl

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

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

[10] 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”, Journal of Applied and Industrial Mathematics, 25:4 (2018), 759–769 (In English) | DOI | MR | Zbl

[11] R. L. Brooks, “On colouring the nodes of a network”, Proceedings of Cambridge Philosophical Society, Mathematical and physical sciences., 37:2 (1941), 194–197 (In English) | DOI | MR