Paper Info
Title
The Vertex Colourability Problem For {Claw, Butterfly}-Free Graphs Is Polynomial-Time Solvable
Abstract
The vertex colourability problem is to determine, for a given graph and a given natural k, whether it is possible to split the graph's vertex set into at most k subsets, each of pairwise non-adjacent vertices, or not. A hereditary class is a set of simple graphs, closed under deletion of vertices. Any such a class can be defined by the set of its forbidden induced subgraphs. For all but four hereditary classes, defined by a pair of connected five-vertex induced prohibitions, the complexity status of the vertex colourability problem is known. In this paper, we reduce the number of the open cases to three, by showing polynomial-time solvability of the problem for {claw, butter f ly}free graphs. A claw is the star graph with three leaves, a butter f ly is obtained by coinciding a vertex in a triangle with a vertex in another triangle.
Year
DOI
Venue
2021
10.1007/s11590-020-01679-9
OPTIMIZATION LETTERS
Keywords
DocType
Volume
Vertex colourability problem, Computational complexity, Hereditary graph class
Journal
15
Issue
ISSN
Citations 
2
1862-4472
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Dmitriy S. Malyshev100.68