9512.net

# X. Relaxed coloring of a graph

Relaxed coloring of a graph
Walter Deuber and Xuding Zhu Sonderforschungsbereich 343 Diskrete Strukturen in der Mathematik Universitat Bielefeld, Germany
Abstract
Let P be a hereditary family of graphs. A relaxed coloring of a graph G = (V; E ) with respect to P is an assignment of colors to vertices of G so that each color class induces a graph which is the disjoint union of members of P . The P -chromatic number P (G) of G is the minimum number of colors in a relaxed coloring of G with respect to P . We study the relation between the girth and the P -chromatic number of a graph, and the P -chromatic number of product graphs. Our results generalize some results of M. L. Weaver and D. B. West in 10], and answer some questions in that paper.

1

1 Introduction
In the last decade, various variations of graph coloring have been studied, 5, 9, 10]. Some of these generalized colorings have requirements stronger than that of the ordinary coloring. In such colorings, the pair of colors assigned to adjacent vertices are not only required to be di erent, they must also forbidden some patterns. Such colorings can be de ned as a homomorphism of a graph G to another graph H , and are usually referred to as H -coloring problems, 1, 2, 5, 6]. Other generalizations have requirements weaker than that of the ordinary coloring. In other words, adjacent vertices are allowed to be colored with the same color. However there are some restrictions on the subgraphs induced by the color classes. Such coloring are called relaxed colorings 10] or improper colorings 9]. Since this is the context of the present paper, we give a de nition. Let P be a so called hereditary family of graphs, which is closed under taking subgraphs. A P -k-coloring of a graph G = (V; E ) partitions V into k blocks such that the subgraphs induced by the blocks are disjoint unions of members of P . The P -chromatic number P (G) of G is the minimum number k such that G is P -k-colorable. If P is the family of empty graphs, then P (G) = (G). When P is the family of forests, then P (G) is also called the vertex arboricity of G. For a survey of results concerning P -kcoloring of graphs, readers are referred to 9] and 10]. Following notions in 10], for a given family H of graphs we denote by H the family consisting of disjoint unions of subgraphs of members of H, and denote by H0 the family of graphs with no subgraph belonging to H. We call the parameters H (G) and H0 (G) the H-restricted and the Hforbidden chromatic numbers of G, respectively. When H = fH g consists of a single graph, then we use H in place of fH g. We shall study only forbidden and restricted chromatic numbers. First we discuss the existence of graphs with large girths and large restricted and forbidden chromatic numbers. The corresponding results generalize some results of M. L. Weaver and D. B. West 10]. We then consider the restricted and forbidden chromatic numbers of the Cartesian product G2G0 and the lexicographic product G G0] of graphs. For the Cartesian product, we prove in particular that the product of more than three odd cycles has path restricted chromatic number 3. In other words, if 2

the Cartesian product of more than three odd cycles are partitioned into two blocks, then at least one of the blocks induce a cycle or a star K ; . This solves the problems posed in 10]. For lexicographic product, we will give an upper bound of the restricted (resp. forbidden) chromatic number of G G0] in terms of the star-chromatic number of G (see de nition in Section 4) and the restricted (resp. forbidden) chromatic number of G0.
1 3

2 Girths versus restricted and forbidden chromatic numbers
A classical result of Erdos 3] says that there are graphs G of arbitrary large girth and arbitrary large chromatic number. For a family H of graphs, we denote by H the family consisting of disjoint unions of subgraphs of members of H, and H0 the family of graphs with no subgraph belonging to H. We call H (G) the H-restricted chromatic number of G and H0 (G) the H-forbidden chromatic number of G. M. L. Weaver and D. B. West 10] considered the problem whether graphs G of large girths have H-restricted chromatic number or H-forbidden chromatic number smaller than its ordinary chromatic number (G). They proved constructively the following theorem 10]:

