کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4652789 | 1632595 | 2010 | 8 صفحه PDF | دانلود رایگان |
We determine a surprising class for which edge-colouring is NP-complete but whose graphs are all Type 1. The class of unichord-free graphs was recently studied by Trotignon and Vušković [N. Trotignon and K. Vušković. A structure theorem for graphs with no cycle with a unique chord and its consequences. To appear in J. Graph Theory. (Available online at http://www.comp.leeds.ac.uk/vuskovi/chord.ps.)] in the context of vertex-colouring. Machado, Figueiredo and Vušković [R. C. S. Machado, C. M. H. de Figueiredo, and K. Vušković. Chromatic index of graphs with no cycle with unique chord. In: Proc. of the ALIO/EUROWorkshop on Applied Optimization (2008). Full paper submitted to Theoret. Comput. Sci.] established the NP-completeness of edge-colouring unichord-free graphs. For the subclass of {square,unichord}-free graphs, an interesting complexity dicothomy holds [R. C. S. Machado, C. M. H. de Figueiredo, and K. Vušković. Chromatic index of graphs with no cycle with unique chord. In: Proc. of the ALIO/EUROWorkshop on Applied Optimization (2008). Full paper submitted to Theoret. Comput. Sci.]: if the maximum degree is 3, the edge-colouring is NP-complete, otherwise, the problem is polynomial. Subsequently, Machado and Figueiredo [R. C. S. Machado and C. M. H. de Figueiredo. Total chromatic number of chordless graphs. In: Proc. of the Cologne-Twente Workshop (2009). Full paper submitted to Discrete Appl. Math.] settled the validity of the Total-Colouring Conjecture for {square,unichord}-free graphs by proving that non-complete {square,unichord}-free graphs of maximum degree at least 4 are Type 1. In the present work, we prove that non-complete {square,unichord}-free graphs of maximum degree 3 are Type 1, establishing the polynomiality of total-colouring restricted to {square,unichord}-free graphs.
Journal: Electronic Notes in Discrete Mathematics - Volume 36, 1 August 2010, Pages 671-678