The intersection of two vertex coloring problems
share
A hole is an induced cycle with at least four vertices. A hole is even if its number of vertices is even. 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. Currently, the following two problems are unresolved: the complexity of coloring even hole-free graphs, and the complexity of coloring 4K1, C4-free graphs. The intersection of these two problems is the problem of coloring 4K1, C4, C6-free graphs. In this paper we present partial results on this problem.
READ FULL TEXT