Injective colorings of graphs with low average degree

2009/02/27 Fri, 4PM-5PM ~~3PM-4PM~~

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, \(\chi_i(G)\), is the minimum number of colors needed for an injective coloring. Let \(mad(G)\) be the maximum average degree of G. In this paper, we show that \(\chi_i(G)\leq\Delta + 2\) if \(\Delta(G) \geq 4\) and \(mad(G) \leq \frac{14}{5}\). When \(\Delta(G) = 3\), 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.