𝔖 Bobbio Scriptorium
✦   LIBER   ✦

(d,1)-total labeling of graphs with a given maximum average degree

✍ Scribed by Mickaël Montassier; André Raspaud

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
166 KB
Volume
51
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The (d,1)‐total number $\lambda _{d}^{T}(G)$ of a graph G is the width of the smallest range of integers that suffices to label the vertices and the edges of G so that no two adjacent vertices have the same color, no two incident edges have the same color, and the distance between the color of a vertex and its incident edges is at least d. In this paper, we prove that $\lambda_{d}^{T}(G) \leq \Delta (G) + 2d - 2$ for connected graphs with a given maximum average degree. © 2005 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Total colorings of planar graphs with la
Total colorings of planar graphs with large maximum degree
✍ Borodin, O. V.; Kostochka, A. V.; Woodall, D. R. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 3 views

It is proved that a planar graph with maximum degree ∆ ≥ 11 has total (vertex-edge) chromatic number ∆ + 1.

A Note on Large Graphs of Diameter Two a
A Note on Large Graphs of Diameter Two and Given Maximum Degree
✍ Brendan D McKay; Mirka Miller; Jozef Širáň 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 242 KB

Let vt(d, 2) be the largest order of a vertex-transitive graph of degree d and diameter 2. It is known that vt(d, 2)=d 2 +1 for d=1, 2, 3, and 7; for the remaining values of d we have vt(d, 2) d 2 &1. The only known general lower bound on vt(d, 2), valid for all d, seems to be vt(d, 2) w(d+2)Â2x W(d