FB Mathematik & Informatik, Freie Universität Berlin, WE 2, Freie Universität Berlin, Arnimallee 3, 14195, Berlin, Germany
Abstract:
The relation of chromatic aspects and the existence of certain induced subgraphs of a triangle-free graph will be investigated. Based on a characterization statement of Pach, some results on the chromatic number of triangle-free graphs with certain forbidden induced subgraphs will be refined by describing their structure in terms of homomorphisms. In particular, we introduce chordal triangle-free graphs as a natural superclass of chordal bipartite graphs and describe the structure of the maximal triangle-free members. Finally, we improve on the upper bound for the chromatic number of triangle-free sK2-free graphs by 1 for s2 giving the tight bound for s=3.