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.