Theorem 1 If H is any nite family of bipartite graphs, then there is a triangle free H-restricted k-critical graph Gk with ordinary chromatic number k. If H contains any complete bipartite graph, then the same statement holds
for the parameter H0 (G).

Here a graph G is said to be H-restricted k-critical if H (G) = k and H (G0 ) < k for any proper subgraph G0 of G. Obviously any graph G with H (G) = k contains a subgraph which is H-restricted critical. We now use probabilistic method to prove the following result:
there is a graph G of girth at least g for which H (G) = (G) = k.
1 2 1 2

Theorem 2 If H is any nite family of graphs, then for any integers g; k,

Proof. Let V ; V ; ; Vk be disjoint n-sets. Let F be the complete k-partite graph with vertex set V = V V Vk , and (x; y) 2 E (G) if and only
3

if x 2 Vi ; y 2 Vj and i 6= j . Then F has k n edges. Let G be the set of all subgraphs G of F with m = b k n c edges, where 0 < < 1=4g. Then ) jGj = (2mn2 . In the following, n is assumed to be su ciently large. We consider G as a propability space in which each member occurs with the same propability 1=jGj. First we show that most graphs G 2 G do not contain too many short cycles. For a xed integer `, since there are kn `` ways of choosing a cycle ` )2 C` with V (C` ) V , and a cycle C` is contained in either 0 or (2mn?`?` of the graphs belonging to G , the expected number of cycles C` of length ` in a graph G 2 G is at most
2 2 1+

k

2

!

2

k

`! N` = kn 2` `
)2 ) Since (2mn `?` (2mn2 ?
k k

!

k
2

n ?` m?`
2 2

!

k

2

n m

2

!?

1

:

?

1

< m`( k n )?` , we obtain
2 2 (1

Therefore

N` < (kn) m` (qn )?` < (kn)` n?` 2`
g? X `
=3 1

`

?

)

= k ` n` :

N` < n? = ng :
2 1 2

Let G be the set of all graphs G 2 G with at most dng e cycles of length less than g. Then the above calculation shows that jG j (1 ? n? = )jGj. We now show that most of graphs G 2 G have the property that if we remove a set E of at most ng edges, then the resulting graph G0 has Hrestricted chromatic number H (G) = k. Since each graph G 2 G is a (G) k. Therefore we only need to show k-partite graph, so H (G) that G ? E is not H -(k ? 1)-colorable for most graphs G 2 G . Suppose G 2 G and that there is a set E of at most ng edges of G such that G ? E is H -(k ? 1)-colorable. Let : V (G) ! f1; 2; ; k ? 1g be
1 0 0 0 0

4

a H -(k ? 1)-coloring of G ? E . Then one of the k ? 1 color classes, say ? (1), conatins at least kn vertices. Therefore there are Vi ; Vj (i 6= j ) such k? that j ? (1) \ Vij kn2 and j ? (1) \ Vj j kn2 . Let Wi Vi \ ? (1); Wj Vj \ ? (1) be subsets of Vi \ ? (1) and Vj \ ? (1) respectively such that jWij = jWj j = d kn2 e. Let p be the number of vertices in a largest connected graph in H (recall that H is a nite family of nite graphs, so there is a largest connected graph in H). Let G(Wi ; Wj ) be the subgraph of G induced by Wi Wj . Then G(Wi ; Wj ) ? E contains no connected component of size greater than p, because Wi Wj is monochromatic. As n is very large (so that kn2 is much larger than p), there are subsets Wi0 Wi and Wj0 Wj with jWi0j = jWj0j = n2 such that no k vertex of Wi0 is connected to a vertex of Wj0 in G ? E . Therefore there are at most ng edges of G between vertices of Wi0 and Wj0. For an integer s ng , denote by M (s) the expected number (in a graph G 2 G ) of pairs Wi Vi ; Wj Vj such that i 6= j , and jWij = jWj j = d n2 e, k and there are exactly s edges connecting Wi and Wj . Then
0 1 1 1 1 1 1 1 1 0 3 0 3

