IMFM
Institute of Mathematics, Physics and Mechanics JADRANSKA 19, 1000 LJUBLJANA, SLOVENIA
Preprint series Vol. 48 (2010), 1116
ISSN 2232-2094
BROOKS THEOREM FOR DART GRAPHS
Martin Kochol Riste Skrekovski
Ljubljana, March 22, 2010
c^	Brooks Theorem for Dart Graphs
o
o
CSI
I
£
CO CO
Martin KochoF
MU SAV, Stefanikova 49, 814 73 Bratislava 1, Slovakia martin.kochol@mat.savba.sk
Riste Skrekovski
Department of Mathematics, University of Ljubljana, Jadranska 19, 1111 Ljubljana, Slovenia skrekovski@gmail.com
Abstract
The well known Brooks theorem says that each graph G of maximum degree k > 3 is k-colorable unless G = Kk+i- We generalize this theorem by allowing higher degree vertices with prescribed types of neighborhood.
CO
1 Introduction
A k-coloring of a graph is a mapping from the set of vertices to {1,... ,k} such that any two adjacent vertices have different colors. The decision problem whether a given graph G has a k-coloring is a classical NP-complete problem for every fixed k > 3 (see [3, 4]).
By Brooks' Theorem [1], every graph with maximum vertex degree at most k > 3 and without a component isomorphic to Kk+i (a complete graph on k + 1 vertices) has a k-coloring. Furthermore, as follows from [2, 6, 7, 8, 9], there exists a linear time algorithm that finds a k-coloring for such a graph.
Kochol, Lozin, and Randerath [6, Theorem 4.3] proved that if D is a class of graphs in which the neighborhood of each 4-degree vertex induces a graph isomorphic to a disjoint union of an isolated vertex and a path of length 2, then every graph from D is either 3-colorable or has a component isomorphic to K4. Furthermore, there exists a linear time algorithm that finds either a 3-coloring or a component isomorphic to K4 for each graph from D. This generalizes the Brooks theorem for the case k = 3.
The aim of this paper is to generalize the Brooks theorem and the result from [6, Theorem 4.3]. We consider classes of graphs where each vertex of degree at least k + 2 has
a
* Supported in part by grant VEGA 2/0118/10. tSupported in part by ARRS Research Program P1-0297.
o
i-H
o
o u
a strictly prescribed neighborhood, so called "(k, s)-dart graphs", defined in the following section. Our main result, Theorem 1, is that if G is a (k, s)-dart graph, k > max{3,s}, and s > 2, then G is (k + 1)-colorable if and only if it has no component isomorphic to Kk+2. Furthermore, if G is (k + 1)-colorable, then a (k + 1)-coloring of G can be constructed in a linear time. We also show that if s > k > 3, then it is an NP-complete problem to decide whether a (k, s)-dart graph is (k + 1)-colorable (see Theorem 2).
2 Definitions
vO
^ &
O
I
CO
£ CO CO
In this paper we consider simple graphs, i.e., without multiple edges and loops. If G is a graph, then V(G) and E(G) denote the vertex and the edge sets of G, respectively.
Let G be a graph and x, y two vertices of G. Then G+xy denotes the graph constructed from G by adding an edge xy. Since we consider simple graphs, G + xy = G if x,y are adjacent in G. For a vertex v of G, let dG(v) denote the degree of v in G. Let H, G be two graphs such that H is not a subgraph of G. Then we use to say that G is a H-free graph.
A (k, s)-diamond is a join of a clique of size k > 1 and an independent set of size s > 1. These graphs are also known as split graphs. In a (k, s)-diamond D, vertices that belong to the independent set are called pick vertices, and the remaining (i.e. those in the k-clique) are called central vertices. Denote by C(D) and P(D) the sets of central vertices and pick vertices of D, respectively. An example of a (4, 2)-diamond D with C(D) = {c\,... ,c4} and P(D) = {pi,p2} is in Figure 1.
c
c
c
c
CO CD
CD CO
u
a
CD U
Figure 1: A (4, 2)-diamond.
Note that a (k, 1)-diamond is isomorphic to Kk+1; in this case the unique pick vertex does not distinguish from the central vertices but in such a situation this is irrelevant for
Definition 1 A graph G is a (k, s)-dart if each vertex of G of degree > k + 2 is a central vertex of some (k,i)-diamond D as an induced subgraph of G with i < s, for which
(a)	dD(x) > dG(x) — 1 for each x E V(D);
(b)	no two vertices of C(D) have a common neighbor in G - D.
o
CSI
Every graph of maximum degree < k + 1 is a (k, 1)-dart graph since in the above definition, we only prescribe the structure on the neighborhood of vertices of higher degree. Also, every (k, s^-dart is a (k, s2)-dart if s1 < s2.
Note that the assumption that x is of degree > k + 2 implies that i > 2. In a (k, s)-dart graph G, every vertex of degree at least k + 2 belongs to an induced (k, i)-diamond with 2 < i < s. Denote by D(G) the set of all induced maximal (k, i)-diamonds of G with i > 2. Observe that we do not require that a diamond of D(G) must contain a vertex of degree k + 2 or more, just to satisfy conditions (a) and (b) of Definition 1.
We say that a vertex of a dart G is central if it is a central vertex of a diamond of D(G). Similarly define a pick vertex of G. Denote the sets of central vertices and pick vertices by C(G) and P(G), respectively.
Let G be a (k, s)-dart and D E D(G). Then, each central vertex x E C(D) is adjacent to at most one vertex v' from G — D. In this case, v' is called isolated neighbor of v. The set of all isolated neighbors of the central vertices of D is denoted by I(D). Possibility I(D) = 0 is not excluded.
We remark that the following observations for a (k, s)-dart G hold:
vO

(1)	A central vertex v of a (k, s)-dart G is not necessarily of degree at least k + 2. This happens only if v is a central vertex of a (k, 2)-diamond D E D(G) and it has no neighbor in G — D. Then, v is of degree k + 1.
(N
(2)	If Kk+2 is a subgraph of a (k, s)-dart G, then it must be a component of G. Thus a copy of Kk+2 in G is disjoint from diamonds of D(G).
CO
(3)	No two pick vertices of the same diamond from D(G) are adjacent.
3 Properties of dart graphs
CO
m
CD
$H
The following lemma is an easy observation.
Lemma 1 Let G be a (k, s)-dart graph and D E D(G). Let X be a proper (k + 1)-coloring of G — C(D) such that all pick vertices P(D) are assigned the same color a. Then, X can be extended to G unless every central vertex of D has an isolated neighbor and X assigns the same color c = a to all vertices of I(D).
Proof: Let L(v) C {1,... ,k + 1} be the set of available colors for a central vertex v E V(G) regarding X. Notice that k > |L(v)| > k — 1. And, |L(v)| = k — 1 if and only
if v has an isolated neighbor v' and X(v') = a. Thus, each central vertex of D has an isolated neighbor and all vertices of I(D) are assigned a same color c = a, if and only if the unions of all L(v)'s is of size k — 1. Now the proof follows by Hall's theorem.
U
a
CD U
Next lemma assures that diamonds in a dart graph are vertex disjoint:
u
vD
Lemma 2 Let G be a (k, s)-dart graph with k > 3. Then
(a)	V(Di) fi V(D2) = 0, for every two distinct diamonds Di,D2 E D(G).
(b)	C(G) f P(G) = 0; in particular each pick vertex is of degree k or k + 1.
(N
Proof: We prove (a). Suppose that v is a vertex of two distinct diamonds Di,D2 E D(G).
Assume that v E C(Di) f C(D2). If C(Di) = C(D2), then by Definition 1(b) we obtain that P(Di) = P(D2), whence Di = D2. Thus C(Di) = C(D2).
Suppose first \C(Di) f C(D2)| = 1, i.e., C(Di) f C(D2) = {v}. Then by Definition 1, either k — 2 or k — 1 vertices of C(D2) (resp. C(Di)) are pick vertices of Di (resp. D2). But then for k > 4, we obtain also two adjacent pick vertices of Di (resp. D2), a contradiction to (3). So we may assume that k = 3, C(Di) = {ui,wi,v}, C(D2) = {u2,w2,v}, and ui (resp. u2) are pick vertices of D2 (resp. Di). By (3), wi (resp. w2) is not a pick vertex of D2 (resp. Di). Then wi E I(D2) (resp. w2 E I(Di)) is a common neighbor of v,u2 E C(D2) (resp. v,ui E C(Di)), a contradiction with Definition 1(b).
Suppose now \C(Di) f C(D2)\ > 2. Then each vertex u E C(Di) \C(D2) is a neighbor of at least two vertices from C(D2), whence by Definition 1(b), u E P(D2) and thus C(Di) \ C(D2) C P(D2). Similarly C(D2) \ C(Di) C P(Di). Thus the subgraph of G induced by C(Di) U C(D2) is a clique, whence \C(Di) U C(D2)\ = k +1, and so \C(Di) f C(D2)\ = k — 1. By assumptions, Di is a (k, si)-diamond, s > si > 2. Thus there exists xi E P(Di)\C(D2). By (3), we infer that xi E I(D2) but then it is a common neighbor of at least two vertices from C(D2), a contradiction with Definition 1(b).
By the above two paragraphs, we can assume that C(Di) f C(D2) = 0. If v E V(Di) f P(D2), then dD2(v) + 1 < dG(v), a contradiction with Definition 1(a). Similarly ^ if v E V(D2) f P(Di). This proves claim (a). Claim (b) is an easy consequence of (a).
£ "
Next lemmas assures that removing small vertices or diamonds in dart graphs we 1—1 preserve the class of dart graphs.
Lemma 3 Let G be a (k, s)-dart graph with k > 3. Then
(a)	if v is a vertex of degree < k, then G' = G — v is a (k, s)-dart (graph,
(b)	if D E D(G), then G' = G — D is a (k, s)-dart graph.
Moreover, in both cases, D(G') can be determined from D(G) in a constant time.
Proof: We first show that in both cases G' is a (k, s)-dart graph. Suppose that u' is an arbitrary vertex of degree > k + 2 in G'. Then, it is also of degree > k + 2 in G, and hence it belongs to a (k, i)-diamond D' E D(G) with 2 < i < s. In case (b), diamonds D and D' are disjoint, by Lemma 2, and hence D' is an induced (k, s)-diamond in G'. Consider now case (a). If D' is an induced subgraph of G', then we are done. Otherwise, v E V(D') is a pick vertex of D'. Since u' is of degree > k + 2 in G', it follows that i > 3, and hence D' — v is a (k, i — 1)-diamond in G'.
o
o
i-H
o
c^
c^ c^
o
I
CSI 00 CSI CSI
Regarding D(G') and D(G), in case (b), Lemma 2 assures that D(G) consists of D and D(G'). In case (a), D(G) may change only if v is a pick vertex of some (k, s)-diamond D' of G. So, in this case, D(G) is either D(G') or (D(G') \ {D' — v)) U {D'}.
In the next few lemmas, we study properties of a graph G' obtained from G be applying some local changes.
Jh
Lemma 4 Let G be a (k,s)-dart graph with k > 3 and let a1,a2 be two central vertices of a diamond D E D(G). Suppose that x1 and x2 are the isolated neighbors of a1 and a2, respectively. Then, each (k + 1)-coloring X* of G* := G — x1a1 — x2a2 + x1x2 can be VO modified into a (k + 1)-coloring of G in a constant time.
Proof: Clearly X*(a1) = X*(a2) and X*(x1) = X*(x2). By Definition 1, a1 and x2 are non-adjacent, and similarly a2 and x1 are non-adjacent. Notice that X* is not a coloring of G if and only if X*(a1) = X*(x1) or X*(a2) = X*(x2). But in that case, we can simply interchange the colors of a1 and a2, and obtain a proper (k + 1)-coloring of G.
Lemma 5 Let G be a Kk+2-free (k,s)-dart graph with k > 3 and D E D(G). Let a1,a2 be two central vertices of D and let x1,x2 be their isolated neighbors, respectively. Then the graph G' = G — x1a1 — x2a2 + x1 x2 is a Kk+2-free (graph unless x1,x2 are pick vertices of a diamond of D(G).
Proof: Suppose that G' contains a copy H of Kk+2. Then, x1,x2 are vertices of H, thus cannot be adjacent in G and there is a set S of k common neighbors of x1 and x2 in G, which induce a clique. Notice that |S| = k and dc(x1), dG(x2) > k + 1.
CO Suppose that dG(x1) > k + 2. Then, x1 is a central vertex of some diamond D' E D(G), whence by Definition 1(b), S C V(D') and clearly, IS fl C(D')| > k — 1 > 2. Then x2 has at least 2 neighbors in C(D'), whence x2 belongs to D', and so it is adjacent with x1 in G, a contradiction.
Thus, by pervious paragraph, we may assume that d(x1) = k +1, and analogously d(x2) = k + 1. Then x1, x2 and S belong to a diamond of D' E D(G) in which x1,x2 E
S P(D') and S = C(D').
• i
Lemma 6 Let G be a (k,s)-dart graph D E D(G). Let a1 ,a2 be two central vertices of D and let x1}x2 be their isolated neighbors, respectively. Then the graph G' = G — x1a1 — a2x2 + x1x2 is a (k,s)-dart graph unless one of the following conditions occurs:
(H
(a)	x1,x2 are pick vertices of the same diamond of D(G);
Jh
(b)	there exists a diamond D' E D(G) and i E {1, 2} such that xi E C(D') and x3-i is an isolated neighbor of a central vertex from D', vhich is distinct from xi.
o
CSI
Proof: Suppose that G' is not a (k, s)-dart graph. First notice that each vertex preserve its degree from G except a1 ,a2, which belong to D and it is a diamond in G' as well. If there is some D' E D(G) that is not induced diamond of G', then x1 and x2 must be pick vertices of D', which is the excluded case (a). Next observe that each diamond of D(G) satisfies Definition 1(a) in G'. Finally, if Definition 1(b) is not satisfied for some D' E D(G) in G', then there are two central vertices u and v with a common neighbor w outside D'. Notice that x1x2 is one of the edges uw or vw. Then without loss of generality, we may assume that x1 is a central vertex in D' and x2 is an isolated neighbor of a central vertex of D' distinct from x1.
Notice that in the exceptional case (a) of the above lemma, G' may still be a dart graph, when D is a (k, 2)-diamond with no isolated verices. Then, D becomes a copy of ,_! Kk+2 in G'.
§ 4 An extension of Brooks theorem
For a diamond D E D(G), a vertex of I(D) could be a central or pick vertex of another diamond of D(G). Denote by Ic(D) and Ip(D) the subset of all such vertices of I(D), respectively. By Lemma 2(b), sets Ic(D) and Ip(D) are disjoint. Finally, let Is(D) be the vertices of I(D) that are neither in Ic(D), nor in Ip(D).
C^
Lemma 7 Let G be a Kk+2-free (k, s)-dart graph with given D(G) = 0 and k > max{3, s} and s > 2. Then, in a constant time we can construct a Kk+2-free (k,s)-dart graph G* together vnth D(G*) such that
CSI
£
CO CO
(a)	\E(G*)| < \E(G)|;
(b)	From any (k + 1)-coloring X of G* one can construct a (k + 1)-coloring of G in a constant time.
Proof: In the construction of G* we use a bounded number of vertex/edge additions and deletions. Similarly, we obtain D(G*) from D(G) in a finite number of steps. This will preserve that constructions are completed in a constant time. In the sequel consider ~ the following cases:
m
Case 1. There exists v E V(G) of degree < k. Then v is not a central vertex. Thus, by Lemma 3(a), G* := G — v is a (k, s)-dart graph with \E(G*)\ < \E(G)\. By the same lemma, one can construct D(G*) from D(G) in a constant time. Obviously, G* is a Kk+2-free graph. A coloring of G* can be easily extended to a coloring of G by assigning to v a color that miss in its neighborhood.
Case 2. There exists v E C(D), D E D(G), having no isolated neighbor. By Lemma 3(b), G* := G — D is a (k, s)-dart graph and D(G*) can be constructed from D(G) in a constant time. Obviously, G* is a Kk+2-free graph and \E(G*)\ < \E(G)\. Let
CD W
X* be a (k + 1)-coloring of G*. Since each pick vertex of D has at most one neighbor outside D and since p(D)| < k + 1, it follows that there exists a color that we can assign to all pick vertices. Since v has no isolated neighbor, we can apply Lemma 1 to extend X* to the central vertices of D.
Case 3. There exists D E D(G), such that Ic(D) U Is(D) = 0, or some two vertices of
o
CSI
CSI
Ip(D) do not belong to the same D' E D(G). We can assume that Case 2 does not hold, whence (D)| + |Ip(D)| + |Is(D)| = k. Let x1,x2 E I(D) be two distinct vertices. And, let ai E C(D) be the neighbor of xi for i = 1, 2.
Now, consider the graph G* = G — x1a1 — x2a2 + x1x2. If none of the exceptions of Lemmas 5 or 6 holds, then G* is a Kfc+2-free (k, s)-dart graph, and by Lemma 4, we can modify any coloring of G* to a proper coloring of G in a constant time. Moreover, E(G*)| < E(G)| and D(G) can be determined in a constant time from D(G*).
Assume that for each pair x1,x2 E I(D), some of the exeptions of Lemmas 5 or 6 is satisfied. This implies immediately that |Ic(D)| < 1 and |Is(D)| < 1.
Thus |Ip(D)| > 1 (because k > 3). Then x1 E Is(D) U Ic(D) and x2 E Ip(D) do not satisfy exeptions of Lemmas 5 or 6, whence Is(D) U Ic(D) = 0. Thus all vertices of I(D) must be pick vertices of one diamond of D(G). This contradicts the assumptions of Case 3.
Case 4. None of Cases 1.-3. occurs. Thus, by Case 3., for each D E D(G), Ic(D) U Is(D) = 0, and all vertices of Ip(D) belongs to a same (k, k)-diamond D' E D(G). We denote D' by p(D). Furthermore, observe that there exists a perfect matching between C(D) and P(p(D)).
Case 4.1. There exists D E D(G), such that p2(D) = D. Then vertices of D and p(D) induce a component G' of G. Let G* := G — G'. Obviously, G* is a (k, k)-dart graph, E(G*)| < |E(G)| and D(G*) = D(G) \ {D,p(D)}. Moreover, we can construct a (k + 1)-coloring of G' in a constant time: just color all vertices of P(D) and P(p(D)) by the color k + 1, and assign colors 1,... ,k to the vertices of C(D) and C(p(D)).
HH
Case 4.2. For each D E D(G), p2(D) = D. By the assumptions of lemma, there exists D E D(G) = 0. Let G* be the graph, we obtain by removing the vertices of p(D) and inserting a perfect matching between C(D) and P(p2(D)). Obviously G* is a (k, k)-dart graph with less edges than G and D(G*) = D(G) \ {p(D)}. Let X* be a (k + 1)-coloring of G*. Then X* assigns the same color c to all vertices of P(p2(D)). Assign c also to all vertices of P(p(D)) and to each of the vertices of C(p(D)) an unique color from {1, . . . , k + 1} \ {c}. This gives a required coloring of G, completing the proof.
i
CSI 00
m
CD
CD
Now we are ready to prove the main result.
Theorem 1 Let G be a (k,s)-dart graph with k > max{3, s} and s > 2. Then G is (k + 1)-colorable if and only if it has no component isomorphic to Kk+2. Furthermore, if G is (k + 1)-colorable, then a (k + 1)-coloring of G can be constructed in a linear time.
Jh
o
i-H
o
o u
VD
Proof: The necessity of the first part of the theorem is trivial. To see the sufficiency, observe that a (k, s)-dart graph is Kk+2-free if and only if it has no component isomorphic to Kk+2. The same is true if G is a graph with vertex degree at most k + 1. Therefore, the sufficiency follows from Lemma 7 and Brooks' Theorem [1].
We can check whether a dart graph G is Kk+2-free in linear time. Analogously, we can find the set D(G) in linear time. Consequently, by means of Lemma 7 we can create in linear time a Kk+2-free graph G' without vertices of degree more than k +1 such that any (k + 1)-coloring of G' can be transformed into a (k + 1)-coloring of G in linear time. By [7] (see also [9, 6]), a (k + 1)-coloring of G' can be found in linear time, which proves the statement.
o
I
CO
£ CO CO
5 NP-Completeness
In this section we show that Theorem 1 cannot be extended for (k, s)-dart graphs where s> k > 2 unless P = NP.
We need some more notation. Take n vertex disjoint copies of (k,k + 1)-diamonds D1,..., Dn, k,n > 2. For i = 1,... ,n, denote by viy1,..., vi>k and uit1,..., uitk+1 the central and pick vertices of Di, respectively. Add nk new edges vitjui+1>j, i = 1... ,n, j = 1,... ,k (considering the sum i + 1 mod n). Then the resulting graph is called a (n, k + 1)-bracelet and vertices u1,k+1,..., un,k+1 are called its connectors. An example of a (4, 3)-bracelet with connectors u1 , ..., u4,3 is in Figure 2.
u
1,3
u,
2,3
u
3,3
u
4,3
CO CD
Jh
CD CO
u
a
CD U
Figure 2: A (3, 4)-bracelet. We study complexity of the following problem.
DART-(k,s)-(k + 1)-COL
Instance: A (k, s)-dart graph G. Question: Is G k + 1-colorable?
Theorem 2 The problem DART-(k, s)-(k + 1)-COL, k > 3, is
(a)	NP-complete for s > k,
(b)	solvable in linear time for s < k.
o
i-h
o
o u
Proof: Claim (b) holds true by Theorem 1. We prove (a). Let G be a graph. Replace each vertex v of G of degree > 2 by a (dG(v),k + 1)-bracelet Hv. Let Hv be an isolated vertex if dG(v) = 1. Each edge uv of G replace by an edge joining a connector of Hv with a connector of Hu so that each connector is attached to at most one new edge. Denote the resulting graph by G'. Clearly, G' is a (k, k + 1)-dart graph. By any (k + 1)-coloring of Hv, v E V(G), all connectors of Hv must be colored by the same color. Hence G' is (k + 1)-colorable if and only if G is so. Thus the problem from item (a) can be polynomially reduced to the problem of (k + 1)-coloring. This problem is NP-complete for every fixed k > 2 by Garey and Johnson [3, GT4].
We have proved item (a) also for k = 2. Let us note that item (b) for this case is a consequence of [6, Theorem 4.3].
0 o
1
CO
£ CO CO
m
cd
$h
CD
m
u
a
CD U
References
[1]	R. L. Brooks, On coloring the nodes of a network, Proc. Cambrigde Phil. Soc. 37 (1941) 194-197.
[2]	V. Bryant, A characterisation of some 2-connected graphs and a comment on an algorithmic proof of Brooks' theorem, Discrete Math. 158 (1996) 279-281.
[3]	M. R. Garey and D. S. Johnson, Computers and Intractability, W.H. Freeman, San Francisco, 1979.
[4]	M. R. Garey, D. S. Johnson, and L. Stockmeyer, Some simplified NP-complete graph problems, Theor. Comput. Sci. 1 (1976), 237-267.
[5]	R. Diestel, Graph Theory, 3rd ed., Springer, Heidelberg, 2005.
[6]	M. Kochol, V. Lozin, and B. Randerath, The 3-colorability problem on graphs with maximum degree four, SIAM J. Comput. 32 (2003) 1128-1139.
[7]	L. Lovasz, Three short proofs in graph theory, J. Combin. Theory Ser. B 19 (1975) 269-271.
[8]	B. Randerath and I. Schiermeyer, A note on Brooks theorem for triangle-free graphs, Australasian J. Combin. 26 (2002), 3-10.
[9]	S. Skulrattanakulchai, A-list vertex coloring in linear time, in Algorithm Theory -SWAT 2002, M. Penttonen and E. Meineche Schmidt, eds., Lecture Notes in Comput. Sci., Vol. 2368, Springer-Verlag, New York, 2003, 240-248.