𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Vertex colorings with a distance restriction

✍ Scribed by Guantao Chen; András Gyárfás; R.H. Schelp

Book ID
104114127
Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
787 KB
Volume
191
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let d, k be any two positive integers with k > d > 0. We consider a k-coloring of a graph G such that the distance between each pair of vertices in the same color-class is at least d. Such graphs are said to be (k,d)-colorable. The object of this paper is to determine the maximum size of (k, 3)-colorable, (k, 4)-colorable, and (k, k-1 )-colorable graphs. Sharp results are obtained for both (k, 3)-colorable and (k, k-1 )-colorable graphs, while the results obtained for (k, 4)-colorable graphs are close to the truth.

📜 SIMILAR VOLUMES

Vertex-distinguishing proper edge-colori
Vertex-distinguishing proper edge-colorings
✍ Burris, A. C.; Schelp, R. H. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 146 KB

An edge-coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for a vertex-distinguishing proper edge-coloring of a simple graph G is denoted by χ s (G). A simple count shows that χ s (G) ≥ max{(

On a theorem about vertex colorings of g
On a theorem about vertex colorings of graphs
✍ Claudio Bernardi 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 121 KB

Lawrence [2, Theorem 3] and Borodin and Kostochka [1, Lemma 2' 1 both give the same theorem about vertex colorings of graphs (Corollary 1 below). But Lawrence's proof, although powerful, is a little long, and Borodin and Kostoehka state the result without a proof.