M (s) = k d n e n 2 k2
3

!

!

2

d n2 e k
3

2

!

k
2

s

n ? d n2 e k m?s
2 3

2

!

k

2

n m

2

!?

1

:

?d Replacing (2)n2m?s3 2 e2 by (2)n2 ?d 3 2 e2 and applying the inequality m a?x a ? < e?bx=a, we obtain b b
k n k k n k
1

2 2n M (s) < k (ek) 3 2 3k 2
n k

!

2

s

2

e?n1+ = k2 < n se? 3 2 n1+ :
3 2

k

1

Hence
2

X

s<n

g

M (s) < exp(?n
0

1+

=

2

+ 3ng logn) < e?n :
0 0 2

Let G be the set of graphs G 2 G with the property G ? E is not H (k?1)-colorable for any E E (G) with jE j ng . Then jG j (1?e?n )jGj. Therefore G \ G 6= . Let G 2 G \ G . Since G 2 G , there is a set E of ng edges such that G ? E has girth at least g. On the other hand G 2 G implies that G ? E is not H -(k ? 1)-colorable. This completes the proof of Theorem 2.
1 2 1 2 1 0 0 2 0

5

For H-forbidden chromatic numbers, it was mentioned in 10] that there exist triangle-free graphs with C -forbidden chromatic number k (observed by B. Bollobas by probabilistic methods). We now consider the problem for which graphs H , there exist graphs with girth at least g and H -forbidden chromatic number at least k. Obviously if H has girth less than g then the H -forbidden chromatic number of any graph G with girth g is 1. We shall prove that if H has girth at least g, then there exist graphs with arbitrary large H -forbidden chromatic number and with girth at least g.
5

Theorem 3 Suppose H is a graph with girth at least g. Then for any integer
k, there exits a graph G with
H 0 (G)

k and with girth at least g.

3] and Lovasz 7] there exist an n-uniform hypergraph F of girth at least g and chromatic number at least k. Let G be a graph obtained from F by (arbitrarily) embedding a copy of H into each hyperedge of F . Then G has girth at least g. Indeed, if C is a cycle of G of length less than g, then C is not contained in any copy of H , because H has girth at least g. Thus C has non-empty intersection with at least two hyperedges of F . But then all those hyperedges which intersect C must contain a cycle of F , which contradicts the assumption that F has girth at least g. Now any (k ? 1)-coloring of the vertices of G can be regarded as a (k ? 1)-coloring of F and hence contains a monochromatic hyperedge. This hyperedge induces a copy of H . Therefore the H -forbidden chromatic number of G is at lest k.

Proof. Suppose jV (H )j = n. By a classical result of Erdos and A. Hajnal

3 Cartesian product
The Cartesian product G2H of two graphs G and H has vertex set V (G2H ) = V (G) V (H ), and (g; h) is adjacent to (g0; h0) if and only if either g = g0 and (h; h0) 2 E (H ) or (g; g0) 2 E (G) and h = h0. It was proved in 10] that for any hereditary family P , maxf P (G); P (H )g P (G2H ) minfmaxf P (G); (H )g; maxf (G); P (H )gg: As a corrollary, the Cartesian product G of odd cycles have P (G) 3 for any hereditary family P . M. L. Weaver and D. B. West then asked the 6

question whether P (G) 2 in case P is a path of certain length. One of their result implies that if P is the path of length k, i.e., with k-edges, and G is the product of more than k odd cycles, then P (G) = 3. On the other hand, if G is the product of two odd cycles of length at least 5, then P (G) = 2 if P is a path of length 2. They then asked a sequence of four questions about the relation between the number of odd cycles in the product G and the length of the path P so that P (G) = 2. Our next result shows that if G is the product of more than three odd cycles then the length of the path is irrelevant.
Then

Theorem 4 Suppose G is the Cartesian product of at least four odd cycles.
P

