On Coloring a Class of Claw-free Graphs
Yingjun Dai, Angèle M. Foley, Chı́nh T. Hoàng · Electronic Notes in Theoretical Computer Science · 2019
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. Recently, Frédéric Maffray and co-authors showed that the problem of coloring { claw , 4 K 1 , K 5 \ e }-free graphs can be solved in polynomial time. In this paper, we investigate a related class of graphs. A hole is an induced cycle of length at least 4. Two vertices x , y of a graph G are twins if for any vertex z different from x and y , xz is an edge if and only if yz is an edge. A hole-twin is the graph obtained from a hole by adding a vertex that forms a twin with some vertex of the hole. Hole-twins, and K 5 \ e , are interesting in their connection with line-graphs. They are among the forbidden subgraphs in the characterization of line-graphs. In this paper, we show there is a polynomial time algorithm to color ( claw , 4 K 1 , hole-twin)-free graphs.