𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the chromatic number of integral circulant graphs

✍ Scribed by Aleksandar Ilić; Milan Bašić

Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
395 KB
Volume
60
Category
Article
ISSN
0898-1221

No coin nor oath required. For personal study only.

✦ Synopsis

Integral circulant graphs are a generalization of unitary Cayley graphs, recently studied by Klotz and Sander. The integral circulant graph X n (D) has vertices 0, 1, . . . , n -1, and two vertices a and b are adjacent iff gcd(xy, n) ∈ D, where D ⊆ {d :

Circulant graphs have various applications in the design of interconnection networks in parallel and distributed computing, while integral graphs play an important role in modeling quantum spin networks supporting the perfect state transfer. Integral circulant graphs also found applications in molecular graph energy. In this paper we deal with the chromatic number of integral circulant graphs and investigate the conjecture proposed in [W. Klotz, T. Sander, Some properties of unitary Cayley graphs, Electron. J. Combin.

14 (2007) #R45

] that the chromatic number divides the order of X n (D). For the integral circulant graph with two divisors, sharp upper and lower bounds for the chromatic number are established; if one of the divisors is equal to one, the chromatic number is explicitly determined. For |D| ≥ 3, we construct a family of counterexamples using exhaustive search algorithm for graph coloring and disprove the conjecture in this case.

📜 SIMILAR VOLUMES

On the chromatic number of disk graphs
On the chromatic number of disk graphs
✍ Malesi?ska, Ewa; Piskorz, Steffen; Wei�enfels, Gerhard 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB 👁 2 views

Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their

On the cost-chromatic number of graphs
On the cost-chromatic number of graphs
✍ John Mitchem; Patrick Morriss 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 566 KB

We consider vertex colorings in which each color has an associated cost, incurred each time the color is assigned to a vertex. For a given set of costs, a minimum-cost coloring is a vertex coloring which makes the total cost of coloring the graph as small as possible. The cost-chromatic number of a

On the chromatic number of cube-like gra
On the chromatic number of cube-like graphs
✍ Charles Payan 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 343 KB

A cube-like graph is a graph whose vertices are all 2" subsets of a set E of cardinality n, in which two vertices are adjacent if their symmetric difference is a member of a given specified collection of subsets of E. Many authors were interested in the chromatic number of such graphs and thought it

On the chromatic number of special dista
On the chromatic number of special distance graphs
✍ M. Voigt; H. Walther 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 153 KB

## A b&act Voigt, M. and H. Walther, On the chromatic number of special distance graphs, Discrete Mathematics 97 (1991) 395-397. For all 12 10 and u 2 1' -61+ 3 the chromatic number is proved to be 3 for distance graphs with all integers as vertices, and edges only if the vertices are at distance

On bounding the chromatic number of L-gr
On bounding the chromatic number of L-graphs
✍ Sean McGuinness 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 585 KB

We show that the intersection graph of a collection of subsets of the plane, where each subset forms an "L" shape whose vertical stem is infinite, has its chromatic number 1 bounded by a function of the order of its largest clique w, where it is shown that ;1<2"4'3"4"'~'-". This proves a special cas