The Edge Chromatic Number of a Directed/Mixed Multigraph Leonid S. Mel’nikov1 * and Vadim G. Vizing2 * 1 INSTITUTE OF MATHEMATICS SIBERIAN BRANCH OF RAS NOVOSIBIRSK 630090, RUSSIA E-mail: omeln@math.nsc.ru 2 DEPARTMENT OF APPLIED MATHEMATICS ODESSA’S STATE FOOD TECHNOLOGY ACADEMY KANATNAJA STR. 112 ODESSA 270039, UKRAINE Received July 22, 1996; revised December 8, 1998 Abstract: We consider colorings of the directed and undirected edges of a mixed multigraph G by an ordered set of colors. We color each undirected edge in one color and each directed edge in two colors, such that the color of the first half of a directed edge is smaller than the color of the second half. The colors used at the same vertex are all different. A bound for the minimum number of colors needed for such colorings is obtained. In the case where G has only directed * Both authors carried out this work during their visit to Odense University in March, 1995. Correspondence to: Leonid S. Mel’nikov Contract grant sponsor: Russian Foundation for Fundamental Research: 99-0100581 Contract grant sponsor: Danish Research Council. Supported in part by INTAS: grant number # 97-1001 c 1999 John Wiley & Sons, Inc. CCC 0364-9024/99/030267-07 268 JOURNAL OF GRAPH THEORY edges, we provide a polynomal algorithm for coloring G with a minimum number c 1999 John Wiley & Sons, Inc. J Graph Theory of colors. An unsolved problem is formulated. 31: 267–273, 1999 Keywords: edge coloring, regular incidentor coloring oriented multigraph, mixed multigraph, maximum degree, edge chromatic number of multigraph, edge chromatic number of mixed multigraph, arc chromatic number of oriented multigraph, source, sink, polynomial algorithm 1. INTRODUCTION A. Origin of the Problem The problem under consideration appears when studying information transfer systems. In such a system there is a finite number of users sending information to each other either via a server or directly. We assume that the time in the system is discrete, and each channel can transfer a unit of information per time unit. We also assume that the capacity of the server is infinite. The moment of receiving information sent via a server must be later than the moment where information was actually sent. At any fixed moment of time, a user can be connected with at most one other user or server. If the connection between two users is direct (not via a server) then the moments of sending and receiving information coincide. Our goal is to minimize the total time needed for a planned information exchange. This problem was suggested to the first author by Erzin [2]. The case when the use of the server is regulated was considered by Pjatkin [8, 9]. Our problem can be transformed into a special coloring problem for mixed multigraphs. B. Terminology and Notation Notation and definitions not given here can be found in Bondy and Murty [1] or Zykov [17]. We consider finite mixed multigraphs without loops. In a mixed multigraph G with vertex set V (G), the edge set E(G) consists of the arc set A(G) [an element a ∈ A(G) we denote by hx, yi = a and call an arc] and the link set L(G) [an element e ∈ L(G) we denote by [x, y] = e and call a → link]. E(G) = A(G) ∪ L(G). Let us define the pair (v, e) (or [v, e], or hv, ei, or ← hv, ei), where v ∈ V (G) and e ∈ E(G), as an incidentor, if the two elements are incident with each other. (In Zykov’s book [17] we have a slightly different definition of incidentor.) In the case where [x, y] = e ∈ L(G), the incidentors [x, e] and [y, e] are similar. In the case when we have hx, yi = e ∈ A(G), we → ← shall say that hx, ei is an initial incidentor and hy, ei is a final incidentor. Let us denote by I(G) the set of incidentors. I(G) may be divided into three types: → ← ([x, e] ∈ I 0 (G), hx, ei ∈ I + (G), hx, ei ∈ I − (G)). The common notation for all three types of incidentors is (x, e). Let us consider a linear order of a finite set of colors C = {c1 , c2 , . . . , ck }. Mostly we consider these colors as the set of the first k positive integers C = {1, 2, . . . , k}. EDGE CHROMATIC NUMBER 269 A mapping ϕ: I(G) → C we define as a regular coloring of incidentors of a mixed multigraph G, if the following three conditions are fulfilled: → ← (i) if two incidentors hx, ei and hy, ei have a common arc e ∈ A(G), then → ← ϕ(hx, ei) < ϕ(hy, ei); (ii) if two incidentors (x, e1 ) and (x, e2 ) have a common vertex x ∈ V (G), then ϕ((x, e1 )) 6= ϕ((x, e2 )); (iii) if two incidentors [x, e] and [y, e] have a common link e ∈ L(G), then ϕ([x, e]) = ϕ([y, e]). The minimum cardinal k for which a mixed multigraph G has a regular coloring of its incidentors by k colors is the edge chromatic number χm (G) = χ`a (G) of the mixed multigraph G. In the case when A(G) = ∅, we are dealing with the classical edge chromatic number χ` (G) = χ0 (G), the study of which was started by Tait [11], König [7], Shannon [12], Vizing [13–16] and Gupta [4]. For more recent information, see Fiorini and Wilson [13], and Jensen and Toft [6]. On the other hand, when L(G) = ∅, we are dealing with the arc chromatic number χa (G) of a directed multigraph. In the article of Harner and Entringer [5], and later in the article of Poljak and Rödl [10], the authors consider consecutive arc colorings of a digraph G and the corresponding consecutive arc chromatic number c(G). Two arcs of a digraph G are consecutive, if the terminal vertex of one is the initial vertex of the other. The main condition for consecutive arc coloring is that no pair of consecutive arcs have the same color. This condition seems simpler than ours. Of course, the main parameter, used many times before, is the maximum degree ∆(G) of the mixed multigraph G, i.e., the maximum number of edges (arcs and links) that are incident to the same vertex of G. In the proof of the main result, we consider sets of incidentors H , and for such sets we also define the maximum degree ∆(H) as the maximum number of incidentors of H with the same vertex. A vertex x of a set of incidentors H is called a sink ← → (source) of H , if all incidentors of H with x are of the type hx, ei (hx, ei). An arc e is said to belong to H , if both incidentors of e are in H . Two incidentors are said to be disjoint, if they have no element (vertex or edge) in common. 2. MAIN RESULTS A. Edge Chromatic Number of a Mixed Multigraph Let G be a mixed multigraph. The undirected modification G̃ of G is a multigraph with the same vertex set V (G̃) = V (G) and E(G̃) = L(G̃) = {(x, y)|[x, y] ∈ L(G) or hx, yi ∈ A(G) or hy, xi ∈ A(G)}. 270 JOURNAL OF GRAPH THEORY Theorem 2.1.1. Let G and G̃ be a mixed multigraph and its undirected modification, respectively. Then χ`a (G) ≤ χ0 (G̃) + 1. Proof. Let us denote χ0 (G̃) shortly by q . Then E(G̃) = Ẽ1 ∪ Ẽ2 ∪ · · · ∪ Ẽq , Ẽi ∩ Ẽj = ∅ for all different i and j , and any Ẽi is a matching of G̃. If we say that we color some link by color i, then we mean that both incidentors of this link have the same color i. Consider the set E1 of edges from E(G), which corresponds to Ẽ1 . We color all links from E1 and terminal incidentors of all arcs from E1 by color 2. We use the color 1 for coloring the initial incidentors of all arcs from E1 . For k = 2, . . . , q , consider the set Ek of edges from E(G), which correspond to Ẽk . We use color k + 1 for coloring all links and terminal incidentors of all arcs from Ek , but we color every initial incidentor of an arc from Ek using a minimal free color from the set of colors {1, 2, . . . , k}. It is easy to see that such a coloring is regular. This proves Theorem 2.1.1. Let us consider the example of Fig. 1 of a mixed multigraph and its undirected modification with a minimal coloring of each. This example shows us that the bound may be exact, but, in this case, multigraph G̃ satisfies χ0 (G̃) = ∆(G). We have the following conjecture. Conjecture 2.1.1. If for a mixed multigraph G we have χ0 (G̃) > ∆(G), then χ`a (G) ≤ χ0 (G̃). It is easy to show that, if Conjecture 2.1.1 is true, then by Theorem 2.1.1 the next conjecture is true also. Conjecture 2.1.2. ication. Then Let G be a mixed multigraph and G̃ its undirected modif χ`a (G) ≤ max{χ0 (G̃), ∆(G) + 1}. For the case where G and G̃ are isomorphic (i.e., A(G) = ∅), it is trivial that χ`a (G) = χ` (G) = χ0 (G̃). For the case where G is a directed multigraph (i.e., FIGURE 1. EDGE CHROMATIC NUMBER 271 L(G) = ∅), we are able to be more specific and to express χ`a (G) = χa (G) as a function of ∆(G) using some simple properties of G. B. Arc Chromatic Number of an Oriented Multigraph We start with a result demonstrating tightness of upper and lower bounds. Theorem 2.2.1. Then Let G be a directed multigraph with maximum degree ∆(G). ∆(G) ≤ χa (G) ≤ ∆(G) + 1. The lower bound follows immediately from the second condition of the definition of a regular coloring of incidentors. The upper bound is sharp, when G has a source or a sink of degree ∆(G), but only in these cases. Theorem 2.2.2. Let G be a directed multigraph with maximum degree ∆(G). If G has no source of degree ∆(G) and no sink of degree ∆(G), then χa (G) = ∆(G). By adding here arcs to a directed multigraph G of maximum degree ∆(G), it can be changed into a G∗ of maximum degree ∆(G∗ ) = ∆(G) + 1 without sources or sinks of degree ∆(G) + 1. Then, by Theorem 2.2.2, χa (G) ≤ χa (G∗ ) = ∆(G∗ ) = ∆(G) + 1. Hence, Theorem 2.2.1 follows from Theorem 2.2.2. To prove Theorem 2.2.2, we shall prove the following more general statement. Theorem 2.2.3. Let H be a subset of the set of incidentors of a directed multigraph G. Suppose that H has no set of ∆(H) arcs, with both initial and terminal incidentors belonging to H, for which the initial/terminal incidentors form a source/sink of H. Then χa (H) = ∆(H). Proof of Theorem 2.2.3. Let D denote the set of vertices x of G for which there are ∆(H) − 1 arcs in G with both initial and terminal incidentors in H and with x contained in the ∆(H) − 1 initial incidentors of the ∆(H) − 1 arcs. Color all terminal incidentors of H at vertices in D, and all initial incidentors of H not in full edges of H at vertices in D, with the color ∆(H). Let D0 be the set of those vertices in D that are joined by ∆(H) − 1 arcs of G to vertices outside D, where the arcs have both initial and terminal incidentors in H (and where all the initial incidentors have their vertex in D). Let H ∗ be the bipartite graph consisting of these arcs considered as undirected edges. By König’s edge color theorem [7], we may edge-color H ∗ by ∆(H) − 1 colors. It follows that H ∗ has a matching M hitting all of the vertices in D0 . Color the terminal incidentors of the arcs corresponding to the edges of M with the color ∆(H). For all vertices x outside D and without a terminal incidentor already colored ∆(H), color a terminal incidentor at x of some arc with both incidentors in H with the color ∆(H). If such an arc does not exist, color some incidentor at x (of an arc with only one of its incidentors in H ) with the color ∆(H). If no such incidentor exists at x, then do nothing at x. 272 JOURNAL OF GRAPH THEORY This finishes the coloring with color ∆(H). Remove the elements of H that are colored ∆(H). The remaining incidentors satisfy the conditions of the theorem with a smaller maximum degree. By repeating the procedure we finally arrive at a situation where the uncolored incidentors from a system of maximum degree ∆ = 1 and without both the initial and the terminal incidentor of any arc in the system. All the incidentors in this system may be colored with the color 1. This proves Theorem 2.2.3. Let us note that the above proof is constructive and gives a polynomial algorithm for the coloring of the incidentors of a directed multigraph with a minimum number of colors. ACKNOWLEDGMENTS We are grateful to Professor Bjarne Toft for his encouragement and advice while this work was being carried out. Our thanks are due to the Department of Mathematics and Computer Science of Odense University for hospitality. References [1] J. A. Bondy and U. S. R. Murty, Graph theory with applications, MacMillan, London, 1976. [2] A. I. Erzin, personal communication, 1992–1993. [3] S. Fiorini and R. J. Wilson, Edge-colourings of graphs, Pitman, London, 1977. [4] R. P. Gupta, The chromatic index and the degree of a graph, Notices Amer Math Soc 13, (1966), 66T–429. [5] C. C. Harner and R. C. Entringer, Arc colorings of digraphs, J Combin Theory (B) 13 (1972), 219–225. [6] T. R. Jensen and B. Toft, Graph coloring problems, Wiley New York, 1995. [7] D. König, Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Math Ann 77 (1916), 453–465. [8] A. V. Pjatkin, M. Sc. Thesis, Novosibirsk State Univ, 1994. [9] A. V. Pjatkin, Some problems in timetable optimization of information transmission in a local network, Diskretnyi Analiz i Issledovanie Operacii 2, (1995), 74–79 (in Russian). [10] S. Poljak and V. Rödl, On the arc-chromatic number of a digraph, J Combin Theory (B) 31 (1981), 190–198. [11] P. G. Tait, On the coloring of maps, Proc Roy Soc Edinburgh Sect. A 10, (1878–80) 501–503, 729. [12] C. E. Shannon, A theorem on coloring the lines of a network, J Math Phys 28 (1949), 148–151. EDGE CHROMATIC NUMBER 273 [13] V. G. Vizing, On an estimate of the chromatic class of a p-graph, Metody Discret Analiz 3 (1964), 25–30 (in Russian). [14] V. G. Vizing, Critical graphs with a given chromatic class, Metody Diskret Analiz 5 (1965), 9–17 (in Russian). [15] V. G. Vizing, The chromatic class of a multigraph, Kibernetika (Kiev) 3 (1965), 29–39 (in Russian). [16] V. G. Vizing, The chromatic class of a multigraph, Ph.D. Thesis, Inst Math, Siberian Branch, Academy of Sci USSR, Novosibirsk, 1966 (in Russian). [17] A. A. Zykov, Fundamentals of graph theory, BCS Associates, Moscow, Idaho, USA, 1990 (English translation of Russian edition, Nauka, Moscow 1987).

1/--страниц