IMFM Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia Preprint series Vol. 50 (2012), 1183 ISSN 2232-2094 THE b-CHROMATIC INDEX OF A GRAPH Marko Jakovac Iztok Peterin Ljubljana, December 12, 2012 сч i-Ч О сч сч о Ö о CSI I со и а CD и The b-chromatic index of a graph Marko Jakovac * University of Maribor Faculty of Natural Sciences and Mathematics Koroška cesta 160, 2000 Maribor, Slovenia marko.jakovac@uni-mb.si Iztok Peterin University of Maribor Faculty of Electrical Engineering and Computer Science Smetanova ulica 17, 2000 Maribor, Slovenia iztok.peterin@uni-mb.si December 10, 2012 Abstract The b-chromatic index y>'(G) of a graph G is the largest integer k such that G admits a proper k-edge coloring in which every color class contains at least one edge incident to some edge in all the other color classes. The b-chromatic index of trees is determined and equals either to a natural upper bound m'(T) or one less, where m'(T) is connected with the number of edges of high degree. Some conditions are given for which graphs have the b-chromatic index strictly less than m'(G), and for which conditions it is exactly m'(G). In the last part of the paper regular graphs are considered. It is proved that with four exceptions, the b-chromatic number of cubic graphs is 5. The exceptions are K4, K3,3, the prism over K3, and the cube Q3. Key words: b-chromatic index, regular graphs; AMS subject classification (2010): 05C15, 05C76 1 Introduction and preliminaries A b-vertex coloring of a graph G is a proper vertex coloring of G such that each color class contains a vertex that has at least one vertex in every other color class in its neighborhood. The b-chromatic number of a graph G is the largest integer <^(G) _ * Corresponding author m CSI CD О for which G has a b-vertex coloring with ^>(G) colors. This concept was introduced СЧ in [14] by Irving and Manlove by a certain partial ordering on all proper colorings in contrast to chromatic number x(G). Namely, x(G) is the minimum of colors used among all minimal elements of this partial ordering, while ^>(G) is the maximum of colors used among all minimal elements of the same partial ordering. Since then the b-chromatic number has drawn quite some attention among the scientific community. Already Irving and Manlove [14] have shown, that computing ^>(G) is an NP-complete problem in general. Hence the approximation approach described in [7] seems natural. The b-chromatic number of some special graph classes has been studied in [9, 8, 10, 3]. The bounds for the b-chromatic number have been studied in [19] in general and for some graph classes in [6, 21, 1, 2]. The b-chromatic number has been considered with respect to subgraphs in [12, 17], while the b-chromatic number under graph operations was considered in [20] for the Cartesian product and in [16] for the other three standard products. In [4] an interesting concept of b-continuous graphs was introduced as graphs for which there exists a t-b-vertex coloring for every integer t between x(G) and ^>(G). Intuitively, we need to have enough vertices of high enough degree, at least one in each color class. Let v\,... ,vn be such a sequence of vertices, that d(vi) > ■ ■ ■ > d(vn). Then m(G) = max{i | d(vj) > i — 1} is an upper bound for ^>(G). From this point of view, d-regular graphs are of special interest, since m(G) = d + 1 for a d-regular graph G and every vertex is a candidate to have each color class in its neighborhood. Indeed, in [22] it was shown that if a d-regular graph G has at least d4 vertices, then the equality ^>(G) = d + 1 holds. This bound was later improved to 2d3 in [5]. In particular it was shown in [15], that there are only four exceptions among cubic graphs with ^>(G) < 4, one of them being the Petersen graph. We introduce in this work an edge version of b-vertex coloring and b-chromatic number, namely b-edge coloring and b-chromatic index, respectively. It is a natural approach to study vertex concepts on edges and vice versa. A classical example are the chromatic number and the chromatic index. But we can also find more recent dates. For instance in [13] the edge Winer index was defined in four different ways. One of these approaches, via the line graph, we also use here. A b-edge coloring of a graph G is a proper edge coloring of G such that each color class contains an edge that has at least one incident edge in every other color class and the b-chromatic index of a graph G is the largest integer ^>'(G) for which G has a b-edge coloring with ^>'(G) colors. An edge e of color i that has all other colors on its incident edges is called color i dominating edge or we say that color i is realized on edge e. In the rest of this section we recall some standard notation that will be used later. In the second section we first describe some bounds, compute ^>'(T) for every tree T, and show that general bounds with respect to A(G) cannot be improved. In third section we show that for many regular graphs <^'(G) attains the trivial upper bound. Next section is devoted to graphs where <^'(G) is strictly less than the trivial CO о Ö CSI 00 CSI CSI и а CD и CSI CD О upper bound and in the last section we describe the complete list of cubic graphs СЧ for which the trivial upper bound is not achieved. Let G be a graph. The line graph L(G) of a graph G is a graph with V(L(G)) = E(G), and two edges of G are adjacent in L(G) if they share a common vertex. Clearly ^>'(G) = ^>(L(G)). Number of vertices incident with the vertex v is the degree of v and is denoted by d(v). If all vertices have the same degree d, we say that G is a d-regular graph. The Cartesian product G □ H of graphs G and H has the vertex set V (G) x V (H ). Two vertices (g,h) and (g', h') are adjacent iff they are adjacent in one coordinate and equal in the other, i.e. g = g' and hh' € E(H) or gg' e E(G) and h = h'. The Cartesian product is associative (see [11]) and hence we can write more factors without brackets: Gi □ ■ ■ ■ □ Gk. If every factor Gi, i € {1,..., k}, is isomorphic to the complete graph Kni, then we call such a Cartesian product a Hamming graph. For more about Cartesian product in general or Hamming graphs in particular see the book [11]. i—l 2 Bounds, trees, and realizability О Every proper edge coloring of a graph G with x'(G) colors is also a b-edge coloring. If not, then every edge of a color class with no realizable edge can be recolored by some other color. This yields a proper edge coloring with less than x'(G) colors, which is a contradiction. Hence x'(G) is a trivial lower bound of <^'(G). On the other hand, a (realizable) edge e can have at most 2A(G) — 2 colors in its neighborhood СЧ (A(G) — 1 in every end vertex). Together with the color of e, this gives a trivial upper bound for ^(G), namely 2A(G) — 1. Let e = uv be an edge of G. Denote with Nu(e) the set of edges in G that share u with e, and Nv(e) the set of edges in G that share v with e. By N(e) we denote the neighborhood of an edge e, which is N(e) = Nu(e) U Nv(e). The degree of edge e is denoted with d(e) and is equal to |N(e)|. The trivial upper bound is meaningful only if there exist enough (> 2A(G) — 1) edges in G of degree 2A(G) — 2, such that every color is realized. Otherwise we can lower the trivial upper bound as follows. Let e1,..., em be edges of G and d(e1) > ... > d(em) the degree sequence of these edges. Then m'(G) = max{i | d(ei) > i — 1} is an improved upper bound for <^'(G). Hence A(G) < x'(G) < p'(G) < m'(G) < 2A(G) — 1. Note that for regular graphs m'(G) = 2A(G) — 1 and for stars K1;^ we have m'(G) = A(G). Every realizable edge of a b-edge coloring must have degree at least m'(G) — 1. Hence we call an edge e with d(e) > m'(G) — 1a dense edge. The distance between edges e, f € E(G) is defined as the numer of edges on a CO CO и CD m и a CD U shortest path between e and f. We now present the exact value for the b-chromatic index of trees. We use a СЧ similar approach than the one used by Irving and Manlove in [14] for the b-chromatic number of trees. СЧ Definition 2.1 A tree T is called pivoted if it has exactly m'(T) dense edges and an edge e such that: 1. Edge e is not dense. CD 00 00 о Ö о CSI и a CD U 2. There exist two dense edges that are incident with edge e and are not incident with each other. CD 3. Each dense edge is incident to e or to a dense edge incident to e. 4. Any dense edge incident to e and to another dense edge which is not incident to e has degree m!(T) — 1. We call such an edge e the pivot of tree T (for an example see Fig. 1). Clearly, the pivot is unique if it exists. Theorem 2.2 If T is a pivoted tree then 2 by Property 2 of Definition 2.1 and q > 1, since e is not a dense edge. 00 Let us first show that (T) < m'(T). Suppose that there exists a b-edge coloring c of T with m'(T) colors. Without lose of generality assume that c(e^ = i, i € (1,..., m'(T)}. Since d(ej) = m'(T) — 1, j € (1,..., q}, edges e1,..., eq are incident to exactly one edge of any other color. Moreover, every dense edge ep+1,..., em/(T) is incident with exactly one edge from e1,..., eq. Now e cannot receive color j € (1,... ,p}. Also it cannot receive color j € (p + 1,..., m'(T)}, or else some ek, k € (1,... ,q}, is incident to two edges of that color and is not realizable. Hence there is no available color for edge e. Next we prove that ^>'(T) = m'(T) — 1 by constructing a proper b-edge coloring c of T with m'(T) — 1 colors. By Property 2 of Definition 2.1 there exist two edges e1 and ei, 2 < i < p, which are incident to e and are not incident with each other. Also for some r € (q + 1,..., m'(T)} there exists a dense edge er which is incident to e1 but not to e. Set c(ej) = j — 1, j € (2,..., m'(T)}, c(e) = r — 1 and c(e1) = i — 1. With this all dense edges are colored together with e. Next we consider uncolored edges that are incident to some dense edge ei, i € (1,... ,m'(T)}. Let f be such an edge. Clearly f is not dense. The only colored m сч i-Ч О сч сч и cd cd о cd со 00 0 Ö о сч 1 сч со сч сч г со со edges incident to f are at most m'(T) — 2 edges. Hence, we can choose a free color for edge f, since m'(T) — 2 < m'(T) — 1. Now we repeat the described procedure by choosing another uncolored edge incident to e^ Each time we choose a color that was not in the neighborhood of ej. Hence, after coloring all the neighbors of ej, edge ej becomes a dominating edge. This argument applies to each ej, i € {1,..., m'(T)}, in turn. Finally suppose that e^ is uncolored for some i € {m'(T) + 1,..., |E(T)|}. As d(ei) < m'(T) — 1, not all of colors 1,..., m — 1 appear on neighbors of e^. Hence there is some color available for e^. It follows that the constructed coloring is a b-edge coloring of T and <^'(T) = m'(T) — 1. □ In order to deal with trees that are not pivoted we give the following definition which is closely related to pivoted trees. Definition 2.3 Let T be a tree and let E' be the set of dense edges of T. Suppose that E'' is a subset of E' of cardinality m'(T). Then E'' encircles some edge e € E\E'' if: 1. There exist two dense edges in E'' that are incident with edge e and are not incident with each other. 2. Each dense edge in E'' is incident to e or to a dense edge incident to e. 3. Any dense edge in E'' incident to e and to another dense edge in E'' which is not incident to edge e has degree m'(T) — 1. We refer to e as an encircled edge with respect to E'' (for an example see Fig. 1). m CD 'H CD m Ò о о о Figure 1: A pivoted tree T with m'(T) = 6, encircled edge e, and <^'(T) = 5 Clearly the pivot is encircled by the set of dense edges in a pivoted tree, but encircled edge of some tree T is not necessarily the pivot of T. We give an addition definition that incorporates the concept of encirclement. U a CD U Definition 2.4 Let T be a tree and let E' be the set of dense edges of T. Suppose СЧ that E'' is a subset of E' of cardinality m'(T). Then E'' is a good set with respect to T if: 1. Set E'' does not encircle any edge in E\E''. 2. Any edge e € E'' with d(e) > m'(T) is incident to some f € E'' with d(f ) = m'(T) - 1. CD О Ö I CSI 00 CSI CSI а CD и Lemma 2.5 Let T be a tree. If T is not a pivoted tree, then there exists a good set for T. CD Proof. Let E' be the set of dense edges of T. By the definition of m'(T), we may choose E'' C E' with |E''| = m'(T) such that every edge in E\E'' has degree less than m'(T). Let E = {ei,..., e|E(T)|} be ordered in such a way that E'' = {eb ... ,em'(T)}- If E'' does not encircles an edge, we are done since E'' satisfy Properties 1 and 2 of Definition 2.4. So we may assume that E'' encircles some edge e / E''. Let e1,... ,ep be edges of E'' incident to e, p < m'(T), and e1,...,eq, q < p, edges of E'' incident to e each having at least one other member of E'', which is not incident to e, as a neighbor. Clearly p > 2 by Property 1 of Definition 2.3. Also q > 1, otherwise p = m'(T) by Property 2 of Definition 2.3, and hence d(e) > m'(T), which contradicts the choice of E''. Thus there exists an edge er, p + 1 < r < m'(T), incident to e1 but not to e. Let e^ 2 < i < p, be an edge incident to e but not to e1. (Such an edge exists according to Property 1 of Definition 2.3.) Case 1: Suppose that edge e is dense. By the choice of E'' we have d(e) = m'(T) - 1. Let W = (E''\{ei}) U {e}. Also by the choice of E'', the only edge not in W that can have degree at least m'(T) is e^ But ei is incident to e € W, and d(e) = m'(T) - 1. So W satisfies Property 2 of Definition 2.4. Let f € E\W be an edge different from ei which is incident to some edge of W. Property 1 of Definition 2.3 is not fulfilled for f by W and f is not encircled by W. Also ei is CO not encircled, since er is to far away from ei. All other edges from E\W are not CO incident with any edge from W and can not be encircled by W. Hence Property 1 of Definition 2.3 is also fulfilled and W is a good set. Case 2: Now suppose that e is not dense. If |E'| = m'(T), then tree T is pivoted for e which is a contradiction. Hence |E'| > m'(T) and there exists a dense edge f € E\E''. Let W = (E''\{e1}) U {f}. Suppose that W encircles some edge g. At most one edge not in W lies on the path between two arbitrary non-incident edges of W, namely edge g. But edges e1 / W and e / W lie on the path between edges ei € W and er € W. This contradiction implies that W satisfies Property 1 of Definition 2.4. Also, W satisfies Property 2 of Definition 2.4, since d(e1) = m'(T) — 1 by Property 3 of Definition 2.3, and therefore every dense edge outside W has degree less than m'(T). □ m о cd We establish next the b-chromatic index of trees that are not pivoted. СЧ Theorem 2.6 If T is a tree that is not pivoted, then 1 and let d1,..., ds be colors c1,..., cs, so that di = ci for all i. Apply color dj to edge Xj, j € (1,..., s}. It is straightforward to verify that Properties (a), (b), and (c) hold. CD 'H CD m и a CD U Case 2: Let s = 1. Because ej has at least two inner neighbors, there is some СЧ neighbor f, which is already colored, say by color d. Attach color d to x\, and color ci to f. Again, it is not difficult to verify that (a), (b), and (c) hold. Now we deal with the uncolored inner neighbors of ep+1,..., eq (assuming that Q = 0). Let z1,...,zk be those inner neighbors. Then no e^ i € {p + 1,...,q}, can have more than one neighbor among the Zj's, and so assigning colors to Zj's, at most one neighbor of each ej is colored. It therefore suffices to ensure that, in assigning a color to each Zj, the following holds: CSI и cd (d) the partial coloring remains proper, (e) no ej of degree exactly m'(T) — 1 has two neighbors of the same color. Let C be the set of colors defined as follows: CO c € C ^ (ec € N (Zj)) V (3d : ec € N (ed) Л ed € N (zj) Л d (ed) = m'(T) — 1) , i—l where c, d € {1,..., m'(T)}. If we choose a color c € C, then (d) and (e) continue to hold. If C = {1,..., m'(T)}, then zj is encircled by W, which is a contradiction since W is a good set. Hence there is always a choice of color for z j. Note that each er, r € {p + 1,..., q}, has only one inner neighbor colored in this way, so that if d(er) > m'(T), then at most two edges incident to er have the same color. All inner edges are now colored. Next we deal with outer edges of U. The outer neighbors of ej, i € {1,..., m'(T)} can be colored independently. Let f be an outer neighbor. The only colored edges incident to f are some dense edges and some inner edges. But they are all incident in the same endvertex of edge f, which means that every outer neighbor has at most A(T) — 1 colored neighbors. Hence, we can choose a free color for edge f since m'(T) > A(T) — 1. Now we repeat the described procedure by choosing CSI another uncolored edge incident to ej. Each time we choose a color that is not in the neighborhood of ej. Hence, after coloring all the neighbors of ej, edge ej becomes a dominating edge. This argument applies to each ej, i € {1,..., m'(T)} in turn. We may extend this partial b-edge coloring with m'(T) colors to a b-edge coloring of T with m'(T) colors as follows. Any remaining uncolored edge e must satisfy d(e) < m'(T) — 1. For, if d(e) > m'(T), then by Property 2 of Definition 2.4, e is incident to some edge f € W, where d(f ) = m'(T) — 1, so that e was already colored. An edge e of degree less than m'(T) cannot have neighbors colored with all of the colors 1,..., m'(T). Hence, there is some color available for edge e. This completes the construction of a b-edge chromatic coloring of T with m'(T) colors. □ m Since testing whether a tree is pivoted may be carried out in linear time, it is clear from Theorems 2.2 and 2.6 that we may compute the b-chromatic index of a О CSI I и CD m и a CD U tree in polyinomial time. CD CD О Corollary 2.7 If T is a tree and L(T) its line graph, then )) can be deter- СЧ mined in polynomial time. As we will see next, trees are already enough to show that the lower bound and the upper bound are tight with respect to the maximum degree. For this let k be a fixed positive integer and let T be a tree on n vertices with A(T) < k. Clearly T has n — 1 edges. We construct tree T' from T as follows. Attach k — deg(u) pendant vertices to every vertex u of T. Hence T' has exactly n vertices of degree k and all other vertices of T' have degree 1. Moreover all vertices of degree k in T' form a connected subtree of T' which is T. All edges of T' that are also in T have degree 2k — 1 and we have n — 1 such edges. Moreover, T' is clearly not a pivoted tree. If n < A(T') = k, we have m'(T') = A(T') and with this also f'(T') = A(T') by Theorem 2.6. For n > A(T'), we have n — 1 edges in T' of degree 2A(T') — 2, while all other edges have degree k — 1. Thus m'(T') = n — 1. By Theorem 2.6 we have <^'(T') = n — 1 whenever n < 2A(T'). We have constructed a tree T' with ^Z(T') = n — 1 for an arbitrary n with A(T') < n — 1 < 2A(T') — 1. We have proved 1 the following theorem. Theorem 2.8 There exists a tree T' with maximum degree A(T'), such that <^'(T') = £ for every integer £ and A(T') < £ < 2A(T') — 1. 3 Graphs with y'(G) = m'(G) О As in the case of b-chromatic number regular graphs play an important role also for the b-chromatic index. First reason for this is that m'(G) = 2A(G) — 1 for any regular graph. Another reason is that we can always end the coloring by a greedy algorithm once we have a partial coloring of G in which all 2A(G) — 1 colors are realized. Thus we have <^'(G) = 2A(G) — 1 for a regular graph G, if we can find such a partial coloring of G. We present in this section two results for regular graphs. First recall that a graph G is of class 1 if x'(G) = A(G) and of class 2 if x'(G) = A(G) + 1. For a vertex v of G is S2(v) a set of all vertices of G that are CO at distance 2 to v. We define a graph G[v] as follows: V(G[v]) = N(v) U S2(v) and E(G[v]) = {e = uw|u,w € N (v)} U {e = uw : u € N (v) and w € S2(v)}. Theorem 3.1 Let G be a d-regular graph with diam(G) > 4 and let u and v be two vertices at distance at least 4- If N[u] and N[v] are class 1 graphs, then p'(G) = 2d — 1. i CSI 00 CSI CSI co CD Proof. Let G be a d-regular graph and u and v two vertices of G with d(u, v) = 4. We split colors in to two sets A = {1,..., d} and B = {d + 1,..., 2d — 1}. Let N(u) = {ui,..., ud} and N(v) = {vi,..., vd}. We define edge coloring c : E(G) ^ CO J-H a CD J-H CSI {1,..., 2d — 1} as follows. Let с(щп) = i for i € {1,..., d} and c(vjv) = d + i for сч i € {1,..., d — 1}. In addition let c(vdv) = 1. Next we color all edges of G[u] and G[v]. Since they are both class 1 graphs, there exists an edge coloring of each with A(G[u]) = A(G[v]) = d — 1 colors. We use colors from B for G[u] and colors from A — 1 for G[v]. Note that every uj, i € {1,..., d}, has degree d — 1 in G[u] and thus have all colors from B on its incident edges. But then color i is realized on uui for every i € {1,..., d}. Similarly every v^ i € {1,..., d}, has degree d — 1 in G[v] and thus have all colors from A — 1 on its incident edges. But then color j, j € {d + i,..., 2d — 1}, is realized on vv i for every i € {1,..., d}. Hence all colors are realized and this partial coloring is a proper coloring since d(u, v) = 4. Since all colors are realized and we have 2d — 1 colors we can end the coloring by the greedy coloring. Hence cC is a b-edge coloring and <^'(G) = 2d — 1. □ CD О О CSI I Note that for every bipartite graph G and any vertex v of G, the graph G[v] is bipartite (bipartition is induced with N(v) and S2(v)). Since every bipartite graph is class 1 graph by König's Theorem, we have the next corollary. i—l Corollary 3.2 If G is a bipartite d-regular graph with diam(G) > 4, then <^'(G) = 2d — 1. Ö In particular, for n > 4, the hypercube Qn = □jLi K2 has diameter n and is a bipartite n-regular graph. Hence <^'(Qn) = 2n — 1. However <^'(Q2) = 2 < 3 and ^>'(Q3) = 4 < 5 as we will see in the next section. One of the most important questions about b-chromatic number is whether the Petersen graph G is the only regular graph of girth 5 with its b-chromatic number strictly lower than m(G). We will see that this is not a problem for the b-chromatic index. СЧ Theorem 3.3 If G is a d-regular graph with girth g > 5, then p'(G) = 2d — 1. CO Proof. Let e = uv be an edge in a graph G with girth g > 5 and let Nu(e) = {v, u2,..., ud} and Nv(e) = {u, vd+1,..., v2d-1}. We define a partial edge coloring с : E (G) ^ {1,..., 2d — 1} in the following way: • c(uv) = 1, • c(uui) = i, i € {2,..., d}, • c(vvj ) = j, j € {d + 1,..., 2d — 1}. • Sh Vertices ui cannot be adjacent to vertices v j, since we would get a 4-cycle contrary to the assumption. It may also happen that N(ui) П N(vj) = 0 for some i and j. U a CD U CSI But since N (uj) n N (uj ) = 0 and N (vj) П N (vj ) = 0 for all applicable i and j we can СЧ continue the coloring procedure in the following way. Assign colors {d+1,..., 2d—1} to all non-colored edges incident with Ui,i e {2,..., d}, and colors {2,..., d} to all non-colored edges incident with v j, j e {d + 1,..., 2d — 1}. With this partial edge coloring all colors are realized on edges uv, uui, and vvj for every i e {2,..., d} and j e {d +1,..., 2d — 1}. Color the rest of the graph with the greedy algorithm to get a proper b-edge coloring of G with 2d — 1 colors. □ § 0 4 Graphs with ^'(G) < m'(G) We have shown in the previous section that for many graphs equality ^>'(G) = m'(G) holds. One can get the impression that finding '(G) < m'(G). Indeed, 00 once this inequality holds, it seems to be very hard to find the exact value for ^>'(G). This is the reason that we believe this problem to be NP complete, despite the fact that one can not use the same reduction as in the case of <^(G) in [14]. A graph G is an edge regular graph or d- edge regular graph if all edges of G have degree d. Clearly every d-regular graph is also a 2d-edge regular graph and Km,n is a (m + n — 2)-edge regular graph. Theorem 4.1 If G is a d-edge regular graph with minimum degree 5 > 4 and <^'(G) = d + 1, then at most two edges of any 4-cycle and at most two edges of any triangle realize their color in (d + 1) -b-edge coloring of G. 1 Proof. Let G be a d-edge regular graph with (G) = d + 1 and let c : E (G) ^ 00 CSI CSI {1,...,d + 1} be a b-coloring of E (G). Suppose that {u^u2,u3,u4} form a four cycle C4. Without loss of generality we may assume that c(u1u2) = 1, c(u2u3) = 2, c(u3u4) = 3, and c(u4u1) = 4. Suppose that u1u2 realize color 1. We split colors in two sets A = {i|c(u1v) = i} and B = {i|c(u2w) = i}. Hence in A and in B are colors of all edges that are incident with u1 and u2, respectively. Since <^'(G) = 2d — 1, we have A n B = {1} and A U B = {1,..., d + 1}. In particular 2 e B and 4 e A. It is enough to show that three (or more) consecutive edges of C4 cannot all realize their color. Suppose first that u2u3 realize color 2. Color 3 must then be in A and set C that contains colors of all edges incident with u3 equals {2} U A — {1}. Thus u3u4 does not realize color 3, since it has two edges of color 4 in its neighborhood. Also u4u1 does not realize color 4, since it has two edges of color 3 in its neighborhood. Let now u1u2u3 be a triangle in G. Again set c(u1u2) = 1, c(u2u3) = 2, and c(u3u1) = 3. Suppose that u1u2 and u2u3 realize colors 1 and 2, respectively. Let A and B be as before. Then C = {i : c(u3w) = i} equals to A since <^'(G) = d + 1 and u1u2 and u2u3 realize their colors. Hence u1u3 does not realize its color. □ CD U a CD U CSI Note, from above proof, that we have two possibilities. Namely, realizable edges СЧ of C4 are either two consecutive edges of C4 or two opposite edges of C4. Also C4 is not necessarily an induced cycle. But if C4 is not induced, we need the additional condition 6 > 4 of Theorem 4.1. If uiu3 € E (G), then c(u\u3 ) = 3 and we need an additional edge incident with ui so that color 3 is in A. Hence if we demand an induced cycle C4, we do not need the condition 6 > 4 anymore. By observing <^'(Kn) for small n it seems that it equals to x'(Kn). Namely, it is not hard to see that 4, then <^'(Kn) < m'(Kn). Proof. Suppose that <^'(Kn) = m'(Kn) = 2n — 3 and let c be a b-edge coloring of E(Kn) with 2n — 3 colors. Let H be a spanning subgraph of Kn whose edges are realizable edges of c. By Theorem 4.1 H has no triangle and no four cycle. Moreover, H is a forest. Namely, if Ck, k > 4, is in H, then three consecutive edges of C k are all realizable on a four cycle in contradiction to Theorem 4.1. This forest has the most edges if it is a tree T. But a spanning tree T has at most n — 1 edges which is a contradiction. □ i For complete bipartite graphs, recall the well-known result that L(Kp,r) = Kp^Kr. Kouider and Maheo have shown in [19] that ^>(Kp^Kr) = r whenever CSI r > p(p — 1) and for p < r < p(p — 1) we have r < ^>(Kp^Kr) < p(p — 1). Hence we have ^>'(Kp,r) = r for r > p(p — 1) and r < 2. We can immediately improve the upper bound in many cases since Kp,r is an edge regular graph with m'(Kp,r ) = p + r — 1. Hence HH <^'(Kp,r) < min{p(p — 1),p + r — 1}. To improve this we need some further arguments. Proposition 4.3 If r > p > 3, then p'(Kp>r) < m'(Kp,r). Proof. If m'(Kp,r) = p(p — 1) we are done by results from [19] (see the above discussion). Thus suppose that (Kp,r) = m'(Kp,r) = p + r — 1 and let c be a b-coloring of E(Kp,r) with p + r — 1 colors. Let H be a spanning subgraph of Kp,r whose edges are realizable edges of c. Again H is a forest, since every cycle Ck, CO k > 4, induce a four cycle in Kpr with three realizable edges, which is not possible СЧ by Theorem 4.1. Moreover, if edges uv and vw are realizable for some colors, then no edge ux or wx is realizable, since it is on a common four cycle uvwxu. Hence we must find a cover of Kp,r by stars with maximum number of edges and every edge of this stars can be a realizable edge. Clearly this number is p + r — 2 if we take two stars Ki,r-i and K1)P-1. Thus we have p + r — 2 candidates for realizable edges, CSI и CD which is a contradiction, since we need at least p + r — 1 candidates. □ We believe that this upper bound can be lowered by one in general, but not more as can be seen from the following schemes. On the scheme we present b-edge colorings of K3,3, K44, and K5,5 with 3, 5, and 7 colors, respectively: 00 00 о Ö и a CD U K : 1.2.3. 231 312 ; K : 1.2.3.4 4.523 5.342 2451 3,3 : 1.23 2.31 3.12 ; 4,4 : 1.4.5.2 2.534 3.245 4321 K 5,5 : 1.2.3.4.7 5.6734 6.7413 73162 2567.1 1.5.6.72 2.6735 3.7416 4.3167. 54321 Here 12347 in first line and first column of K5,5 represents colors of u1w1, u1w2, u1w3, u1w4, and u1w5, respectively, and k. means that this edge realize color k. Unfortunately we could not find a pattern for every graph Kn,n. Next we show that there exists no 4-b-edge coloring of K3,3, which is a difficult task already, since we can not use Theorem 4.1 anymore. Proposition 4.4 ^'(K3 3) = 3. Proof. Suppose that there exists an 4-b-edge coloring of K3 3 and let c be a b-00 coloring of E(Kpr) with 4 colors. Let H be a spanning subgraph of Kpr whose СЧ edges are realizable edges of c. We will analyze all different possibilities for H. If H is isomorphic to a forest of two stars K1 , 2, we have a contradiction, since the edge between centers of these two stars can not be colored by any of four colors. If H is isomorphic to C4 U {x, y}, we have a contradiction since edge xy can not be colored. If H is isomorphic to P4 U K2, the middle edge of P4 is not realizable, since the color of K2 cannot be in its neighborhood. If there exists a path P5 in H and an isolated vertex x, we first concentrate on the first and last edge e and f, respectively, of P5. It is easy to see that all edges, except the edge between the middle vertex of P5 and x, must be colored, so that e and f are realizable edges. In that case the middle edges of P5 cannot be realizable, since only one edge remains and each of them needs one additional color. Finally, suppose that H contains one component that is isomorphic to K1 , 3 in which one edge is subdivided and one isolated vertex. It is easy to see, that edges of K1>3 that where not subdivided cannot be both realizable, since only one can have the color of the other pendant edge in its neighborhood. □ CD сч i-Ч О сч сч i-Ч CD гО а CD О CD Q СО 00 0 Ö о сч 1 сч со сч сч £ со со со CD 'H CD СО Jh а CD U Let G be a k-partite complete graph K, tion to see that Kn ■ ,nk ni,...,nk• It is a straightforward computa-is an edge regular graph if and only if щ = ... = nk = n. Then Kni)...>nfc is (k — 1)n-regular graph and we will use notation Kk for this graph. Proposition 4.5 If k > 3 and n a positive integer, then у''(K) < ш'(КП). Proof. Suppose that ) = m'(Kn) = 2(k — 1)n — 1 and let c be a b-coloring of E (Kn) with 2(k — 1)n — 1 colors. Let H be a spanning subgraph of K whose edges are realizable edges of c. By Theorem 4.1 H is a forest. In contrast to proof of Proposition 4.3, here we can have a component different than a star. Clearly we have more edges if the number of components of H is smaller. Nevertheless, even if H is a tree, we have kn — 1 edges in H, which is not enough, since k > 3. □ Let G be a regular graph. In view of Theorem 3.1, one can expect more graphs with y'(G) < m'(G) among those with small diameter (< 4). Such are Hamming graphs with two or three factors. It seems that it is quite hard to give an exact answer for general Hamming graph Kp^Kr. The impression is that, if p and r are "large" enough, we have equality between у' and m'. For this note that from Theorem 4.1 easy follows that ^>'(K2^K3) < m'(K2□Ks) = 5, but on the following scheme there is a 4-b-edge coloring of K2^K3, which yields ^>'(K2^K3) = 4. On this scheme also an 11-b-edge coloring of K3^K5 is presented. (Note that m'(K3□Ks) = 11.) 2.4 K2^Ka : 1. 34. 3. — 11 2— Ka^K; 5 1.2.3.4. 7 11 8 8 11 7 _ 3 10 10 10 10 5.6.7.8. 3 4 11 11 4 3 _ 1 2 2 2 2 9.10.11.3 487 78 4 _ 5 6 6 6 6 Again k. is the edge that realizes color k. Every odd line represents colors of edges of a K5 layer, while every even line represents colors of edges in K3 layers that projects to the same edge. Furthermore in every odd line numbers that are written in i-th column present consecutive colors of edges (i,i + 1),..., (i, 5) for i e {1,2,3, 4}. For Q3 = K2^K2^K2 it is easy to see, with the use of Theorem 4.1, that 2 we can expect equality between у' and m'. On the other hand we do not dare to predict what happens if p = q = 2. Namely, if у' is always less than m', or there exists an integer k, such that equality holds for every r > k, or equality holds for some integers and for some not. о сч сч и cd cd о cd 5 3-regular graphs We already know that if G is a d-regular graph, then <^'(G) < 2d — 1. Many of d-regular graphs achieve this trivial upper bound by Theorems 3.1 and 3.3. Determining <^'(G) is equivalent to determining ^>(L(G)) which is also a regular graph. Acorrding to the theorem of Kratochvll, Tuza, and Voigt [22] there are only a finite number of regular graphs with

1, let Di = {v € V(G)|d(v, C) = i} be the i-th distance level with respect to C. According to Theorem 3.3 we only need to consider cases where g = 3 and g = 4. On figures that follows we usually present only a part of the graph in which we find an induced C5 or P6, since the rest can be color by greedy algorithm. Also we do not draw all possibilities that have the same induced C5 or P6, but just one representative. Case 1: g = 3. In this case C is a triangle. We distinguish subcases with respect to the size of D1. 2 CSI Case 1.1: |DX| = 1. СЧ In this subcase G = K4 which is forbidden. Case 1.2: |Di| = 2. Let D1 = {x, y}. Note that there is a unique way (up to the isomorphism) how x and y are adjacent with the vertices of C. Assume without loss of generality that x has two neighbors in C (and hence y has one). Suppose first that xy € E (G). If x and y have a common neighbor in D2, then we have an induced C5, see the left graph on Fig. 4. If x and y have no common neighbor in D2, then |D2| =3. If vertices of D2 induce a triangle, then there is no vertex in D3 and this graph has no induced C5 or P6, but there is a 5-b-edge coloring on the second graph of Fig. 4. If D2 does not induce a triangle, then | D31 > 1 and one neighbor of y has a neighbor in D3. This yields an induced P6, see the third graph of Fig. 4. Finally if xy € E(G), then D| = 1, |Ds| = 2, and |DX| > 1. In all cases there exists an edge from D3 to D4 as denoted on the right graph of Fig. 4, and therefore we have an induced P6. CD О a T m CD и CD m и a CD и 1 5 4 1 3 Figure 4: Subgraphs with g = 3 and |D1| = 2 i Case 1.3: |Di| = 3. In this subcase each vertex from C has its own private neighbor in D1. If vertices СЧ of D1 induced a triangle, we get the forbidden graph K3 □ K2. Hence suppose that СЧ D1 does not induce a triangle and we always have two nonadjacent vertices in D1. If two nonadjacent vertices of D1 have a common neighbor in D2, then there exists an induced C5, see the left graph of Fig. 5. If two nonadjacent vertices of D1 have no common neighbor in D2, then we have |D2| = 6. In a cubic graph there exists two nonadjacent vertices among them with different neighbors in D1. They form an induced P6, see the second graph of Fig. 5 for one possibility. Suppose now that D1 induces K2 + K1 and denote K1 by x. If a neighbor of x in D2 coincides with a neighbor of some other vertex of D1, we get an induced C5, see the third graph of Fig. 5. If a neighbor of x in D2 is nonadjacent with a vertex of D2 which is nonadjacent to x, we have an induced P6, see the fourth graph of Fig. 5 (doted line means there is no edge). Otherwise both neighbors of x in D2 are adjacent to both neighbors in D2 of K2 in D1. This graph contains an induced C5, see the fifth graph of Fig. 5. Finally, if D1 induce P3, we have an induced C5, see the last graph of Fig. 5. о сч сч и cd cd о cd со 00 0 Ö о сч 1 сч со сч сч £ со со Figure 5: Subgraphs with g = 3 and |D1| = 3 Case 2: g = 4. Now C is a square. Note that two adjacent vertices of C have no common neighbor in D1. Once more we distinguish subcases with respect to the size of D1. It is obvious that the case |D1| = 1 is not possible. Case 2.1: |D1| = 2. If vertices of D1 are adjacent, we obtain K3,3 which is forbiden. Otherwise we have an induced C5 if they have a common neighbor in D2 or an induced Рб if they have no common neighbor in D2, see Fig. 6. Figure 6: Subgraphs with g = 4 and |D1| = 2 Case 2.2: |D1| = 3. Here two nonadjacent vertices of C must have a common neighbor in D1, while the other two have a private neighbor in D1. If this private neighbors are adjacent, we have an induced C5, see first graph on Fig. 7. If neighbors in D1 of two adjacent vertices of C are adjacent, we have |D2| > 2. This yields an induced P6, since the third vertex of D1 has two neighbors in D2, see the second graph on Fig. 7. Otherwise no two vertices of D1 are adjacent. If neighbors in D1 of two adjacent vertices of C have a common neighbor in D2, then these vertices form an induced C5, see the third graph of Fig. 7. Let x € D1 be a vertex with two neighbors in C. If a neighbor of x in D2 is nonadjacent to some other vertex of D2, we have an induced Рб, see the fourth graph on Fig. 7. Otherwise we have the last graph of Fig. 7 which also contains an induced Рб. m CD 'H CD m и а CD U Figure 7: Subgraphs with g = 4 and |D1| = 3 Case 2.3: |D1| = 4. Every vertex of C has his own private neighbor in D1. If two neighbors of nonadjacent vertices of C are adjacent, we have an induced C5, see the left graph of Fig. 8. CSI со со CD 'H CD СО Jh а CD U Now D1 does not induce a cycle C4, since we have either the first possibility or Q3 СЧ which is forbidden. If D1 induces paths P2, P3, 2P2, or P4, see the second, third, forth, and fifth graph, respectively, of Fig. 8 for an induced P6, which starts and ends in nonadjacent vertices of D1. Thus it remains to deal with the cases when there are no edges between vertices of D1. Since every vertex if D2 has at most three neighbors in D1, we can easily find an induced C5 or P6, see the lover three graphs of Fig. 8. □ S3 00 00 0 Ö о СЧ 1 Figure 8: Subgraphs with g = 4 and |D1| = 4 References [1] R. Balakrishnan, S. Francis Raj, Bounds for the b-chromatic number of the Mycielskian of some families of graphs, manuscript. [2] R. Balakrishnan, S. Francis Raj, Bounds for the b-chromatic number of G — v, Discrete Appl. Math. (2011) Doi:10.1016/j.dam.2011.08.022. 00 [3] R. Balakrishnan, S. Francis Raj, T. Kavaskar, Coloring the Mycielskian, Proc. Int. Conf. ICDM (2008) 53-57. [4] D. Barth, J. Cohen, T. Faik, On the b-continuity property of graphs, Discrete Appl. Math. 155 (2007) 1761-1768. [5] S. Cabello, M. Jakovac, On the b-chromatic number of regular graphs, Discrete Appl. Math. 159 (2011) 1303-1310. [6] F. Chaouche, A. Berrachedi, Some bounds for the b-chromatic number of a generalized Hamming graphs, Far East J. Appl. Math. 26 (2007) 375-391. [7] S. Corteel, M. Valencia-Pabon, J-C. Vera, On approximating the b-chromatic number, Discrete Appl. Math. 146 (2005) 106-110. [8] B. Effantin, The b-chromatic number of power graphs of complete caterpillars, J. Discrete Math. Sci. Cryptogr. 8 (2005) 483-502. [9] B. Effantin, H. Kheddouci, The b-chromatic number of some power graphs, Discrete Math. Theor. Comput. Sci. 6 (2003) 45-54. [10] B. Effantin, H. Kheddouci, Exact values for the b-chromatic number of a power complete k-ary tree, J. Discrete Math. Sci. Cryptogr. 8 (2005) 117-129. [11] R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition, Discrete Mathematics and Its Applications, CRC Press, Boca Raton, 2011. CD О 00 00 о Ö со со и а CD и [12] C.T. Hoang, M. Kouider, On the b-dominating coloring of graphs, Discrete Appl. Math. 152 (2005) 176-186. [13] A. Iranmanesh, I. Gutman, O. Khormali, A. Mahmiani, The edge version of the Wiener index, MATCH. 61 (2009) 663-672. [14] R.W. Irving, D.F. Manlove, The b-chromatic number of a graph, Discrete Appl. Math. 91 (1999) 127-141. [15] M. Jakovac, S. Klavžar, The b-chromatic number of cubic graphs, Graphs Com-bin. 26 (2010) 107-118. [16] M. Jakovac, I. Peterin, On the b-chromatic number of some products, Studia Sci. Math. Hungar. 49 (2012) 156-169. Ф [17] M. Kouider, b-chromatic number of a graph, subgraphs and degrees, Rapport interne LRI 1392. [18] M. Kouider, A. El Sahili, About b-colouring of regular graphs, Rapport de Recherche No 1432, CNRS-Universite Paris Sud-LRI. [19] M. Kouider, M. Maheo, Some bounds for the b-chromatic number of a graph, Discrete Math. 256 (2002) 267-277. [20] M. Kouider, M. Maheo, The b-chromatic number of the Cartesian product of two graphs, Studia Sci. Math. Hungar. 44 (2007) 49-55. [21] M. Kouider, M. Zaker, Bounds for the b-chromatic number of some families of graphs, Discrete Math. 306 (2006) 617-623. [22] J. Kratochvll, Z. Tuza, M. Voigt, On the b-chromatic number of graphs, Lecture Notes in Comput. Sci. 2573 (2002) 310-320.