Counterexamples to a conjecture on injective colorings

Authors

  • Borut Lužar
  • Riste Škrekovski University of Ljubljana

DOI:

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

Keywords:

Injective coloring, planar graph, square graph

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.

Published

2015-02-03

Issue

Section

Articles