(G) = 3 for any path P .

Proof. We only need to consider the case that G is the product of exactly
1 2 3 4

four odd cycles. Suppose G = C 2C 2C 2C , where Ci is an odd cycle of length 2ki + 1. Suppose the vertices of Ci are numbers from 0 to 2ki and edges are (i; i + 1); i = 0; 1; ; 2ki ? 1 and (0; 2ki ). Then the vertices of G are (x ; x ; x ; x ) where 0 xi 2ki . Let c : V (G) ! fa; bg be a two coloring of G. We shall show that either there is a monochromatic cycle, or a monochromatic star K ; . First we consider the restriction of c to the subset f(0; 0; 0; x ) : 0 x 2k g. Since this set induce an odd cycle, there is a monochromatic edge. Without loss of generality, we assume that c(0; 0; 0; 0) = c(0; 0; 0; 1) = a. Next we consider the restriction of c to the subset f(0; 0; x ; 0); (0; 0; x ; 1) : 0 x 2k g. We claim that there is an index j such that either (0; 0; j; 0); (0; 0; j; 1); (0; 0; j + 1; 0) are monochromatic, or (0; 0; j; 0); (0; 0; j; 1); (0; 0; j + 1; 0) are monochromatic. (Here the additions are carried out modulo 2k + 1). If one of (0; 0; 1; 0) and (0; 0; 1; 1) is colored a, then we are done. Otherwise both (0; 0; 1; 0) and (0; 0; 1; 1) are colored b. If one of (0; 0; 2; 0) and (0; 0; 2; 1) is colored b, again we are done. Repeating this argument we see that the claim is true unless (0; 0; j; 0) and (0; 0; j; 1) are both colored a when j is even and both are colored b when j is odd. But then (0; 0; 0; 0); (0; 0; 0; 1); (0; 0; 2k ; 0) are monochromatic, and the claim is also true. Thus without loss of generality, we assume that c(0; 0; 1; 0) = c(0; 0; 0; 0) = c(0; 0; 0; 1) = a.
1 2 3 4 1 3 4 4 4 3 3 3 3 3 3

7

Now we consider the subset f(0; x ; 1; 0); (0; x ; 0; 0); (0; x ; 0; 1) : 0 x 2k g. With an argument similar to that in the previous paragraph, we can show that either there is a monochromatic star K ; , or there is an index j such that (0; j; 1; 0); (0; j; 0; 0); (0; j; 0; 1); (0; j + 1; 1; 0) are monochromatic, or (0; j; 1; 0); (0; j; 0; 0); (0; j; 0; 1); (0; j + 1; 0; 1) are monochromatic. If there is a monochromatic star K ; then the theorem is proved. Thus we assume, without loss of generality, that c(0; 0; 1; 0) = c(0; 0; 0; 0) = c(0; 0; 0; 1) = c(0; 1; 1; 0) = a. We consider the cube formed by the vertices S = f(0; x ; x ; x ) : 0 xi 1g, which is depicted in Figure 1(a). By our assumption the four vertices (0; 0; 1; 0); (0; 0; 0; 0); (0; 0; 0; 1); (0; 1; 1; 0) are colored a. In order to avoid a monochromatic K ; or a monochromatic cycle, there are only two ways to color the remaining four vertices, as depicted in Figure 1(b) and 1(c).
2 2 2 2 2 1 3 1 3 0 2 3 4 1 3

0110

0111

a

b

a b

a

0010

0011

a 0101 b a

b b a Fig. 1(b)

a b a

0100 0000 Fig. 1(a) 0001

b a

Fig. 1(c)

