The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices
- PDF / 380,546 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 98 Downloads / 226 Views
Aequationes Mathematicae
The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices Naoki Matsumoto and Minako Tanaka
Abstract. The G´ arf´ as–Sumner conjecture asks whether for every tree T , the class of (induced) T -free graphs is χ-bounded. The conjecture is solved for several special trees, but it is still open in general. Motivated by the conjecture, the chromatic number of triangle-free and broom-free graphs is well studied, since a broom is one of the generalizations of a star, where a broom B(m, n) is the graph obtained from a star K1,n and an m-vertex path Pm by identifying the center of K1,n and a leaf of Pm . G´ arf´ as, Szemeredi and Tuza proved that for every triangle-free and B(m, n)-free graph G, χ(G) ≤ m + n − 1. This upper bound has been improved by Wang and Wu to m + n − 2 for m ≥ 2, n ≥ 1. In this paper, we prove that any triangle-free and B(4, 2)-free graph G is 3-colorable if the number of vertices of G is at least 17. Furthermore, the above estimation is the best possible since there exists a triangle-free and B(4, 2)-free 4-chromatic graph with sixteen vertices, named the Clebsch graph. Mathematics Subject Classification. 05C15. Keywords. Chromatic number, Triangle-free, Broom-free.
1. Introduction All graphs considered in this paper are finite, simple and undirected graphs. A k-coloring of a graph G is a map c : V (G) → {1, 2, . . . , k} such that for any edge uv ∈ E(G), c(u) = c(v). A graph G is k-colorable if G has a k-coloring, and the chromatic number of G, denoted by χ(G), is the smallest number k such that G is k-colorable. In particular, if χ(G) = k, then G is a k-chromatic graph. For a graph H, a graph G is H-free if G does not contain H as an induced subgraph. We refer the reader to [3] for other basic terminologies in graph theory. In the literature, Brooks [1] proved that every graph G is Δ(G)-colorable unless G is isomorphic to an odd cycle or a complete graph, where Δ(G) is the maximum degree of G. Brooks’ proof is simplified by some characterizations of cycles and complete graphs [2]. In their book [8, Problem 4.6], Jensen and Toft
N. Matsumoto, M. Tanaka
AEM
propose the problem of improving Brooks’ theorem in terms of the maximum degree for the class of triangle-free graphs. As far as we know, the best known result is χ(G) ≤ 23 (Δ(G) + 3) for any triangle-free graph G by Kostochka (personal communication in [8]). For more details and related topics, see [8, pp.83–85] and a survey [15]. A family of graphs is χ-bounded, first introduced in [6], if there exists a function f such that χ(G) ≤ f (ω(H)), whenever H is an induced subgraph of G, where ω(H) is the clique number of H. Every class of graphs with bounded chromatic number is χ-bounded, but there are several graph classes which are not χ-bounded; for example, it is shown in [4,5] that there exists a triangle-free graph with arbitrarily large chromatic number. On the other hand, for several special trees T , it is known that the family of T -free graphs is χ-bounded [6,19]. Thus G´ ar
Data Loading...
