  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.