We consider two cases. Case 1 The cube S = f(0; x ; x ; x ) : 0 xi 1g is colored as in Figure 1(b). Consider the possible coloring of the cubes Sj = f(j; x ; x ; x ) : 0 xi 1g, 1 j 2k . If for each j , the coloring of Sj is obtained from the coloring of Sj? by ipping the colors of the corresponding vertices, then corresponding vertices of S k1 and S would have the same color, and hence we obtain a monochromatic cycle and the theorem is true in this case. Thus without loss of generality we assume that the coloring of S is not obtained from the coloring of S by ipping the colors of the corresponding vertices. By symmetry, we can assume that c(1; 1; 1; 0) = a. Then the
0 2 3 4 2 3 4 1 1 2 0 1 0

8

remaining vertices of S are forced to be colored as in Figure 2 in order to avoid a monochromatic K ; or a monochromatic cycle, where the numbers beside the vertices indicate the forcing steps, i.e., rst consider vertex with number 1, then vertex with number 2, and so on. The uncolored vertices in Figure 2 can not be colored without creating a monochromatic K ; or a monochromatic cycle.
1 1 3 1 3

a b 2

a 1 b 6 b 3 7 5 a b 4 b

b a

a

a b

b

b Fig. 2

Fig. 3

Case 2 The cube S is colored as in Figure 1(c). Again we consider the possible coloring of the cubes Sj = f(j; x ; x ; x ) : 0 xi 1g, 1
0 2 3 4 1 1 1 3 0

j 2k . There are essentially two possible coloring of S which will avoid a monochromatic K ; or a monochromatic cycle. One is obtained from the coloring of S by ipping the colors of the corresponding vertices. The other is as depicted in Figure 3. In both colorings of S , there are 5 vertices colored b and 3 vertices colored a. Repeating this argument, we see that in all possible colorings of Sj that will avoid monochromatic K ; and monochromatic cycle, there are 5 vertices colored a if j is even, and 5 vertices colored b if j is odd. In particular, 5 vertices in S k1 are colored a. It is easy to see that this will creat a monochromatic cycle in the subgraph induced by the two cubes S and S k1 . This completes the proof of Theorem 5.
1 1 3 2 0 2

vertices of G are colored by two colors, then there is a monochromatic star K;.
1 3

Corollary 1 Suppose G is the product of at least ve odd cycles. If the
1 2 3 4 5

Proof. We may assume that G = C 2C 2C 2C 2C and that the vertices of Ci are f0; 1; 2; ; 2kig. Let : V (G) ! fa; bg be a 2-coloring of the ver9

tices of G. By Theorem 5 the restriction of to the subset f(0; x ; x ; x ; x ) : 0 xi 2ki g of V (G) contains either a monochromatic K ; or a monochromatic cycle. If there is a monochromatic K ; then we are done. Thus we assume that there is a cycle X f(0; x ; x ; x ; x ) : 0 xi 2ki g such that (X ) = a. Let Xi = f(i; x ; x ; x ; x ) : (0; x ; x ; x ; x ) 2 X g. If for each i, the colors of the vertices of Xi are obtained by ipping the colors of the corresponding vertices of Xi? then all the vertices of X k1 are colored a and hence we have a monochromatic K ; . Otherewise we may assume that there is a one vertex of X is colored a, then again we obtain a monochromatic K;.
2 3 4 5 1 3 1 3 4 0 2 3 5 0 2 3 4 5 2 3 4 5 0 1 2 1 3 1 1 3

Conjecture 1 For any integer m, there is an integer f (m) such that if G is
the product of at least f (m) odd cycles then for any 2-coloring of the vertices of G there is a monochromatic star K ;m.
1

