KAIST Discrete Math Seminar

An injective coloring of a graph G is an assignment of colors to the vertices of G so that any two vertices with a common neighbors receives distinct colors. The injective chromatic number, , is the minimum number of colors needed for an injective coloring. Let be the maximum average degree of G. In this paper, we show that if and . When , we show that mad(G) < \frac{36}{13}[/latex] implies [latex]\chi_i(G) \leq 5[/latex]. This is sharp; there is a subcubic graph [latex]H[/latex] such that [latex]mad(H) = \frac{36}{13}[/latex], but [latex]\chi_i(H) = 6[/latex]. This is joint work with Daniel Cranston and Gexin Yu.

The square G² of a graph G is the graph with the same vertex set as G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that for a planar graph G with maximum degree Δ(G)=3 we have χ(G²)≤7. Kostochka and Woodall conjectured that for every graph, the list-chromatic number of G² equals the chromatic number of G², that is χ_l(G²)=χ(G²) for all G. If true, this conjecture (together with Thomassen’s result) implies that every planar graph G with Δ(G)=3 satisfies χ_l(G²)≤7. We prove that every graph (not necessarily planar) with Δ(G)=3 other than the Petersen graph satisfies χ_l(G²)≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G)=3 and girth g(G)≥7, then χ_l(G²)≤7. Dvořák, Škrekovski, and Tancer showed that if G is a planar graph with Δ(G)=3 and girth g(G)≥10, then χ_l(G²)≤6. We improve the girth bound to show that: if G is a planar graph with Δ(G)=3 and g(G)≥9, then χ_l(G²)≤6. This is joint work with Daniel Cranston.