¿^creative	, ars mathematica
^commons	contemporánea
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 8 (2015) 291-295
Counterexamples to a conjecture on injective colorings*
Borut LuZar, Riste Skrekovski
Faculty of Information Studies, Novo mesto, Slovenia, Institute ofMathematics, Physics and Mechanics, Ljubljana, Slovenia
Received 23 July 2013, accepted 5 May 2014, published online 5 February 2015 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 [3] conjectured that every planar graph with maximum degree A > 3 admits an injective coloring with at most |"3A/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. Math. Subj. Class.: 05C10, 05C15
1 Introduction
An injective k-coloring of a graph G is a mapping c : V(G) ^ {1,2,..., k} such that c(u) = c(v) for every pair of distinct vertices u,v e V(G) having a common neighbor. The least k such that G is injectively k-colorable is the injective chromatic number of G, denoted by Xi(G). Note that this type of coloring is not necessarily proper.
The injective coloring of graphs was first introduced by Hahn, Kratochvil, Siran and Sotteau [7] in 2002. The first results on the injective chromatic number of planar graphs were presented by Doyon, Hahn and Raspaud [6] in 2005. As a corollary of the main theorem they obtained that if G is a planar graph of maximum degree A and girth g(G) > 7, then the injective chromatic number is at most A + 3. Moreover, if g(G) > 6 then Xi(G) < A+4, and if g(G) > 5 then Xi(G) < A+8. Chen, Hahn, Raspaud, and Wang [3] investigated K4 -minor-free graphs and showed that if G is such a graph of maximum degree A, then Xi(G) < [§A]. Moreover, they conjectured that the same bound holds for all planar graphs:
* Partially supported by ARRS Program P1-0383 and Creative Core - FISNM - 3330-13-500033.
E-mail addresses: borut.luzar@gmail.com (Borut LuZar), skrekovski@gmail.com (Riste Skrekovski)
©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/
292
Ars Math. Contemp. 8 (2015) 291-295
Figure 1: A planar graph with maximum degree A and girth 4 that needs § A colors for an injective coloring.
Conjecture 1.1 (Chen, Hahn, Raspaud, and Wang). For every planar graph G with maximum degree A > 1, it holds that
Xi(G) <
2A
The conjecture holds for planar graphs with large girth. There is a number of results (see e.g. [1, 2, 4, 5, 8]) showing that if the girth of a planar graph is at least 5, the injective chromatic number of a graph is at most A + C, where C is some small constant. When considering graphs of girth smaller than 5 the injective chromatic number considerably increases. In Fig. 1 a planar graph of girth 4 and injective chromatic number 2 A is depicted.
In this note we present examples of planar graphs with maximum degree A > 4 and injective chromatic number A + 5, for 4 < A < 7, and [| Aj + 1, for A > 8. Thus providing counterexamples to Conjecture 1.1 for planar graphs with maximum degree at most 7 or even.
The central problem regarding the chromatic number of squares of planar graphs is the well-known Wegner's conjecture [9] proposed in 1977. Note that for larger A, the bound of this conjecture is one more than that of Conjecture 1.1.
Conjecture 1.2 (Wegner). Let G be a planar graph with maximum degree A. The chromatic number of square graph G2 is at most 7, if A = 3, at most A+ 5, if 4 < A < 7, and at most |_2 A + 1, otherwise.
2 Planar graphs with largest injective chromatic numbers
Using the following result we easily disprove Conjecture 1.1 for every A G {4, 5,6,7} and for every even A > 8. We believe that the bound for graphs with maximum degree 3 is correct, however.
Theorem 2.1. There exist planar graphs G of maximum degree A > 3 satisfying the following:
(a) Xi (G) = 5, if A = 3;
B. Luzar and R. Skrekovski: Counterexamples to a conjecture on injective colorings
293
(b)	Xi(G) = A + 5, if 4 < A < 7;
(c)	Xi(G) = L 2 Aj + 1, if A > 8.
Proof. For A = 3, i.e., the case (a) of the theorem, a cubic planar graph with the injective chromatic number equal to 5 was presented in [3] (see Fig. 2). For A > 4, the following simple characterization will be used:
(*) A graph G has injective chromatic number equal to its order, if and only if
1.	G has diameter 2; and
2.	every edge of G belongs to a triangle.
Figure 3: Planar graphs with diameter 2 and maximum degree A G {4,..., 9}.
In Fig. 3 planar graphs with maximum degree A G {4,..., 9} are presented. Note that these graphs are of diameter 2 and of orders 9, 10, 11, 12, 13, and 14, respectively.
294
Ars Math. Contemp. 8 (2015) 291-295
Figure 4: Constructions of diameter 2 planar graphs with maximum degree A >8 (even on the left and odd on the right) and the injective chromatic number equal to |_f A + 1.
Moreover, they have the property that each of their edges belongs to a 3-cycle. By (*), it follows that each of them has chromatic index equal to its order. As these graphs have maximum degree 4, 5, 6, 7, 8, and 9, respectively, we conclude that each of them satisfies the identity of the case (6) of the theorem. Finally, we consider the case (c) of the theorem. We give constructions for planar graphs with diameter 2, maximum degree A > 8, and order [§ A J + 1, where each edge belongs to a 3-cycle. Then by (*), the claim (c) of the theorem immediately follows.
We distinguish two cases regarding whether A is even or odd (see Fig. 4 for an illustration). In both cases we start with a path uvw. Then we insert the paths Pa = a1a2 • • • ak, Pb = b1b2 • • • bk, and Pc = cic2 • • • cfc+1 (if A is odd, we introduce also the edge cfc+1cfc+2). These additional edges are providing paths of length two between the vertices u, v, w and the vertices ai, bi, and ci.
The left graph depicted in Fig. 4 has maximum degree A = 2k + 2 and the right one has A = 2k + 3, for k > 3. It is easy to see that there is a path of length two between every pair of vertices, thus every vertex in the graph should receive a different color in an injective coloring.	□
Let us remark that the presented graphs from the above theorem are not the only ones with such properties. For example in the last construction all the edges of the paths Pa, Pb, and Pc are not really needed to obtain a graph with the desired properties. In fact, it is enough that each vertex of these paths is incident with one edge of the path, so roughly every second is redundant.
We conclude the paper with an attempt to correct Conjecture 1.1 by proposing the following Wegner type conjecture for the injective chromatic number of planar graphs:
Conjecture 2.2. Let G be a planar graph with maximum degree A. Then
(а)	x (G) < 5, if A = 3;
(б)	Xi (G) < A + 5, if 4 < A < 7;
(c) Xi (G) < [2 Aj + 1, if A > 8.
Since the injective chromatic number is at most equal to the chromatic number of the square of a graph, proving Wegner's conjecture would imply the truth of Conjecture 2.2. If
B. Luzar and R. Skrekovski: Counterexamples to a conjecture on injective colorings
295
Wegner's conjecture holds, then the extremal graphs (i.e. the graphs that attain the upper bound) of both conjectures coincide for A's from Theorem 2.2. As the injective coloring is a relaxed version of coloring the square one may reason that colorability of the square is mainly conducted by the injective incidence of the vertices.
References
[1]	O. V. Borodin and A. O. Ivanova, Injective (A + 1)-coloring of planar graphs with girth 6, Sib. Math. J. 52 (2011), 23-29.
[2]	Y. Bu, D. Chen, A. Raspaud and W Wang, Injective coloring of planar graphs, Discrete App. Math. 157 (2009), 663-672.
[3]	M. Chen, G. Hahn, A. Raspaud and W. Wang, Some results on the injective chromatic number of graphs, J. Comb. Optim. 24 (2012), 299-318.
[4]	D. W. Cranston, S-J. Kim and G. Yu, Injective Colorings of Graphs with Low Average Degree, Algorithmica 60 (2011), 553-568.
[5]	W. Dong and W. Lin, Injective coloring of planar graphs with girth 6, Discrete Math. 313 (2013), 1302-1311.
[6]	A. Doyon, G. Hahn and A. Raspaud, Some bounds on the injective chromatic number of graphs, Discrete Math 310 (2010), 585-590.
[7]	G. Hahn, J. Kratochvil, J. Siran and D. Sotteau, On the injective chromatic number of graphs, Discrete Math. 256 (2002), 179-192.
[8]	B. Luzar, R. Skrekovski and M. Tancer, Injective coloring of planar graphs with few colors, Discrete Math 309 (2009), 5636-5649.
[9]	G. Wegner, Graphs with given diameter and a coloring problem, Technical report, University of Dortmund, Germany (1977).