✦ LIBER ✦

T-colorings of graphs

✍ Scribed by Daphne Der-Fen Liu

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 594 KB
Volume: 101
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90603-d

No coin nor oath required. For personal study only.

✦ Synopsis

Given a finite set T of positive integers containing {0}, a T-coloring of a simple graph G is a nonnegative integer function f defined on the vertex set of G, such that if (u, v} E E(G) then Lf(u) -f (u)l $ T. The T-span of a T-coloring is defined as the difference of the largest and smallest colors used; the T-span of G, se,(G), is the minimum span over all T-colorings of G. It is known that the T-span of G satisfies spr(&(o) ) s se,(G) 6 spr(K,(,)). When T is an r-initial set (Cozzens and Roberts, 1982), or a k multiple of s set (A. Raychaudhuri, 1985), then se,(G) = spr(Kx(& for all graphs G. Using graph homomorphisms and a special family of graphs, we characterize those T's with equality spr(G) = spr(K,(,J for all graphs G. We discover new T's with the same result. Furthermore, we get a necessary and sufficient condition of equality se,(G) = se,(&) for all graphs G with x(G) = m.

📜 SIMILAR VOLUMES

Relative colorings of graphs

✍ Paul C Kainen 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 231 KB

A rainbow about T-colorings for complete

A rainbow about T-colorings for complete graphs

✍ Klaus Jansen 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 700 KB

Given a finite set T of positive integers, with 0 E T, a T-coloring of a graph G = (V, E) is a functionf: V -+ No such that for each {x, y} E E If(x) -f(y)l#T. The T-span is the difference between the largest and smallest colors and the T-span of G is the minimum span over all T-colorings of G. We s

Oriented list colorings of graphs

✍ Zs. Tuza; M. Voigt 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB 👁 1 views

A 2-assignment on a graph G (V,E) is a collection of pairs Lv of allowed colors speci®ed for all vertices v PV. The graph G (with at least one edge) is said to have oriented choice number 2 if it admits an orientation which satis®es the following property: For every 2-assignment there exists a choic

Acrylic improper colorings of graphs

✍ Boiron, P.; Sopena, E.; Vignal, L. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 153 KB 👁 2 views

In this article, we introduce the new notion of acyclic improper colorings of graphs. An improper coloring of a graph is a vertex-coloring in which adjacent vertices are allowed to have the same color, but each color class V i satisfies some condition depending on i. Such a coloring is acyclic if th

Acyclic edge colorings of graphs

✍ Noga Alon; Benny Sudakov; Ayal Zaks 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 102 KB

## Abstract A proper coloring of the edges of a graph __G__ is called __acyclic__ if there is no 2‐colored cycle in __G__. The __acyclic edge chromatic number__ of __G__, denoted by __a′__(__G__), is the least number of colors in an acyclic edge coloring of __G__. For certain graphs __G__, __a′__(_

Face colorings of embedded graphs

✍ Dan Archdeacon 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 498 KB

We characterize those graphs which have at least one embedding into some surface such that the faces can be properly colored in four or fewer colors. Embeddings into both orientable and nonorientable surfaces are considered.