вход по аккаунту



код для вставкиСкачать
The Edge Chromatic
Number of a
Leonid S. Mel’nikov1 * and Vadim G. Vizing2 *
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,
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
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
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.
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}.
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.
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)}.
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.,
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.
Arc Chromatic Number of an Oriented Multigraph
We start with a result demonstrating tightness of upper and lower bounds.
Theorem 2.2.1.
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.
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.
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.
[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.
[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).
Без категории
Размер файла
181 Кб
Пожаловаться на содержимое документа