Structures and chromaticity of extremal 3-colourable sparse graphs

Abstract

Assume that G is a 3-colourable connected graph with e(G) = 2v(G) - k, where k ≥ 4. It has been shown that s3(G) ≥ 2k-3, where sr(G) - P(G, r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s3(G) < 2k-2, then G contains at most v(G) - k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle Ck by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel Wn by deleting all but s consecutive spokes. © Springer-Verlag 2001.