The vertex colourability problem for \claw, butterfly\-free graphs is polynomial-time solvable

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

Recommendations

Polynomial cases for the vertex coloring problem
scientific article; zbMATH DE number 5179133
Coloring vertices of claw-free graphs in three colors
The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
On the structure of graphs without claw, \(4K_1\) and co-R

Cites work

scientific article; zbMATH DE number 3639144 (Why is no real title available?)
scientific article; zbMATH DE number 2044943 (Why is no real title available?)
scientific article; zbMATH DE number 5179133 (Why is no real title available?)
4-coloring \(H\)-free graphs when \(H\) is small
A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
A survey on the computational complexity of coloring graphs with forbidden subgraphs
Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
Colouring \((P_r + P_s)\)-free graphs
Colouring diamond-free graphs
Colouring square-free graphs without long induced paths
Complexity of coloring graphs without paths and cycles
Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
Decomposition by clique separators
Four-coloring \(P_6\)-free graphs
Hereditary graph classes: When the complexities of <scp>coloring</scp> and <scp>clique cover</scp> coincide
Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
On coloring a class of claw-free graphs.
On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
On graphs with polynomially solvable maximum-weight clique problem
On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
Polynomial cases for the vertex coloring problem
Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
Structure and algorithms for (cap, even hole)-free graphs
The class of \((P_7, C_4, C_5)\)-free graphs: decomposition, algorithms, and \(\chi \)-boundedness
The coloring problem for classes with two small obstructions
The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
The intersection of two vertex coloring problems
The weighted coloring problem for two graph classes characterized by small forbidden induced structures
Three-coloring and list three-coloring of graphs without induced paths on seven vertices
Two cases of polynomial-time solvability for the coloring problem
Two complexity results for the vertex coloring problem
Updating the complexity status of coloring graphs without a fixed induced linear forest
Vertex coloring of graphs with few obstructions

Cited in

(3)

A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
Polynomial cases for the vertex coloring problem

This page was built for publication: The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable

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