Geodesic
Counterexamples to a conjecture on injective colorings
Ars Mathematica Contemporanea, Tome 8 (2015) no. 2, pp. 291-295.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.516.ada
Keywords: Injective coloring, planar graph, square graph 
@article{10_26493_1855_3974_516_ada,
     author = {Borut Lu\v{z}ar and Riste \v{S}krekovski},
     title = {Counterexamples to a conjecture on injective colorings},
     journal = {Ars Mathematica Contemporanea},
     pages = {291--295},
     publisher = {mathdoc},
     volume = {8},
     number = {2},
     year = {2015},
     doi = {10.26493/1855-3974.516.ada},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.516.ada/}
}
TY  - JOUR
AU  - Borut Lužar
AU  - Riste Škrekovski
TI  - Counterexamples to a conjecture on injective colorings
JO  - Ars Mathematica Contemporanea
PY  - 2015
SP  - 291
EP  - 295
VL  - 8
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.516.ada/
DO  - 10.26493/1855-3974.516.ada
LA  - en
ID  - 10_26493_1855_3974_516_ada
ER  - 
%0 Journal Article
%A Borut Lužar
%A Riste Škrekovski
%T Counterexamples to a conjecture on injective colorings
%J Ars Mathematica Contemporanea
%D 2015
%P 291-295
%V 8
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.516.ada/
%R 10.26493/1855-3974.516.ada
%G en
%F 10_26493_1855_3974_516_ada
Borut Lužar; Riste Škrekovski. Counterexamples to a conjecture on injective colorings. Ars Mathematica Contemporanea, Tome 8 (2015) no. 2, pp. 291-295. doi : 10.26493/1855-3974.516.ada. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.516.ada/

Cité par Sources :