✦ LIBER ✦

Distance Graphs andT-Coloring

✍ Scribed by Gerard J Chang; Daphne D.-F Liu; Xuding Zhu

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 126 KB
Volume: 75
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1998.1881

No coin nor oath required. For personal study only.

✦ Synopsis

We discuss relationships among T-colorings of graphs and chromatic numbers, fractional chromatic numbers, and circular chromatic numbers of distance graphs. We first prove that for any finite integral set T that contains 0, the asymptotic T-coloring ratio R(T ) is equal to the fractional chromatic number of the distance graph G(Z, D), where D=T&[0]. This fact is then used to study the distance graphs with distance sets of the form D m, k =[1, 2, ..., m]&[k]. The chromatic numbers and the fractional chromatic numbers of G(Z, D m, k ) are determined for all values of m and k. Furthermore, circular chromatic numbers of G(Z, D m, k ) for some special values of m and k are obtained.

📜 SIMILAR VOLUMES

Pattern Periodic Coloring of Distance Gr

Pattern Periodic Coloring of Distance Graphs

✍ Xuding Zhu 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 250 KB

Suppose D is a subset of Z. The distance graph G(Z, D) with distance set D is the graph with vertex set Z and two vertices x, y are adjacent if |x& y| # D. We introduce a coloring method for distance graphs, the pattern periodic coloring, and we shall compare this method with other general coloring

Average distance in colored graphs

✍ Peter Dankelmann; Wayne Goddard; Peter Slater 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB

## Abstract For a graph __G__ where the vertices are colored, the __colored distance__ of __G__ is defined as the sum of the distances between all unordered pairs of vertices having different colors. Then for a fixed supply __s__ of colors, __d~s~(G)__ is defined as the minimum colored distance ove

Relation Algebras andt-vertex Condition

Relation Algebras andt-vertex Condition Graphs

✍ J. WojdyŁo 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 120 KB

The scheme associated with a graph is an association scheme iff the graph is strongly regular. Consider the problem of extending such an association scheme to a superscheme. The obstacles can be expressed in terms of t-vertex conditions. If a graph does not satisfy the t-vertex condition, a presuper

Coloring precolored perfect graphs

✍ Kratochv�l, Jan; Seb?, Andr�s 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 2 views

We consider the question of the computational complexity of coloring perfect graphs with some precolored vertices. It is well known that a perfect graph can be colored optimally in polynomial time. Our results give a sharp border between the polynomial and NP-complete instances, when precolored vert

Star coloring of graphs

✍ Guillaume Fertin; André Raspaud; Bruce Reed 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 181 KB

## Abstract A __star coloring__ of an undirected graph __G__ is a proper vertex coloring of __G__ (i.e., no two neighbors are assigned the same color) such that any path of length 3 in __G__ is not bicolored. The __star chromatic number__ of an undirected graph __G__, denoted by χ~s~(__G__), is the

Coloring quasi-line graphs

✍ Maria Chudnovsky; Alexandra Ovetsky 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract A graph __G__ is a quasi‐line graph if for every vertex __v__, the set of neighbors of __v__ can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. A theorem of Shannon's implies that if __G__ is a line graph, then