Complexity separating classes for edge-colouring and total-colouring
DOI10.1007/S13173-011-0040-8zbMATH Open1275.68074OpenAlexW2077973426MaRDI QIDQ2391946FDOQ2391946
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)
Full work available at URL: https://doi.org/10.1007/s13173-011-0040-8
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
computational complexitytotal chromatic numbertheoretical computer sciencecolouring of graphsbipartite unichord-free
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)
Cites Work
- List edge and list total colourings of multigraphs
- Total colourings of graphs
- Total chromatic number of unichord-free graphs
- NP completeness of finding the chromatic index of regular graphs
- Total colouring regular bipartite graphs is NP-hard
- A structure theorem for graphs with no cycle with a unique chord and its consequences
- The NP-completeness column: an ongoing guide
- Chromatic index of graphs with no cycle with a unique chord
- The total chromatic number of some bipartite graphs.
- Edge-colouring and total-colouring chordless graphs
- Total chromatic number of \{square,unichord\}-free graphs
Cited In (9)
- Clique-colouring and biclique-colouring unichord-free graphs
- Total colorings-a survey
- Total chromatic number of unichord-free graphs
- Total chromatic number of \{square,unichord\}-free graphs
- Separating type-I odd-cycle inequalities for a binary-encoded edge-coloring formulation
- Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs
- Complexity-separating graph classes for vertex, edge and total colouring
- Two complexity results for the vertex coloring problem
- Complexity of colouring problems restricted to unichord-free and square, 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)
