Some maximum multigraphs and edge/vertex distance colourings

• Autorzy: Zdzisław Skupień
• Języki publikacji: EN

Abstrakty

EN

Shannon-Vizing-type problems concerning the upper bound for a distance chromatic index of multigraphs G in terms of the maximum degree Δ(G) are studied. Conjectures generalizing those related to the strong chromatic index are presented. The chromatic d-index and chromatic d-number of paths, cycles, trees and some hypercubes are determined. Among hypercubes, however, the exact order of their growth is found.

Słowa kluczowe

EN

(strong) chromatic index   chromatic number   matching   hypercube   error-correcting code   asymptotics  

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C35: Extremal problems
• 94B05: Linear codes, general

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 1995
• Tom: 15
• Numer: 1
• Strony: 89-106

Daty

wydano

1995

otrzymano

1994-11-30

Twórcy

autor

Zdzisław Skupień

• Institute of Math. AGH, al. Mickiewicza 30, 30-059 Kraków, Poland

Bibliografia

• [1] L.D. Andersen, The strong chromatic index of a cubic graph is at most 10, in: J. Nesetril, ed., Topological, Algebraical and Combinatorial Structures; Frolik's Memorial Volume. Discrete Math. 108 (1992) 231-252; reprinted in Vol. 8 of Topics in Discrete Math. (Elsevier, 1993).
• [2] J.C. Bermond, J. Bond, M. Paoli and C. Peyrat, Graphs and interconnection networks: diameter and vulnerability, in: Surveys in Combinatorics, Proc. Ninth British Combin. Conf. (London Math. Soc., Lect. Notes Series 82, 1983) 1-30.
• [3] F.R.K. Chung, A. Gyarfas, Zs. Tuza and W.T. Trotter, The maximum number of edges in 2K₂-free graphs of bounded degree, Discrete Math. 81 (1990) 129-135, doi: 10.1016/0012-365X(90)90144-7.
• [4] R.J. Faudree, A. Gyarfas, R.H. Schelp and Zs. Tuza, Induced matchings in bipartite graphs, Discrete Math. 78 (1989) 83-87, doi: 10.1016/0012-365X(89)90163-5.
• [5] R.J. Faudree, R.H. Schelp, A. Gyarfas and Zs. Tuza, The strong chromatic index of graphs, Ars Combinat. 29-B (1990) 205-211.
• [6] P. Horák, H. Qing and W.T. Trotter, Induced matchings in cubic graphs, J. Graph Theory 17 (1993) 151-160. [Communicated at 1991 Conf. in Zemplinska Sirava (CS).], doi: 10.1002/jgt.3190170204.
• [7] F. Kramer, Sur le nombre chromatique K(p,G) des graphes, Rev. Franç. Automat. Inform. Rech. Opérat. 6 (1972) 67-70; Zbl. 236,05105
• [8] F. Kramer and H. Kramer, On the generalized chromatic number, in: Combinatorics '84, Proc. Int. Conf. Finite Geom. Comb. Struct., Bari/Italy, 1984 (Ann. Discrete Math. 30, 1986) 275-284; Zbl. 601,05020.
• [9] F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes (North-Holland, Amsterdam et al., 1981).
• [10] C.E. Shannon, A theorem on coloring the lines of a network, J. Math. Phys. 28 (1949) 148-151.
• [11] E. Sidorowicz and Z. Skupień, A joint article in preparation.
• [12] 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, Enschede, 1993) 173-175.
• [13] V.G. Vizing, Chromatic class of a multigraph [Russian], Kibernetika 3 (1965) 29-39.
• [14] S. Wagon, (Note) A bound on the chromatic number of graphs without certain induced subgraphs, J. Combin. Theory (B) 29 (1978) 345-346, doi: 10.1016/0095-8956(80)90093-3.

Identyfikatory

DOI

10.7151/dmgt.1010