Total chromatic number of unichord-free graphs |
| |
Authors: | RCS Machado CMH de Figueiredo |
| |
Institution: | a Instituto Nacional de Metrologia Normalização e Qualidade Industrial, Brazilb COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, RJ, Brazil |
| |
Abstract: | A unichord is an edge that is the unique chord of a cycle in a graph. The class C of unichord-free graphs — that is, graphs that do not contain, as an induced subgraph, a cycle with a unique chord — was recently studied by Trotignon and Vuškovi? (2010) 24], who proved strong structure results for these graphs and used these results to solve the recognition and vertex-colouring problems. Machado et al. (2010) 18] determined the complexity of the edge-colouring problem in the class C and in the subclass C′ obtained from C by forbidding squares. In the present work, we prove that the total-colouring problem is NP-complete when restricted to graphs in C. For the subclass C′, we establish the validity of the Total Colouring Conjecture by proving that every non-complete {square, unichord}-free graph of maximum degree at least 4 is Type 1. |
| |
Keywords: | Cycle with a unique chord Decomposition Recognition Petersen graph Heawood graph Edge-colouring Total-colouring |
本文献已被 ScienceDirect 等数据库收录! |
|