A LOWER BOUND ON COCHROMATIC NUMBER FOR LINE GRAPHS OF A KIND OF GRAPHS

摘要

Erdoes, Gimbel and Straight (1990) conjectured that if ω(G) < 5 and z(G) > 3, then z(G) ≥ χ(G) - 2. But by using the concept of edge cochromatic number it is proved that if G is the line graph of a connected triangle-free graph with ω(G) < 5 and G ≠ K_4, then z(G) ≥ χ(G) -2.