Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-09T14:40:33.444Z Has data issue: false hasContentIssue false
  • English
  • Français

Distant Vertex Partitions of Graphs

Published online by Cambridge University Press:  01 December 1998

CHRIS JAGGER
CHRIS JAGGER
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, 16 Mill Lane, Cambridge CB2 1SB, England (e-mail: C.N.Jagger@dpmms.cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider the function χ(Gk), defined to be the smallest number of colours that can colour a graph G in such a way that no vertices of distance at most k receive the same colour. In particular we shall look at how small a value this function can take in terms of the order and diameter of G. We get general bounds for this and tight bounds for the cases k=2 and k=3.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 7 , Issue 4 , December 1998 , pp. 413 - 422
Copyright
1998 Cambridge University Press