Download PDF - On distance local connectivity and vertex distance colouringAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

On distance local connectivity and vertex distance colouring

Authors 1

Affiliations

  1. Department of Mathematics, University of West Bohemia and Institute for Theoretical, Computer Science (ITI), Charles University, Univerzitni 22, 306 14 Pilsen, Czech Republic

Abstract

In this paper, we give some sufficient conditions for distance local connectivity of a graph, and a degree condition for local connectivity of a k-connected graph with large diameter. We study some relationships between t-distance chromatic number and distance local connectivity of a graph and give an upper bound on the t-distance chromatic number of a k-connected graph with diameter d.

Keywords

ENG
degree condition, distance local connectivity, distance chromatic number

Bibliography

  1. P. Baldi, On a generalized family of colourings, Graphs Combin. 6 (1990) 95-110, doi: 10.1007/BF01787722.
  2. J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London and Elsevier, 1976).
  3. G. Chartrand and R.E. Pippert, Locally connected graphs, Cas. pro pestování matematiky 99 (1974) 158-163.
  4. A. Chen, A. Gyárfás and R.H. Schelp, Vertex coloring with a distance restriction, Discrete Math. 191 (1998) 83-90, doi: 10.1016/S0012-365X(98)00094-6.
  5. P. Holub and L. Xiong, On Distance local connectivity and the hamiltonian index, submitted to Discrete Math.
  6. S. Jendrol' and Z. Skupień, Local structures in plane maps and distance colourings, Discrete Math. 236 (2001) 167-177, doi: 10.1016/S0012-365X(00)00440-4.
  7. F. Kramer and H. Kramer, Un problème de coloration des sommets d'un graphe, C.R. Acad. Sci. Paris Sér. A-B 268 (1969) A46-A48.
  8. F. Kramer and H. Kramer H, On the generalized chromatic number, Ann. Discrete Math. 30 (1986) 275-284.
  9. T. Madaras and A. Marcinová, On the structural result on normal plane maps, Discuss. Math. Graph Theory 22 (2002) 293-303, doi: 10.7151/dmgt.1176.
  10. Z. Ryjácek, On a closure concept in claw-free graphs, J. Combin. Theory (B) 70 (1997) 217-224, doi: 10.1006/jctb.1996.1732.
  11. Z. Skupień, Some maximum multigraphs and edge/vertex distance colourings, Discuss. Math. Graph Theory 15 (1995) 89-106, doi: 10.7151/dmgt.1010.
Discussiones Mathematicae Graph Theory
2007/27/2
Export to PBN, Opens in new tab
Pages:
209-227
Main language of publication
English
Received
2005-09-15
Accepted
2007-05-18
Published
2007

DOI: 10.7151/dmgt.1356

Exact and natural sciences