Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949503 | Discrete Applied Mathematics | 2017 | 9 Pages |
Abstract
Given a set L of graphs, a graph G is L-free if G does not contain any graph in L as an induced subgraph. There has been keen interest in colouring graphs whose forbidden list L contains graphs with four vertices. A recent paper of Lozin and Malyshev (in press) discusses the state of the art on this problem, identifying three outstanding classes: L=(4K1,claw), L=(4K1,claw, co-diamond), and L=(4K1,C4). In this paper we investigate the class of (4K1, C4, C5)-free graphs and show that if G is a (4K1, C4, C5)-free graph, then G either has bounded clique width or is perfect.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Dallas J. Fraser, Angèle M. Hamel, ChÃnh T. Hoà ng, Kevin Holmes, Tom P. LaMantia,