A coloring algorithm for 4K(1)-free line graphs

作者：Fraser Dallas J; Hamel Angele M; Hoang Chinh T^*; Maffray Frederic

来源：Discrete Applied Mathematics, 2018, 234: 76-85.

DOI：10.1016/j.dam.2017.06.006

• Graph coloring
• Claw
• K-5 \ e
• Line-graph

Given a family F of graphs, let Free(F) be the class of graphs that do not contain any member of 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, 4K(1)}, = {claw, 4K(1), co-diamond}, and F = {C-4, 4K(1)}. In this paper, we study the coloring problem for Free(claw, 4K(1)). We solve the vertex coloring problem for a subclass of Free(claw, 4K(1)) which contains the class of 4K(1)-free line graphs.

• 出版日期2018-1-10