Some maximum multigraphs and edge/vertex distance colourings

Zdzisław Skupień

Discussiones Mathematicae Graph Theory (1995)

  • Volume: 15, Issue: 1, page 89-106
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Zdzisław Skupień. "Some maximum multigraphs and edge/vertex distance colourings." Discussiones Mathematicae Graph Theory 15.1 (1995): 89-106. <http://eudml.org/doc/270722>.

@article{ZdzisławSkupień1995,
abstract = {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.},
author = {Zdzisław Skupień},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {(strong) chromatic index; chromatic number; matching; hypercube; error-correcting code; asymptotics; distance colourings; chromatic index; multigraph; line graph; maximum degree; trees; cycles},
language = {eng},
number = {1},
pages = {89-106},
title = {Some maximum multigraphs and edge/vertex distance colourings},
url = {http://eudml.org/doc/270722},
volume = {15},
year = {1995},
}

TY - JOUR
AU - Zdzisław Skupień
TI - Some maximum multigraphs and edge/vertex distance colourings
JO - Discussiones Mathematicae Graph Theory
PY - 1995
VL - 15
IS - 1
SP - 89
EP - 106
AB - 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.
LA - eng
KW - (strong) chromatic index; chromatic number; matching; hypercube; error-correcting code; asymptotics; distance colourings; chromatic index; multigraph; line graph; maximum degree; trees; cycles
UR - http://eudml.org/doc/270722
ER -

References

top
  1. [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). Zbl0756.05050
  2. [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. Zbl0525.05018
  3. [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. Zbl0698.05039
  4. [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. Zbl0709.05026
  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. Zbl0721.05018
  6. [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. Zbl0787.05038
  7. [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 Zbl0236.05105
  8. [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. [9] F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes (North-Holland, Amsterdam et al., 1981). 
  10. [10] C.E. Shannon, A theorem on coloring the lines of a network, J. Math. Phys. 28 (1949) 148-151. Zbl0032.43203
  11. [11] E. Sidorowicz and Z. Skupień, A joint article in preparation. 
  12. [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. [13] V.G. Vizing, Chromatic class of a multigraph [Russian], Kibernetika 3 (1965) 29-39. 
  14. [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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.