Colorings and Homomorphisms of Minor Closed Classes
We relate acyclic (and star) chromatic number of a graph to the chromatic number of its minors and as a consequence we show that the set of all triangle free planar graphs is homomorphism bounded by a triangle free graph. This solves a problem posed in [[
- PDF / 398,420 Bytes
- 14 Pages / 439 x 666 pts Page_size
- 53 Downloads / 187 Views
Abstract We relate acyclic (and star) chromatic number of a graph to the chromatic number of its minors and as a consequence we show that the set of all triangle free planar graphs is homomorphism bounded by a triangle free graph. This solves a problem posed in [15]. It also improves the best known bound for the star chromatic number of planar graphs from 80 to 30. Our method generalizes to all minor closed classes and puts Hadwiger conjecture in yet another context.
1
Introduction
Denote by χa (G) the acyclic chromatic number of a graph G, i.e. the minimum number of colors which are sufficient for a (proper) coloring of the vertices of G so that every cycle in G gets at least 3 colors. It is known that χa is bounded for graphs of bounded genus and also for bounded degree graphs, see [2, 3] for the best known bounds. Similarly, let χst (G) denote the star chromatic number of a graph G, i.e. the minimal number of colors which are sufficient for a (proper) coloring of the vertices of G so that 4 vertices of every path of length 3 in G get at least 3 colors. Clearly χst (G) ≥ χa (G). It is known that χst is bounded whenever χa is bounded (folklore, see e.g. [6]). It is also well known that χa differs arbitrarily from χ as it is unbounded for bipartite graphs and even for bipartite 2-degenerated graphs: It suffices to consider the graph Kn which we get from Kn by subdividing every edge by a single vertex. We complement these results by the following result: Theorem 1.1. There exists a function f : N → N such that for any graph G holds χa (G) ≤ χst (G) ≤ f (max χ(H)) where the maximum is taken over all minors H of G. In fact f (n) ≤ cn2 where c is a constant. (The proof is in Section 3.) Recall, that G is a minor of H if G can be obtained from a subgraph of H by a sequence of edge-contractions. We consider only loopless simple graphs. B. Aronov et al. (eds.), Discrete and Computational Geometry © Springer-Verlag Berlin Heidelberg 2003
652
J. Neˇsetˇril and P. Ossona de Mendez
We denote by the minor relation for graphs. A class K is said to be minor closed if H ∈ K and G H implies G ∈ K. The class K is said to be proper if it does not contain all graphs. It follows that for any minor closed class K, {χa (G), G ∈ K} is bounded iff {χ(G), G ∈ K} is bounded. It follows that this is equivalent to bounded oriented chromatic number χ ( [12, 18]) and to bounded colorings of mixed graphs with colored edges ( [1,19]), see Theorem 6.1. We shall make use of the following two (we believe) well known results. We sketch a proof of Lemma 2 for completeness. √ Lemma 1. For each k, there exists some natural number h(k) < γk log k (for some constant γ) such that every graph of minimum degree at least h(k) contains Kk as a minor. This Lemma 1 has been proved by Kostochka [11] and Thomason [21] (extending earlier work of Mader [13]). The constant γ is well understood, [22]. Lemma 2. For any minor closed class K, {χ(G), G ∈ K} is bounded if and only if K is proper (i.e. different from the class of all graphs). Proof. If {χ(G), G ∈ C} is u
Data Loading...
