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

DOI10.1007/S11590-020-01679-9zbMATH Open1466.05075OpenAlexW3118332917MaRDI QIDQ828645FDOQ828645

Authors: D. 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

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

zbMATH Keywords

computational complexityhereditary graph classvertex colourability problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Decomposition by clique separators
• 4-coloring \(H\)-free graphs when \(H\) is small
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• Vertex coloring of graphs with few obstructions
• Title not available (Why is that?)
• The coloring problem for classes with two small obstructions
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Title not available (Why is that?)
• On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• Complexity of coloring graphs without paths and cycles
• On graphs with polynomially solvable maximum-weight clique problem
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Two complexity results for the vertex coloring problem
• Two cases of polynomial-time solvability for the coloring problem
• On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size
• Hereditary graph classes: When the complexities of <scp>coloring</scp> and <scp>clique cover</scp> coincide
• The weighted coloring problem for two graph classes characterized by small forbidden induced structures
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Polynomial cases for the vertex coloring problem
• Four-coloring P₆-free graphs
• Structure and algorithms for (cap, even hole)-free graphs
• 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
• 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
• The class of (P7,C4,C5)‐free graphs: Decomposition, algorithms, and χ‐boundedness
• A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions

Cited In (1)

• A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs

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)