Counterexamples to a conjecture on injective colorings

Borut Lužar, Riste Škrekovski

Abstract


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.


Keywords


Injective coloring, planar graph, square graph

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.516.ada

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications