The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable

DOI10.1007/s11590-020-01679-9zbMath1466.05075OpenAlexW3118332917MaRDI QIDQ828645

Dmitriy S. Malyshev

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

zbMATH Keywords

computational complexityhereditary graph classvertex colourability problem

Mathematics Subject Classification ID

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 P₆-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