On 3-Coloring of ( )-Free Graphs.

The 3-coloring of hereditary graph classes has been a deeply-researched problem in the last decade. A hereditary graph class is characterized by a (possibly infinite) list of minimal forbidden induced subgraphs ; the graphs in the class are called -free. The complexity of 3-coloring is far from being understood, even for classes defined by a few small forbidden induced subgraphs.