IMFM
Institute of Mathematics, Physics and Mechanics JADRANSKA 19, 1000 LJUBLJANA, SLOVENIA
Preprint series Vol. 48 (2010), 1110
ISSN 2232-2094
PLANAR GRAPHS WITH LARGEST INJECTIVE CHROMATIC NUMBERS
Borut Luzar
Ljubljana, January 19, 2010
o
Planar graphs with largest injective chromatic
numbers*
o &
1—1
&
Borut Luzar
1 Institute of Mathematics, Physics, and Mechanics Jadranska 19, 1111 Ljubljana, Slovenia borut.luzar@gmail.com
Abstract
An injective coloring of graphs is a vertex coloring where two vertices receive distinct colors if they have a common neighbor. In 1977, Wegner [12] posed a conjecture on the chromatic number of squares of graphs which remains unsolved ^	for planar graphs with maximum degrees A > 4. Obviously, the chromatic number
of the square of a graph is at least the injective chromatic number of a graph. We present examples and constructions of planar graphs for every A, which have the O	^ c™,,. number e^J to the I™, conjectured by Wegner.
I
Keywords: Graph coloring, injective coloring, planar graphs
CO
MSC2000: 05C15
1 Introduction
An injective coloring of a graph G is a mapping c : V(G) — {1, 2,..., k} such that
c(u) = c(v) for every pair of vertices u, v G V(G) that have a common neighbor. The
least k such that G is injectively 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, Kratochvll, Siran and
Sotteau [6] in 2002. In 2005, first results on planar graphs were given by Doyon, Hahn and
Raspaud [4]. As a corollary of the main theorem they obtained that if G is a planar graph
of maximum degree A and of 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.
The next result is due to Hahn, Raspaud, and Wang [7]. They investigated graphs without
K4-minor and showed that if G is a K4-minor free graph of maximum degree A, then
Xi(G) ^ r§A]. For planar graphs, they proved the following theorem:
• i 2
Theorem 1 If G is a planar (graph of maximum degree A > 3; then Xi(G) < A2 — A. Oh -
* Operation part financed by the European Union, European Social Fund.
Jh
1
o &
1—1 O
0 o
1
CO
£ CO CO
CO CD
$H
CD CO
$H
a
CD Jh
In 2006, Luzar, Skrekovski, and Tancer [9] proved several results for planar graphs of higher girth:
Theorem 2 Let G be a planar graph with maximum degree A. Then the following hold:
(a)	if g(G) > 19, then Xi(G) < A;
(b)	if g(G) > 10, then Xi (G) < A + 1;
(c)	if g(G) > 7 and A < 3, then Xi(G) < 5;
(d)	if g(G) > 5 and A > 439, then xi(G) < A + 4.
In 2009, Dimitrov, Luzar, and Skrekovski [3] completed Theorem 2 by proving that the injective chromatic number of planar graphs of girth at least 7 is at most A + 2. Some of these results were improved by Cranston, Kim, and Yu. They showed that for A > 4 all planar graphs with girth at least 13 can be injectively colored with A colors. Moreover, if a planar graph has girth at least 9, the injective chromatic number is at most A + 1.
When considering graphs of girth less than 5 the injective chromatic number considerably increases. In Fig. 1 a planar graph of girth 4 and injective chromatic number |A is presented.
Figure 1: Planar graph with maximum degree A and girth 4 that needs |A colors for an injective coloring.
Thus, it is natural to ask what is the upper bound for an injective chromatic number of planar graphs. In 2006, Hahn, Raspaud and Wang [7] asked whether it is true that for every planar graph G with maximum degree A holds that ;\i(G) < |~f A]. 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.
2 Planar graphs with largest injective chromatic numbers
The upper bounds of an injective chromatic number presented in this note correspond to orders of maximal planar graphs with diameter two. It is easy to see that the injective chromatic number of planar triangulations with diameter two is equal to their order.
Moreover, recall that the graph does not need to be a triangulation to have an injective chromatic number equal to its order, it is enough that there exists a path of length two between all pairs of its vertices.
The size of largest planar graphs of diameter two has been intensively studied. In 1993, Hell and Seyffarth [8] proved that the order of every planar graph G with diameter two and maximum degree A > 8, is at most |_|Aj +1. They also gave a construction of such graphs. Furthermore, they posed the lower bounds for largest possible order n of planar graphs of diameter two and maximum degree 4 < A < 7, and presented such graphs. Tishchenko [11] proved that the obtained lower bounds, n > A + 5, were in fact sharp.
Although these bounds were not proved yet, Wegner [12] posed a notable conjecture in 1977 on coloring squares of planar graphs which uses the same bounds for the required number of colors:
2
Conjecture 1 (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 |_|Aj + 1, otherwise.
Now we present planar graphs whose injective chromatic number, with exception of cubic graphs, is the bound proposed by Wegner.
Maximum degree A = 3. When subcubic graphs are considered, Conjecture 1 states that the square of any planar graph is 7-colorable. This result is announced to be proven by Thomassen, but it is not published yet. For injective colorings it seems that 5 colors 00 suffice. Theorem 1 implies that every subcubic planar graph is injectively 6-colorable. However, until now only the subcubic graphs with injective chromatic number 5 are known. In Fig. 2 a graph presented in [7] is depicted.
CSI CSI
£
CO CO
w
CD ■ i J-H
Figure 2: Planar cubic graph with injective chromatic number 5.
Maximum degree 4 < A < 7. Now, we present examples of planar graphs with maximum degree 4 < A < 7. Note that the graphs depicted in Fig. 3 were already presented in [8] and are the largest planar graphs with diameter 2 and fixed maximum degree A. In Fig. 4 we depict new graphs of maximum degree 5 < A < 9 with a different construction and injective chromatic number A + 5.
H
o &
1—1 O
0 o
1
CO
£ CO CO
CO CD
$H
CD CO
$H
a
CD Jh
Figure 3: Planar graphs with diameter 2 and maximum degree 4 < A < 7.
Figure 4: Planar graphs with diameter 2 and maximum degree 5 < A < 9.
Maximum degree A > 8. Finally, in Fig. 5 we give constructions for planar graphs with diameter 2 and maximum degree A > 8 which need |_|Aj + 1 colors for an injec-tive coloring. The constructions of planar graphs with arbitrary maximum degrees and chromatic number of the square graph equal to their order were known (see [12, 8]). In fact, we modify those graphs by inserting the paths Pa = a\a2 ■ ■ ■ ak, Pb = &1&2 ■ ■ ■ bk, and Pc = c1c2 ■ ■ ■ ck+1 (if A is odd, we introduce also the edge ck+1ck+2). These additional edges are providing the paths of length two between the vertices u, v, w and the vertices aj, bi, and q. Note that 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. However, for a sake of having simple construction we prefer to keep all of them. The left graph depicted in Fig. 5 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 all vertices, thus every vertex in the graph should receive different color for proper injective
Figure 5: Constructions of diameter 2 planar graphs with maximum degree at least 8 (even on the left and odd on the right) with injective chromatic number |_§Aj + 1.
0 o
1
CO ^
CO CO
coloring.
Thus, following Wegner's conjecture, we pose a new variation for the maximum injec-tive chromatic number of planar graphs:
Conjecture 2 Let G be a planar graph with maximum degree A. Then,
(a)	Xi(G) < 5, if A = 3;
(b)	Xi(G) < A+ 5, if 4 < A < 7;
(c)	Xi(G)< |jAj+M/A>8.
Note that the injective chromatic number is at most equal to the chromatic number of the square of a graph, therefore proving Wegner's conjecture would imply the proof of Conjecture 2.
Acknowledgement. The author would like to thank Riste Skrekovski for introducing the topic and fruitful discussions.
References
CO CD
$H
CD CO
u
a
CD U
[1]	N. Alon, M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992) 125-134.
[2]	D. W. Cranston, S-J. Kim, G. Yu, Injective colorings of sparse graphs, manuscript (2008).
[3]	D. Dimitrov, B. Luzar, R. Skrekovski, Injective coloring of planar graphs with A + 2 colors, manuscript (2009).
[4]	A. Doyon, G. Hahn, A. Raspaud, On the injective chromatic number of sparse graphs, preprint (2005).
k
k
o &
1—1 O
0 o
1
CO
£ CO CO
[5]	Z. Dvorak, D. Kral', P. Nejedly, R. Skrekovski, Coloring squares of planar graphs with girth .six, European J. Combin 29 (2008), 838-849.
[6]	G. Hahn, J. Kratochvil, J. Siran, D. Sotteau, On the injective chromatic number of graphs, Discrete Math. 256 (2002), 179-192.
[7]	G. Hahn, A. Raspaud, W. Wang, On the injective coloring of K4-minor free (graphs, preprint (2006).
[8]	P. Hell, K. Seyffarth, Largest planar graphs of diameter two and fixed maximum degree, Discrete Math. 111 (1993), 313-322.
[9]	B. Luzar, R. Skrekovski, M. Tancer, Injective coloring of planar graphs with few colors, to appear in Discrete Math.
[10]	M. Molloy, M. R. Salavatipour, A bound on the chromatic number of the square of a planar graph, J. Combin. Theory Ser. B. 94 (2005), 189-213.
[11]	S. A. Tishchenko, The largest graphs of diameter 2 and fixed Euler characteristics, Fundam. Prikl. Mat. 7 (2001), 1203-1225.
[12]	G. Wegner, Graphs with given diameter and a coloring problem, Technical report, University of Dortmund, Germany (1977).
CO CD
$H
CD CO
u
a
CD U