Forbidden Structures for Planar Perfect Consecutively Colourable Graphs

Marta Borowiecka-Olszewska, and Ewa Drgas-Burchardt. "Forbidden Structures for Planar Perfect Consecutively Colourable Graphs." Discussiones Mathematicae Graph Theory 37.2 (2017): 315-336. <http://eudml.org/doc/288073>.

@article{MartaBorowiecka2017,
abstract = {A consecutive colouring of a graph is a proper edge colouring with posi- tive integers in which the colours of edges incident with each vertex form an interval of integers. The idea of this colouring was introduced in 1987 by Asratian and Kamalian under the name of interval colouring. Sevast- janov showed that the corresponding decision problem is NP-complete even restricted to the class of bipartite graphs. We focus our attention on the class of consecutively colourable graphs whose all induced subgraphs are consecutively colourable, too. We call elements of this class perfect consecutively colourable to emphasise the conceptual similarity to perfect graphs. Obviously, the class of perfect consecutively colourable graphs is induced hereditary, so it can be characterized by the family of induced forbidden graphs. In this work we give a necessary and sufficient conditions that must be satisfied by the generalized Sevastjanov rosette to be an induced forbid- den graph for the class of perfect consecutively colourable graphs. Along the way, we show the exact values of the deficiency of all generalized Sevastjanov rosettes, which improves the earlier known estimating result. It should be mentioned that the deficiency of a graph measures its closeness to the class of consecutively colourable graphs. We motivate the investigation of graphs considered here by showing their connection to the class of planar perfect consecutively colourable graphs.},
author = {Marta Borowiecka-Olszewska, Ewa Drgas-Burchardt},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {edge colouring; consecutive (interval) colouring; deficiency; Sevastjanov graph; forbidden graph; sevastjanov graph},
language = {eng},
number = {2},
pages = {315-336},
title = {Forbidden Structures for Planar Perfect Consecutively Colourable Graphs},
url = {http://eudml.org/doc/288073},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Marta Borowiecka-Olszewska
AU - Ewa Drgas-Burchardt
TI - Forbidden Structures for Planar Perfect Consecutively Colourable Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 2
SP - 315
EP - 336
AB - A consecutive colouring of a graph is a proper edge colouring with posi- tive integers in which the colours of edges incident with each vertex form an interval of integers. The idea of this colouring was introduced in 1987 by Asratian and Kamalian under the name of interval colouring. Sevast- janov showed that the corresponding decision problem is NP-complete even restricted to the class of bipartite graphs. We focus our attention on the class of consecutively colourable graphs whose all induced subgraphs are consecutively colourable, too. We call elements of this class perfect consecutively colourable to emphasise the conceptual similarity to perfect graphs. Obviously, the class of perfect consecutively colourable graphs is induced hereditary, so it can be characterized by the family of induced forbidden graphs. In this work we give a necessary and sufficient conditions that must be satisfied by the generalized Sevastjanov rosette to be an induced forbid- den graph for the class of perfect consecutively colourable graphs. Along the way, we show the exact values of the deficiency of all generalized Sevastjanov rosettes, which improves the earlier known estimating result. It should be mentioned that the deficiency of a graph measures its closeness to the class of consecutively colourable graphs. We motivate the investigation of graphs considered here by showing their connection to the class of planar perfect consecutively colourable graphs.
LA - eng
KW - edge colouring; consecutive (interval) colouring; deficiency; Sevastjanov graph; forbidden graph; sevastjanov graph
UR - http://eudml.org/doc/288073
ER -