IMFM
Institute of Mathematics, Physics and Mechanics JADRANSKA 19, 1000 LJUBLJANA, SLOVENIA
Preprint series Vol. 49 (2011), 1142
ISSN 2232-2094
LINEAR COLOURING OF PLANAR GRAPHS WITH PRESCRIBED GIRTH AND MAXIMUM DEGREE
Rok Erman Riste Skrekovski
Ljubljana, March 11, 2011
Linear colouring of planar graphs with prescribed girth
and maximum degree
Rok Erman a and Riste Skrekovski March 10, 2011
J-i
A
O u
CSI CSI
u
cu
b
a Institute of Mathematics, Physics and Mechanics, Jadranska 19,1000 Ljubljana, Slovenia. Email: rok. erman@gmail. com b Department of Mathematics, University of Ljubljana, Jadranska 21, 1000 Ljubljana, Slovenia. Email: skrekovski@gmail. com
Keywords: Linear colouring; Girth; Maximum degree
Abstract
A linear colouring of a graph is a proper vertex colouring such that the subgraph induced by any two colour classes is a set of vertex disjoint paths. The corresponding linear chromatic number of a graph G, namely lc(G), is the minimum number of colours in a linear colouring of G. We prove that for a graph G with girth g > 8 and maximum degree A > 7 the inequality on its linear colouring number holds:
lc(G) < [fl + 1. This improves the girth assumption of a previously known bound of Raspaud and Wang [9].
CO
1 Introduction
All graphs in this paper are undirected, simple and finite. For standard graph definitions the reader is referred to [3]. A colouring of the vertices of a graph G = (V, E) is a mapping c : V ^ N; we call elements of N colours. A colouring is proper if any two adjacent vertices are mapped to different colours. A proper vertex colouring is called linear if the subgraph induced by the union of any two colour classes is a set of vertex disjoint paths. The minimum number of colours in a linear colouring of a graph G is the linear chromatic number lc(G).
The notion of a linear colouring was first introduced by Yuster [11] who proved that lc(G) = O(A3/2) where A is the maximum degree. He also constructed graphs with lc(G) = Q(A3/2) which showed that his bound is the best possible for general graphs.
In [9] Raspaud and Wang proved that lc(G) = f^] + 1 for a planar graph that satisfies one of the following conditions: (1) g > 13 and A > 3; (2) g > 11 and A > 5; (3) g > 9
and A > 7; (4) g > 7 and A > 13. In a wider sense this improves the bound of Yuster to lc(G) = O(A) for planar graphs with large enough girth and maximum degree.
CSI f 1—1 1—1
A
o u d
csi
To prove our theorem we will use the discharging method which was first used by Wernicke [10]. The discharging method is a technique used to prove statements in structural graph theory, and it is commonly applied in the context of planar graphs. It is most well-known for its central role in the proof of the Four Colour Theorem.
A linear colouring is a special case of an acyclic colouring, where it is required that the subgraph induced by the union of any two colour classes is a forest. This colouring has been introduced by Granbaum [5] and later studied in [1, 2, 7, 8]. It is clear that lc(G) > A(G), where A(G) is the acyclic chromatic number of G. Acyclic colouring has also been extended to acyclic list colouring by Esperet et al.[4] A related concept is that of k-frugal colourings, considered by Hind et al. [6], where a graph is k-frugal if it can be properly coloured so that no colour appears k times in a vertex neighbourhood. Such a colouring is called a k-frugal colouring. Clearly, a linear colouring is 3-frugal, but the converse is not necessarily true.
We use the following notation. Let N(v) be the set of neighbours of v and N2(v) the neighbours of v of degree two. Denote by l(f) the length of a face f. A n-vertex is a vertex of degree n. A <n-vertex and >n-vertex is a vertex of degree at most n and at least n respectively. Let c be a colouring of a graph. Denote the colours that appear twice in the neighbourhood of a vertex v by c2(v).
As we already mentioned, Raspaud and Wang proved that a planar graph with girth g > 9 and maximum degree A > 7 allows a linear colouring with at most + 1 colours. We improved the restriction on girth and so obtained the following:
Theorem 1.1. Let G be a planar graph with maximum degree A > 7 and girth g > 8. Then G has s linear colouring with at most + 1 colours.
2 Proof of the theorem
C^
In the proof, we will use the discharging method. To obtain a contradiction we will suppose that we have a minimal counterexample G to the theorem regarding the number of vertices. First we will prove that some planar configurations are reducible, i.e. cannot S occur in the minimal counterexample. Then we assign the initial charge to every vertex and every face with negative total sum. Next we redistribute the charge in such a way that the final charge is nonnegative for every vertex and face. This will be a contradiction that establishes the theorem.
2.1 Reducible configurations
In the proof we use the following reducible configurations:
CD
(Q1): a 1-vertex;
(Q2): a 2-vertex adjacent to another 2-vertex and a vertex of degree less than seven;
I ^
(Q3): a 2-vertex adjacent to a 3-vertex and a vertex of degree less than five;
• i
(Q4): a 2-vertex adjacent to a <5-vertex and a 3-vertex which is also adjacent to a 2-vertex and a <5-vertex (see Figure 3);
(Q5): a 7-vertex adjacent to seven 2-vertices where 5 of them are again adjacent to another 2-vertex and the remaining two 2-vertices have another neighbour of degree <3 (see Figure 4);
(Q6): a 7-vertex adjacent to five 2-vertices where each of them is again adjacent to another 2-vertex and the remaining two neighbours are of degree <3 and both have 2-vertices as the remaining neighbours (see Figure 5).
The reducibility of each of the above configurations is proven in a separate lemma. The lemmas provide the proof only for the case when the degrees are maximal as to the < conditions in the configuration. As it will be clear from the proofs, the reasoning for proving the reducibility for lower degrees is even simpler. It will be implicitly assumed that such configurations are not present in the possible minimal counterexample of Theorem 1.1
A
O u ti
Lemma 2.1. (Q1) i.e. a 1-vertex is reducible.
J-i

