On-line 3-chromatic graphs - I. Triangle-free graphs

This is the first half of a two-part paper devoted to on-line 3-colorable g raphs. Here on-line 3-colorable triangle-free graphs are characterized by a finite list of forbidden induced subgraphs. The key role in our approach i s played by the family of graphs which are both triangle- and (2K(2) + K-1) -free. Characterization of this family is given by introducing a bipartite modular decomposition concept. This decomposition, combined with the greedy algorithm, culminates in an on-line 3-coloring algorithm for this family. On the other hand, based on the characterization of this family, all 22 for bidden subgraphs of on-line 3-colorable triangle-free graphs are determined . As a corollary, we obtain the 10 forbidden subgraphs of on-line 3-colorab le bipartite graphs. The forbidden subgraphs in the finite basis characteri zation are on-line 4-critical, i.e., they are on-line 4-chromatic but their proper induced subgraphs are on-line 3-colorable. The results of this pape r are applied in the companion paper [Discrete Math., 177 (1997), pp. 99-12 2] to obtain the finite basis characterization of connected on-line 3-color able graphs (with 51 4-critical subgraphs). However, perhaps surprisingly, connectivity (or the triangle-free property) is essential in a finite basis characterization: there are infinitely many on-line 4-critical graphs.