Sharp upper bound of injective coloring of planar graphs with girth at least 5 (Q2165276)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sharp upper bound of injective coloring of planar graphs with girth at least 5 |
scientific article |
Statements
Sharp upper bound of injective coloring of planar graphs with girth at least 5 (English)
0 references
19 August 2022
0 references
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.
0 references
graph coloring
0 references
injective coloring
0 references
planar graph
0 references
discharging
0 references
0 references