Forbidden Structures for Planar Perfect Consecutively Colourable Graphs
| Autor: | Marta Borowiecka-Olszewska, Ewa Drgas-Burchardt |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Vertex (graph theory)
consecutive (interval) colouring forbidden graph Applied Mathematics 020206 networking & telecommunications Natural number 0102 computer and information sciences 02 engineering and technology Astrophysics::Cosmology and Extragalactic Astrophysics deficiency Decision problem 01 natural sciences Graph Combinatorics edge colouring Planar 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Bipartite graph QA1-939 Discrete Mathematics and Combinatorics sevastjanov graph Astrophysics::Galaxy Astrophysics Mathematics |
| Zdroj: | Discussiones Mathematicae Graph Theory, Vol 37, Iss 2, Pp 315-336 (2017) |
| ISSN: | 2083-5892 |
| Popis: | A consecutive colouring of a graph is a proper edge colouring with natural numbers 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 [1] for bipartite graphs and developed for all graphs by Giaro and Kubale. Sevastjanov 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 Rosette of Sevastjanov to be a forbidden graph for the class of perfect consecutively colourable graphs. Along the way, we show the exact values of the deficiency of all Rosettes of Sevastjanov, 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. Finally, we motivate the investigation of graphs considered here by showing their connection to the class of planar perfect consecutively colourable graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|