Complexity separating classes for edge-colouring and total-colouring

Brazilian Computer Society. Journal

Raphael Machado¹  Celina Figueiredo² 

[1] Instituto Nacional de Metrologia, Qualidade e Tecnologia (Inmetro), COPPE—Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil

关键词: Theoretical computer science;    Computational complexity;    Colouring of graphs;    Total chromatic number;    Bipartite unichord-free;   

DOI  :  10.1007/s13173-011-0040-8

学科分类：农业科学（综合）

来源: Springer U K

【 摘 要 】

The class of unichord-free graphs was recently investigated in a series of papers (Machado et al. in Theor. Comput. Sci. 411:1221–1234, 2010; Machado, de Figueiredo in Discrete Appl. Math. 159:1851–1864, 2011; Trotignon, Vušković in J. Graph Theory 63:31–67, 2010) and proved to be useful with respect to the study of the complexity of colouring problems. In particular, several surprising complexity dichotomies could be found in subclasses of unichord-free graphs. We discuss such results based on the concept of “separating class” and we describe the class of bipartite unichord-free as a final missing separating class with respect to edge-colouring and total-colouring problems, by proving that total-colouring bipartite unichord-free graphs is NP-complete.

【 授权许可】

CC BY