Proof. A 1-vertex v adjacent to x is clearly reducible since removing it yields a smaller graph that can be coloured by minimality of G. This colouring can be extended since colouring v with a colour that does not appear twice in the neighbourhood of x or on x is obviously proper. The number of forbidden colours for v is then at most c2 (x) + 1 = L^f1] + 1 = [■§■], and so we have at least one available colour for v.
□
Lemma 2.2. (Q2) i.e. a 2-vertex adjacent to another 2-vertex and a vertex of degree at most six is reducible.
Proof. Let v be a 2-vertex adjacent to a 2-vertex x and to y a vertex of degree < 7. After removing v we are left with a smaller graph which has a linear colouring c by minimality of G. We will now extend this colouring to v by considering two cases:
•	Case 1: c(x) = c(y). Colouring v with a colour distinct from c(x) that does not appear twice in N(y) or on the other neighbour of x clearly gives a linear colouring of G. Thus the number of forbidden colours for v is at most |c2(y)| + 1 + 1 =
+ 1 + 1 < |_%rJ +2 = 4. But since A > 7 we have at least 5 colours, we can choose such a colour for v.
•	Case 2: c(x) = c(y). Colouring v with a colour distinct from c(x) and c(y) that does not appear twice in N(y) is again linear. The number of forbidden colours in this case is |c2 (^r) | + 2 <	+2 = 4 and again with at least 5 colours we can choose a colour for v.
□
x	v	y
CO CD
$H
CD CO
$H
cu	Lemma 2.3. (Q3) i.e. a 2-vertex adjacent to a 3-vertex and a vertex of degree at most
four is reducible.
Figure 1: Reducible configuration (Q2).
Proof. Let v be a 2-vertex adjacent to a 3-vertex x and y with degree < 5. Let x\ and x2 be the other neighbours of x. Again removing v gives a smaller graph with a linear colouring c (by minimality of G). We distinguish two cases:
•	Case 1: c(x) = c(y). Ifwe colour v with a colour that is not in c2(y)U{c(x), c(xi), c(x2)} the result is a linear colouring of G. This set contains |c2(y)| + |{c(x), c(x1), c(x2)}| < L^J +3 = 4 colours, but as we have at least 5 available colours, we can easily colour v in the desired way.
•	Case 2: c(x) = c(y). Assigning a colour to v distinct from colours in c2(y), c(x), c(y) and c(x1) gives a linear colouring. The inequality |c2(y)| + |{c(x), c(x1), c(y)}| < L^J +3 = 4 assures that we have at least one available colour left for v.
W
u
□
y
C^
Figure 2: Reducible configuration (Q3).
Lemma 2.4. (Q4) i.e. a 2-vertex adjacent to a 5-vertex and a 3-vertex where its other neighbours are of degree 2 and <5 is reducible.
CO
Proof. Since A > 7 the number of colours we use is at least 5. Let v be a 2-vertex adjacent
CSI
to a 3-vertex x and a 5-vertex y, and let x1 and x2 be the other two neighbours of x. Let x1 be of degree 2 and x2 of degree <5. Let xi be the other neighbour of x1. In order to simplify the proof we define the set S = N(y) \ {v} U {x1, x2} and T = N(x2) \ {x} U {x1}. We remove v and colour the remaining graph by minimality of G. We may assume that c(y) = 1. We distinguish two cases:
• Case 1: c(x) = 1. Observe that one of the remaining colours appears at most once in the set S since |S| = 6. We assign this colour to v and hereby obtain a linear colouring of G.
Case 2: c(x) = 1. Say, c(x) = 2. If the colouring c cannot be extended to v, we
may assume the following
i
5H CD W
U
- c(x1) = c(x2) = 3,
— each of the colours 4 and 5 appear twice in N(y) \ {v}.
We uncolour x and assign the colour 2 to v. Now we only need to colour x with 1, 4 or 5. If this in not possible then each of the colours 1, 4 and 5 appear twice in T, which is impossible since |T| = 5.
v

