Brazilian Computer Society. Journal | |
Complexity separating classes for edge-colouring and total-colouring | |
Raphael Machado1  Celina Figueiredo2  | |
[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
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO201902193515307ZK.pdf | 493KB | download |