کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419863 | 683868 | 2011 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Total chromatic number of unichord-free graphs Total chromatic number of unichord-free graphs](/preview/png/419863.png)
A unichord is an edge that is the unique chord of a cycle in a graph. The class CC 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 CC and in the subclass C′C′ obtained from CC by forbidding squares. In the present work, we prove that the total-colouring problem is NP-complete when restricted to graphs in CC. For the subclass C′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.
Journal: Discrete Applied Mathematics - Volume 159, Issue 16, 28 September 2011, Pages 1851–1864