Sharp upper bound of injective coloring of planar graphs with girth at least 5 (Q2165276): Difference between revisions

An injective \(k\)-coloring of a graph \(G\) is a (not necessarily proper) coloring \(c\) of the vertices of \(G\) by \(k\) colors such that \(c(u) \neq c(v)\) whenever \(u\) and \(v\) have a common neighbor in \(G\). The injective chromatic number \(\chi_i(G)\) is the least integer \(k\) such that \(G\) has an injective \(k\)-coloring. In this paper, the authors prove that if \(G\) is a planar graph with girth at least \(5\) and maximum degree \(\Delta(G) \geq 2339\), then \(\chi_i(G) \leq \Delta(G)+1\). This improves upon several previous results on the injective chromatic number of planar graphs with girth at least \(5\). The proof is based on a quite involved discharging procedure involving extensive case analysis.