The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
type: Item
instance of: scholarly article
title: The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
zbMATH Open document ID: 1466.05075
published in: Optimization Letters
publication date: 2021-05-05T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 7343952
zbMATH Keywords: vertex colourability problem
zbMATH Keywords: computational complexity
zbMATH Keywords: hereditary graph class
author: D. S. Malyshev
MaRDI profile type: Publication
full work available at URL: s11590-020-01679-9
OpenAlex ID: W3118332917
cites work: On graphs with polynomially solvable maximum-weight clique problem
cites work: Hereditary graph classes: When the complexities of <scp>coloring</scp> and <scp>clique cover</scp> coincide
cites work: Three-coloring and list three-coloring of graphs without induced paths on seven vertices
cites work: Updating the complexity status of coloring graphs without a fixed induced linear forest
cites work: The class of (P7,C4,C5)‐free graphs: Decomposition, algorithms, and χ‐boundedness
cites work: Structure and algorithms for (cap, even hole)-free graphs
cites work: Colouring diamond-free graphs
cites work: On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
cites work: On coloring a class of claw-free graphs.
cites work: The intersection of two vertex coloring problems
cites work: Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
cites work: Q4198056
cites work: Colouring square-free graphs without long induced paths
cites work: A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
cites work: 4-coloring \(H\)-free graphs when \(H\) is small
cites work: Complexity of coloring graphs without paths and cycles
cites work: Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
cites work: Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
cites work: Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
cites work: Q5755526
cites work: Polynomial cases for the vertex coloring problem
cites work: Q4448764
cites work: Colouring \((P_r + P_s)\)-free graphs
cites work: Vertex coloring of graphs with few obstructions
cites work: The coloring problem for classes with two small obstructions
cites work: The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
cites work: Two cases of polynomial-time solvability for the coloring problem
cites work: The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
cites work: The weighted coloring problem for two graph classes characterized by small forbidden induced structures
cites work: Two complexity results for the vertex coloring problem
cites work: A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
cites work: On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size
cites work: Four-coloring P6-free graphs
cites work: Decomposition by clique separators
DOI: 10.1007/S11590-020-01679-9
description: scientific article; zbMATH DE number 7343952