PDF

Discussiones Mathematicae Graph Theory 27(2) (2007) 209-227
DOI: https://doi.org/10.7151/dmgt.1356

ON DISTANCE LOCAL CONNECTIVITY AND VERTEX DISTANCE COLOURING

Premysl Holub

Department of Mathematics
University of West Bohemia and Institute for Theoretical
Computer Science (ITI), Charles University
Univerzitni 22, 306 14 Pilsen, Czech Republic
e-mail: holubpre@kma.zcu.cz

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: degree condition, distance local connectivity, distance chromatic number.

2000 Mathematics Subject Classification: 05C15, 05C75.

References

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

Received 15 September 2005
Revised 18 May 2007
Accepted 18 May 2007