An injective coloring of a graph is a vertex coloring where two vertices receive distinct colors if they have a common neighbor. Chen, Hahn, Raspaud, and Wang conjectured that every planar graph with maximum degree Δ ≥ 3 admits an injective coloring with at most ⌈3Δ / 2⌉ colors. We present an infinite family of planar graphs showing that the conjecture is false for graphs with small or even maximum degree. We conclude this note with an alternative conjecture, which sheds some light on the well-known Wegner’s conjecture for the mentioned degrees.
@article{516,
title = {Counterexamples to a conjecture on injective colorings},
journal = {ARS MATHEMATICA CONTEMPORANEA},
volume = {11},
year = {2015},
doi = {10.26493/1855-3974.516.ada},
language = {EN},
url = {http://dml.mathdoc.fr/item/516}
}
Lužar, Borut; Škrekovski, Riste. Counterexamples to a conjecture on injective colorings. ARS MATHEMATICA CONTEMPORANEA, Tome 11 (2015) . doi : 10.26493/1855-3974.516.ada. http://gdmltest.u-ga.fr/item/516/