DMGT

Discussiones Mathematicae Graph Theory 19(2) (1999) 251-252
DOI: https://doi.org/10.7151/dmgt.1101

ON DISTANCE EDGE COLOURINGS OF A CYCLIC MULTIGRAPH

Zdzisław Skupień

Faculty of Applied Mathematics
University of Mining and Metallurgy AGH
al. Mickiewicza 30, 30-059 Kraków, Poland
e-mail: skupien@uci.agh.edu.pl

We shall use the distance chromatic index defined by the present author in early nineties, cf. [5] or [4] of 1993. The edge distance of two edges in a multigraph M is defined to be their distance in the line graph L(M) of M. Given a positive integer d, define the d⁺-chromatic index of the multigraph M, denoted by q^(d)(M), to be equal to the chromatic number χ of the dth power of the line graph L(M),

q^(d)(M) = χ(L(M)^d).

Then the colour classes are matchings in M with edges at edge distance larger than d apart.

Call C to be a cyclic multigraph if C consists of a cycle on n vertices with possibly more than one edge between two consecutive vertices.

The following problem was presented in [6].

Problem. Given an integer d ≥ 2 and a cyclic multigraph C, find (or estimate) q^(d)(C), the d⁺-chromatic index of C.

In other words, generalize the following formula due to Berge [1] for the ordinary chromatic index (q = q¹)

q(C) = Δ(C)

⎧
⎪
⎪
⎨
⎪
⎪
⎩

max

⎧
⎨
⎩

Δ(C),

⎡
⎢
⎢

e(C)

⎣[n/2] ⎦

⎤
⎥
⎥

⎫>
⎬
⎭

for odd n,

for even n,

where Δ(C) and e(C) are the maximum degree among vertices and the size of C, respectively.

Remarks 1. 2⁺-chromatic index q⁽²⁾ is known under the name strong chromatic index, estimations of q⁽²⁾(C) being studied in [2,3].

2. In [5] it is proved that

q^(d)(^pC_n) =

⎧
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎝

if n ≤ 2d+1,

⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢

⎢
⎢
⎢
⎢
⎣

d+1

⎥
⎥
⎥
⎥
⎦

⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥

if n ≥ d+1

where ^pC_n is the cyclic multigraph C with all edge multiplicities equal to p.

3. Let M be a loopless multigraph whose underlying graph is a forest. Then q^(d)(M), the d⁺-chromatic index of M, can be seen to be equal to the diameter-d cluster (or diameter-d edge-clique) number of M (i.e., the density of the dth power, L(M)^d, of the line graph of M). This extends the known corresponding results on a tree [5] and on q⁽²⁾(M) in [2].

References

[1]	C. Berge, Graphs and Hypergraphs (North-Holland, 1973).
[2]	P. Gvozdjak, P. Horák, M. Meszka and Z. Skupień, Strong chromatic index for multigraphs, Utilitas Math., to appear.
[3]	P. Gvozdjak, P. Horák, M. Meszka and Z. Skupień, On the strong chromatic index of cyclic multigraphs, Discrete Appl. Math., to appear.
[4]	Z. Skupień, Some maximum multigraphs and chromatic d-index, in: U. Faigle and C. Hoede, eds., 3rd Twente Workshop on Graphs and Combinatorial Optimization, (Fac. Appl. Math. Univ. Twente) Memorandum No. 1132 (1993) 173-175.
[5]	Z. Skupień, Some maximum multigraphs and edge/vertex distance colourings, Discuss. Math. Graph Theory 15 (1995) 89-106, doi: 10.7151/dmgt.1010.
[6]	Z. Skupień, Problem 4, (on the list of problems presented at workshop:) Cycles and Colourings held at Stará Lesná, Slovakia, September 10-15, 1995.

Received 21 March 1999
Revised 13 September 1999