Coloring Powers and Girth
Résumé
Alon and Mohar (2002) posed the following problem: among all graphs G of maximum degree at most d and girth at least g, what is the largest possible value of χ(G t), the chromatic number of the tth power of G? For t ≥ 3, we provide several upper and lower bounds concerning this problem, all of which are sharp up to a constant factor as d → ∞. The upper bounds rely in part on the probabilistic method, while the lower bounds are various direct constructions whose building blocks are incidence structures. 1. Introduction. For a positive integer t, the tth power G t of a (simple) graph G = (V, E) is a graph with vertex set V in which two distinct elements of V are joined by an edge if there is a path in G of length at most t between them. What is the largest possible value of the chromatic number χ(G t) of G t , among all graphs G with maximum degree at most d and girth (the length of the shortest cycle contained in the graph) at least g? For t = 1, this question was essentially a long-standing problem of Vizing [11], one that stimulated much work on the chromatic number of bounded degree triangle-free graphs, and was eventually settled asymptotically by Johansson [6] using the probabilistic method. In particular, he showed that the largest possible value of the chromatic number over all girth 4 graphs of maximum degree at most d is Θ(d/ log d) as d → ∞. The case t = 2 was considered and settled asymptotically by Alon and Mohar [2]. They showed that the largest possible value of the chromatic number of a graph's square taken over all girth 7 graphs of maximum degree at most d is Θ(d 2 / log d) as d → ∞. Moreover, there exist girth 6 graphs of arbitrarily large maximum degree d such that the chromatic number of their square is (1 + o(1))d 2 as d → ∞. In this work, we consider this extremal question for larger powers t ≥ 3, which was posed as a problem in [2], and settle a range of cases for g. A first basic remark to make is that, ignoring the girth constraint, the maximum degree Δ(G t) of G t for G a graph of maximum degree at most d satisfies
Origine : Fichiers produits par l'(les) auteur(s)
Loading...