A
o u

0 o
1
CO ^
CO CO
m
CD
$H
CD
m
u
a
CD U
Figure 3: Reducible configuration (Q4).
Lemma 2.5. (Q5) i.e. a 7-vertex adjacent to seven 2-vertices where 5 of them are again adjacent to a 2-vertex and 2 of them are adjacent to 3-vertices is reducible.
Proof. Let v, x\,..., x7, y\,... ,y7, z\,..., z7 and z'6, z'7 be vertices as in Figure 4. If we remove the star S = (v,xi,... , x7} the resulting graph has a linear colouring c by the minimality of G. Now we want to extend this colouring to the whole graph G. Let the list of all possible colours be col = {1,..., + 1}. Since A > 7 we know that |col| > 5.
Denote the lists of available colours for vertex xi by L(xj) = col \ {c(yi), c(z^)} for those xi adjacent to 2-vertices and L(xi) = col \ {c(yi), c(zi), c(z')} for those xi adjacent to 3-vertices.
Observe that at most two xj can be coloured the same. Our problem can be now put in terms of finding a matching in a bipartite graph H constructed as follows: In partition A we will have the vertices x1,...,x7 and in partition B the vertices u1,... ,u5,u[,... ,u'5. Here (in partition B) the indices correspond to the 5 colours we have at our disposal. Any vertex xj with its list of admissible colours L(xj) is connected to the vertices in B which have indices in L(xj). This means that the vertices in A are all of degree 6 or 4. If we find a matching in H which covers A this will correspond to a proper colouring of x1,... ,x7, where each colour appears at most twice. The colour of xj would simply be the index k of the vertex uk or u'k that xj is matched by. If we can then also properly colour v the result will be a linear colouring. Let us show that this is indeed possible.
Hall's theorem states that we can find a matching in a bipartite graph covering the partition A if for each S C A the inequality |S| > |N(S)| holds. In our case the condition clearly holds for each |S | < 6 since each vertex in A has degree 6 or 4 and only 2 are of degree 4.
The only case where we can have a problem is when S = A and the lists are of the form: L(xi) = {1, 2, 3} if yi is a 2-vertex and L(xi) C {1, 2, 3} if yi is a 3-vertex.
Let u be the size of the union of all lists, i.e. u = | U (L(xi))|. Now in other words we only have a problem when u = 3. This means that the lists for those xi adjacent to 2-vertices are the same and the lists for those xi adjacent to 3-vertices are subsets of this list. In this case we have |S| = 7 and N(S) = 6. We will deal with this case later.
Let us now suppose that u > 4 and try to colour v. If any colour does not appear on x1,..., x7 we use that colour for v and the proof is complete. So now we suppose that all colours are used on the vertices x1,..., x7. Without loss of generality the colours used on x1,..., x7 are the multiset {1,1, 2, 2, 3, 4, 5} and we may assume that the colour 3 is not
v

A
o u

0 o
1
CO ^
CO CO
Figure 4: Reducible configuration (Q5).
used for x6 or x7. We now recolor the vertex xt, which is coloured with colour 3, with either 4 or 5 depending on which of these two colours is not used for its neighbour yt. We need not care about zt since all we might create is a longer path in the graph induced by the colour classes of colours c(xt) and c(yt). Finally colour v with 3.
So now all that remains is to check the case when u = 3. Again without loss of generality we suppose that all the lists are equal to or contained in {1, 2, 3}. We choose to colour xi and x2 with 1, x3 and x4 with 2 and x5 and x6 with 3. Then we set the colour of x7 to be either 4 or 5 distinct from the colour of y7 and then we use the remaining colour of these two colours for v. Similarly as before we do not violate the conditions for
a linear colouring this way. This concludes the proof that this configuration is reducible.
□
m
CD
$H
CD
m
u
a
CD U
Lemma 2.6. (Q6) i.e. a 7-vertex adjacent to five 2-vertices where each of them is again adjacent to another 2-vertex and the remaining two neighbours are of degree 3 and both have 2-vertices as the remaining two neighbours is reducible.
Proof. The proof of this lemma is similar to the proof of lemma 2.5 and therefore this proof will be somewhat condensed. Let v, x1,..., x7, y1,... ,y7, z1,..., z7, y'6 ,y'7 and z'6, z'7 be vertices like in the Figure 5. If we remove the star S = v, x1,..., x7 the resulting graph has a linear colouring c by the minimality of G. Now we want to extend this colouring to G.
Let col = {1, 2, 3, 4, 5}. We now set the lists of available colours for xj to be L(xj) = col \ {c(yj), c(zj)} for those xj of degree 2 and L(xj) = col \ {c(yi),c(zi),c(y'i),c(z'i)} for those xi of degree 3.

A
o u ti

0 o
1
CO ^
CO CO
m
CD
$H
CD
m
u
a
CD U fc
Figure 5: Reducible configuration (Q6).
Again we can only contradict the requirements for a linear colouring within the star S and if we can extend the colouring to a proper colouring of S where at most two Xj are coloured the same the result is a linear colouring.
Similarly as in the previous lemma our problem can be now put in terms of finding a matching in a bipartite graph H constructed as follows: In partition A we will have the vertices xi,..., x7 and in partition B the vertices ..., u5, ui,..., u'5. In partition B the indices correspond to the 5 colours we have at our disposal. Any vertex Xj with its list of admissible colours L(xj) is connected to the vertices in B which have indices in L(xj).
This means that the vertices in A are all of degree 6 or 2. If we find a matching in H which covers A this will correspond to a proper colouring of x1,..., x7, where each colour appears at most twice. Again the colour of xj would simply be the index k of the vertex uk or uUk that xj is matched by. If we can then also properly colour v the result will be a linear colouring. Let us show that this is indeed possible.
The condition of Hall's theorem clearly holds for each |S| < 6 since each vertex in A has degree 6 or 2 and only 2 are of degree 2. The only case where we can have a problem is when S = A and the lists are of the form: L(x^) = {1, 2, 3} if xj is a 2-vertex and L(xj) C {1, 2, 3} if xj is a 3-vertex. Let u be the size of the union of all lists u = | U (L(xj))|. Let us now suppose that u > 4 and try to colour v. If any colour does not appear on xi, . . . , x7 we use that colour for v and the proof is complete. So now we suppose that all colours are used on the vertices x1,..., x7. Without loss of generality the colours used on x1,..., x7 are the multiset {1,1, 2, 2, 3, 4, 5}. One of the colours 3, 4 and 5 appears on xt where t ^ {6, 7}. We recolour xt with either 4 or 5 avoiding the colour of yt the neighbour of xt.
When u = 3 we colour the vertices x2,... ,x7 with the colours 1, 2 and 3 without
A
o u ti

0 o
1
CO
£ CO CO
m
CD
$H
CD
m
u
a
CD U
using any of them twice, which is clearly possible. Then we colour x1 with either 4 or 5 depending on its neighbour y1. At last we use the remaining colour for v and the proof is complete.
□
2.2 Initial charge
We assign initial charge to every vertex v and every face f of G as follows:
cho(v) = 3deg(v) - 8 and cho(f ) = 1(f) - 8.
Observe that by Euler's formula the total charge assigned this way is -4. By this choice of initial charge all the faces have nonnegative innitial charge. Since $(#) > 2 only 2-vertices have negative charge.
deg(u)	cho(i')	s{v)
2	-2	
3	1	1/3
4	4	1
5	7	7/5
6	10	5/3
7	13	13/7
> 8	> 16	> 2
Figure 6: This table shows the degree of a vertex, its initial charge and the initial charge divided by the degree.
2.3 Discharging rules
We redistribute the initial charge by the following rules:
•	R\ : Each vertex v of degree at least 3 sends s(v) =	to neighbouring vertices of degree 2.
•	R2 : A vertex v of degree at least 3 adjacent to a vertex u of degree at least 3 sends
deg(^Hd°eg(lt)-i) ^0 everV vertex of degree 2 adjacent to u.
•	R3 : Let v1v2v3v4v5 be a path in G such that deg(v1) = deg(v2) = deg(v4) = 2 and deg(v3) = 7. Now:
—	if deg(v5) > 4 then v4 sends 1/7 to v2;
—	if deg(v5) = 3 then v4 sends 1/21 to v2.
•	R4 : If a 7-vertex has positive charge after applying rules R1, R2 and R3 it sends it to its neighbours of degree 2 distributed equally.
2.4 Final charge
After the discharging rules are applied we will conclude that every face and every vertex has nonnegative charge which will be a contradiction since the total charge is -4. Because a 1-vertex is reducible we only need to take care of 2-vertices since they are the only ones with negative initial charge.
The final charge of vertices of degree at least 3 stays nonnegative since:
i—l
ch(i>) = cho(i') -	') - i (	x-7T»>2(u)(deg(i>) - n2{v))
deg(v)	deg(v)(deg(u) — 1)
, . . ch0(v) . ch0(v) , . . ...
£ ch«(t') - d4r2(t,) - d4i(deg(i,) -Mv))
clip (l')
= ch0 f - -j—T--deg(v) deg(v)
= 0.
o
Let v be a 2-vertex and let x and y be its two neighbours. If both x and y are of degree > 4, then by R\, ch(v) > —2 + 2 ■ 1 = 0. Suppose that deg(x) = 3. Then deg(y) > 5 by (Q3). If deg(y) > 6 then ch(u) > — 2 + | + | = 0. So we may assume that deg(y) = 5. Now by (Q4) we conclude that x has either one neighbour of degree > 6 or two neighbours of degree > 3. In the first case ch(i>) > — 2 + | + -g + >0 and in the second case ch(u) > -2 + | + | + || > 0 by i?i and R2.
Now, we may assume that v has a neighbour of degree 2, say x. Then, y is of degree CSI	> 7 by the reducibility of (Q2). In case deg(y) > 8, then ch(v) > —2 + 2 = 0 by Ri.
So assume that deg(y) = 7. After rule R\ the charge of v is ch(u) = — 2 + y = — I. By (Q5) and (Q6) we know that one of the following cases holds:
(a)	one of the neighbours of y is a >4-vertex;
(b)	three neighbours of y are 3-vertices;
CO
(c)	exactly two neighbours of y are 3-vertices and at least one of them has another >3-vertex
as a neighbour ;
(d)	one vertex z at distance 2 from y is a >4-vertex;
(e)	three vertices u1,u2 and u3 at distance 2 from y are 3-vertices. This means that the final charge of v in these cases is:
W
V«7 —	7 1 6
(а)	ch(i>) = + | > 0 by i?2;
(б)	ch(i-) = -I + 3 • 3L > 0 by i?2;
(c) in this case y has at least tt| = 13 — 5y — 3tt| charge left after rules R\ and R2
U &
-7 + 7 = °;
13
Litre - ims way y senus ax letisi 7
so ch(u) = -h + ^ > 0 by i?4;
while rule i?3 cannot be applied here - this way y sends at least yy^ charge to v and
7-2-5
(d) the common neighbour of z and y sends 1/7 charge to v by R3 and so ch(v) 7 ' 7
(e) the common neighbours of u1 and y, u2 and y and u3 and y send 1/21 charge to v by R3 and so ch(i>) = — 1 + = 0.
CO CD
$H
CD CO
$H
a
CD Jh
This concludes our proof that every vertex has nonnegative charge after the discharging step and so a contradiction arises since the sum of the initial charge is -4. This contradiction establishes the theorem.

References
A
o u

0 o
1
CO ^
CO CO
[1]
[2]
[3]
[4]
[5]
[6]
[7
[9 [10 [11
O. V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211-236.
O. V. Borodin, D. G. Fon-Der Flaass, A. V. Kostochka, A. Raspaud, E. Sopena, Acyclic list 7-coloring of planar graphs, J. Graph Theory 40 (2002) 83-90.
R. Diestel, Graph theory, Springer-Verlag, New York, 1997.
L. Esperet, M. Montassier, A. Raspaud, Linear choosability of graphs, DMTCS Proc. AE 14 (2005) 99-104.
B. Griinbaum, Acyclic colorings of planar graphs, Israel J. Math. 41 (1973) 390-408.
H. Hind, M. Molloy, B. Reed, Coloring a graph frugally, Combinatorica 17 (1997) 469-482.
A. V. Kostochka, Acyclic 6-coloring of planar graphs, Metody Diskret. Anal. 28 (1976) 40-56.
J. Mitchem, Every planar graph has an acyclic 8-coloring, Duke Math. J. 14 (1974) 177-181.
A. Raspaud, W. Wang, Linear coloring of planar graphs with large girth, Discrete Math. 309 (2009) 5678-5686.
P. Wernicke, Uber den kartographischen Vierfarbensatz, Math. Ann. 58 (1904) 413426.
R. Yuster, Linear coloring of graphs, Discrete Math. 185 (1998) 293-297.