2015/06/18 by Dallas J. Fraser, Fraser, Dallas J., Angèle M. Hamel +4 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1506.05719
15 pages; updated a definition
openalex publication_date 2015/06/18 · arxiv created 2015/06/24 · arxiv updated 2015/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let L be a set of graphs. Free(L) is the set of graphs that do not contain any graph in L as an induced subgraph. It is known that if L is a set of four-vertex graphs, then the complexity of the coloring problem for Free(L) is known with three exceptions: L = claw, 4K1, L = claw, 4K1, co-diamond, and L = C4, 4K1. In this paper, we study the coloring problem for Free(claw, 4K1). We solve the coloring problem for a subclass of Free(claw, 4K1) which contains the class of 4K1-free line graphs. Our result implies the chromatic index of a graph with no matching of size four can be computed in polynomial time.