Geodesic
Study of boundary graph classes for colorability problems
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 6, pp. 37-48.

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

The notion of a boundary graph class is a helpfull tool for computational complexity analysis of graph theory problems in the family of hereditary graph classes. Some general and specific features for families of boundary graph classes for the vertex-$k$-colorability problem and its “limited” variant, the chromatic number problem were investigated in previous papers of the author. In this paper, the similar research is conducted for the edge-$k$-colorability and the chromatic index problems. Every boundary class for the edge-$3$-colorability problem is a boundary class for the chromatic index problem. Surprisingly, for any $k>3$ there exist uncountably many boundary classes for the edge-$k$-colorability problem such that each of them is not boundary for the chromatic index problem. Finally, we formulate a necessary condition for existence of boundary graph classes for the vertex-$3$-colorability problem which are not boundary for the chromatic number problem. To the author's mind, the resolution of the condition cannot be true and, hence, there are no such boundary classes for the vertex-$3$-colorability problem. Bibliogr. 11.
Keywords: computational complexity, boundary graph class, colorability problem. 
@article{DA_2012_19_6_a3,
     author = {D. S. Malyshev},
     title = {Study of boundary graph classes for colorability problems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {37--48},
     publisher = {mathdoc},
     volume = {19},
     number = {6},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_6_a3/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - Study of boundary graph classes for colorability problems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 37
EP  - 48
VL  - 19
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_6_a3/
LA  - ru
ID  - DA_2012_19_6_a3
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T Study of boundary graph classes for colorability problems
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 37-48
%V 19
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_6_a3/
%G ru
%F DA_2012_19_6_a3
D. S. Malyshev. Study of boundary graph classes for colorability problems. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 6, pp. 37-48. http://geodesic.mathdoc.fr/item/DA_2012_19_6_a3/

[1] Vizing V. G., “Ob otsenke khromaticheskogo klassa $p$-grafa”, Diskret. analiz, 3, 1964, 25–30 | MR

[2] Malyshev D. S., “Kontinualnye mnozhestva granichnykh klassov grafov dlya zadach o raskraske”, Diskret. analiz i issled. operatsii, 16:5 (2009), 41–51 | MR | Zbl

[3] Malyshev D. S., “O peresechenii i simmetricheskoi raznosti semeistv granichnykh klassov dlya zadach o raskraske i o khromaticheskom chisle”, Diskret. matematika, 24:2 (2012), 75–78

[4] Alekseev V. E., “On easy and hard hereditary classes of graphs with respect to the independent set problem”, Discrete Appl. Math., 132 (2004), 17–26 | DOI | MR

[5] Alekseev V. E., Boliac R., Korobitsyn D. V., Lozin V. V., “NP-hard graph problems and boundary classes of graphs”, Theor. Comput. Sci., 389 (2007), 219–236 | DOI | MR | Zbl

[6] Bodlaender H. L., “Dynamic programming on graphs with bounded treewidth”, Automata, languages, and programming (Tampere, 1988), Proc., Lect. Notes Comput. Sci., 317, Springer-Verl., Berlin, 1988, 105–118 | DOI | MR

[7] Korpeilainen N., Lozin V. V., Malyshev D. S., Tiskin A., “Boundary properties of graphs for algorithmic graph problems”, Theor. Comput. Sci., 412 (2011), 3545–3554 | DOI | MR

[8] Lozin V. V., Rautenbach D., “On the band-, tree- and clique-width of graphs with bounded vertex degree”, Discrete Math., 18 (2004), 195–206 | MR | Zbl

[9] Machado R., de Figueiredo C. M. H., “Complexity separating classes for edge-colouring and total-colouring”, J. Braz. Comput. Soc., 17 (2011), 281–285 | DOI | MR

[10] Machado R., de Figueiredo C. M. H., Vuskovic K., “Chromatic index of graphs with no cycle with a unique chord”, Theor. Comput. Sci., 411 (2010), 1221–1234 | DOI | MR | Zbl

[11] Schrijver A., Combinatorial optimization – polyhedra and efficiency, Springer-Verl., Berlin, 2003, 1882 pp. | Zbl