The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
From MaRDI portal
Publication:828645
DOI10.1007/s11590-020-01679-9zbMath1466.05075OpenAlexW3118332917MaRDI QIDQ828645
Publication date: 5 May 2021
Published in: Optimization Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11590-020-01679-9
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of coloring graphs without paths and cycles
- Vertex coloring of graphs with few obstructions
- The coloring problem for classes with two small obstructions
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Two complexity results for the vertex coloring problem
- Polynomial cases for the vertex coloring problem
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Decomposition by clique separators
- The weighted coloring problem for two graph classes characterized by small forbidden induced structures
- Structure and algorithms for (cap, even hole)-free graphs
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
- 4-coloring \(H\)-free graphs when \(H\) is small
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- On coloring a class of claw-free graphs.
- Colouring \((P_r + P_s)\)-free graphs
- The intersection of two vertex coloring problems
- Colouring square-free graphs without long induced paths
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
- Colouring diamond-free graphs
- Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- 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
- The class of (P7,C4,C5)‐free graphs: Decomposition, algorithms, and χ‐boundedness
- Hereditary graph classes: When the complexities of <scp>coloring</scp> and <scp>clique cover</scp> coincide
- Four-coloring P6-free graphs
- Two cases of polynomial-time solvability for the coloring problem
- A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
