Complexity separating classes for edge-colouring and total-colouring

DOI10.1007/S13173-011-0040-8MaRDI QIDQ2391946zbMATHOpenAlexFDO

Authors R. C. S. Machado, Celina M. H. de Figueiredo

Publication date 6 August 2013

Published in Journal of the Brazilian Computer Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s13173-011-0040-8

zbMATH Keywords

computational complexitytotal chromatic numbertheoretical computer sciencecolouring of graphsbipartite unichord-free

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Complexity-separating graph classes for vertex, edge and total colouring
• Total chromatic number of \{square,unichord\}-free graphs
• Total chromatic number of unichord-free graphs
• Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs
• Clique-colouring and biclique-colouring unichord-free graphs

Cites work

• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Chromatic index of graphs with no cycle with a unique chord
• Edge-colouring and total-colouring chordless graphs
• List edge and list total colourings of multigraphs
• NP completeness of finding the chromatic index of regular graphs
• The NP-completeness column: an ongoing guide
• The total chromatic number of some bipartite graphs.
• Total chromatic number of \{square,unichord\}-free graphs
• Total chromatic number of unichord-free graphs
• Total colouring regular bipartite graphs is NP-hard
• Total colourings of graphs

Cited in

(9)

• Complexity-separating graph classes for vertex, edge and total colouring
• Total colorings-a survey
• Total chromatic number of \{square,unichord\}-free graphs
• Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs
• Separating type-I odd-cycle inequalities for a binary-encoded edge-coloring formulation
• Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs
• Clique-colouring and biclique-colouring unichord-free graphs
• Two complexity results for the vertex coloring problem
• Total chromatic number of unichord-free graphs

This page was built for publication: Complexity separating classes for edge-colouring and total-colouring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2391946)