| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6871713 | Discrete Applied Mathematics | 2018 | 10 Pages |
Abstract
Given a family F of graphs, let Free (F) be the class of graphs that do not contain any member of F as an induced subgraph. When F is a set of four-vertex graphs the complexity of the vertex coloring problem in Free (F) is known, with three exceptions: F={claw,4K1}, F={claw,4K1,co-diamond}, and F={C4,4K1}. In this paper, we study the coloring problem for Free (claw, 4K1). We solve the vertex coloring problem for a subclass of Free (claw, 4K1) which contains the class of 4K1-free line graphs.
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, Frédéric Maffray,