Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs
From MaRDI portal
(Redirected from Publication:496654)
Abstract: A emph{unichord} in a graph is an edge that is the unique chord of a cycle. A emph{square} is an induced cycle on four vertices. A graph is emph{unichord-free} if none of its edges is a unichord. We give a slight restatement of a known structure theorem for unichord-free graphs and use it to show that, with the only exception of the complete graph , every square-free, unichord-free graph of maximum degree~3 can be total-coloured with four colours. Our proof can be turned into a polynomial time algorithm that actually outputs the colouring. This settles the class of square-free, unichord-free graphs as a class for which edge-colouring is NP-complete but total-colouring is polynomial.
Recommendations
- Total chromatic number of \{square,unichord\}-free graphs
- Total chromatic number of unichord-free graphs
- Complexity separating classes for edge-colouring and total-colouring
- Clique-colouring and biclique-colouring unichord-free graphs
- Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs
Cites work
- scientific article; zbMATH DE number 4085672 (Why is no real title available?)
- 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
- Complexity separating classes for edge-colouring and total-colouring
- Determining the total colouring number is NP-hard
- Edge-colouring and total-colouring chordless graphs
- On Total Chromatic Number of a Graph
- On the total coloring of certain graphs
- The determination of the total chromatic number of series-parallel graphs with \((G) \geq 4\)
- The total chromatic number of any multigraph with maximum degree five is at most seven
- The total coloring of a multigraph with maximal degree 4
- Total chromatic number of one kind of join graphs
- Total chromatic number of planar graphs with maximum degree ten
- Total chromatic number of unichord-free graphs
- Total colouring regular bipartite graphs is NP-hard
Cited in
(18)- Complexity-separating graph classes for vertex, edge and total colouring
- Total colorings-a survey
- scientific article; zbMATH DE number 6007698 (Why is no real title available?)
- A new characterization of unichord-free graphs
- Characterizing atoms that result from decomposition by clique separators
- Total chromatic number of \{square,unichord\}-free graphs
- Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs
- Requiring that minimal separators induce complete multipartite subgraphs
- scientific article; zbMATH DE number 4024813 (Why is no real title available?)
- Strongly unichord-free graphs
- Complexity separating classes for edge-colouring and total-colouring
- Clique-colouring and biclique-colouring unichord-free graphs
- Edge-colouring and total-colouring chordless graphs
- The complexity of \(G\)-free colourability
- \(\chi\)-bounds, operations, and chords
- Characterizing k-chordal unichord-free graphs
- Total chromatic number of unichord-free graphs
- New graph classes characterized by weak vertex separators and two-pairs
This page was built for publication: Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q496654)