4 Lexicographic product
The lexicographic product G H ] of two graphs G and H has vertex set V (G H ]) = V (G) V (H ), and (g; h) is adjacent to (g0; h0) if and only if either g = g0 and (h; h0) 2 E (H ) or (g; g0) 2 E (G). In this section, we derive an upper bound on the relaxed chromatic number P (G H ]) for any graphs G; H and any hereditary family P of graphs. We need the de nition of the star-chromatic number of a graph. Suppose G is a graph and k; d are positive integers such that k 2d. A (k; d)-coloring of G is a coloring c of the vertices of G with k colors f0; 1; 2; ; k ? 1g such that if (x; y) 2 E (G), then d jc(x) ? c(y)j k ? d. If there is a (k; d)-coloring of G then we say that G is (k; d)-colorable. Note that a (k; 1)-coloring is just the ordinary k-coloring. The star-chromatic number (G) of a graph G is de ned as (G) = minfk=d : G is (k; d) ? colorableg: The existence of the \minimum" was proved in 1, 8]. It was also proved in 1, 8] that (G) ? 1 < (G) (G) for any graph G. An upper bound on the chromatic number of G H ] in terms of the star-chromatic number of 10

G and the chromatic number of H was given in 11]. This bound is sharp for many circulant graphs 4]. The following theorem generalizes the upper bound given in 11] to relaxed colorings.

Theorem 5 For any graphs G; H and for any hereditary family P of graphs, we have P (G H ]) d (G) P (H )e. Proof. Suppose (G) = k=d and P (H ) = n. Let c : V (G) ! f0; 1; ; k ? 1g be a (k; d)-coloring of G, and let c0 : V (H ) ! f0; 1; ; n ? 1g be a P -ncoloring of H . De ne f : V (G H ]) ! f0; 1; ; d (G) P (H )e as follows:
f (g; h) = b c(g) +dc (h)k c:
As b nkd? c d nk ? 1e, f is a mapping of V (G H ]) to f0; 1; ; d nk ? 1eg. d d We now show that for any color class X = f ? (i), i = 0; 1; ; d nk ? 1e, d the subgraph of G H ] induced by X is a member of P . Indeed, if f (g; h) = f (g0; h0) then j(c(g) + c0(h)k) ? (c(g0) + c0(h0)k)j < d. This implies that either c(g) = c(g0) and c0(h) = c0(h0), or 0 < jc(g) ? c(g0)j < d and c0(h) = c0(h0), or jc(g) ? c(h)j > k ? d and jc0(h) ? c0(h0)j = 1. In the second and third cases, (g; h) is not adjacent to (g0; h0), because c is a (k; d)-coloring of G. In the rst case, either (g; h) and (g0; h0) are not adjacent, or (h; h0) is a monochromatic edge with respect to the coloring c0. Therefore each connected monochromatic subgraph of G H ] with respect to the coloring f is contained in a copy of H , and is monochromatic with respect to the coloring c0. Since c0 is a P -n-coloring of H , the mapping f is indeed a P -d nk e-coloring d of G H ].
1 1

0

References
1] J. A. Bondy and P. Hell, A note on the star chromatic number, J. Graph Theory 14(1990), 479-482. 2] W. Deuber and X. Zhu, Circular coloring of weighted graphs, manuscript, 1994. 11

3] P. Erdos and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hung., 17(1966), 61-99. 4] G. Gao and X. Zhu, Star extremal graphs and the lexicographic product, to appear in Disc. Math. 5] P. Hell and J. Nesetril, On the complexity of H -colouring, J. Combin. Theory B 48(1990), 92-110. 6] P. Hell, J. Nesetril and X. Zhu, Duality of graph homomorphisms, Combinatorics, Paul Erdos is eighty, Vol. 2, Bolyai Society Mathematical Studies, 1994. 7] L. Lovasz, On chromatic number of nite systems, Acta Math. Acad. Sci. Hung., 19(1968) 59-67. 8] Star chromatic number, J. Graph Theory, 12(1988) 551-559. 9] D. Woodall, Improper colorings of graphs, Graph Colorings, Ed. R. Nelson and R. J. Wilson, John Wiley & Sons, Inc., New York, 1990. pp. 45-64. 10] M. L. Weaver and D. B. West, Relaxed chromatic numbers of graphs, Graphs and Combinatorics, 10(1994), 75-93. 11] X. Zhu, Star-chromatic numbers and products of graphs, J. Graph Theory, 16(1992) 557-569.

12