✦ LIBER ✦

On the Chromatic Roots of Generalized Theta Graphs

✍ Scribed by Jason I. Brown; Carl Hickman; Alan D. Sokal; David G. Wagner

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 242 KB
Volume: 83
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2001.2057

No coin nor oath required. For personal study only.

✦ Synopsis

The generalized theta graph G s1, ..., sk consists of a pair of endvertices joined by k internally disjoint paths of lengths s 1 , ..., s k \ 1. We prove that the roots of the chromatic polynomial p(G s1, ..., sk , z) of a k-ary generalized theta graph all lie in the disc |z -1| [ [1+o(1)] k/log k, uniformly in the path lengths s i . Moreover, we prove that G 2, ..., 2 4 K 2, k indeed has a chromatic root of modulus [1+o(1)] k/log k. Finally, for k [ 8 we prove that the generalized theta graph with a chromatic root that maximizes |z -1| is the one with all path lengths equal to 2; we conjecture that this holds for all k.

📜 SIMILAR VOLUMES

On the chromatic number of the general K

On the chromatic number of the general Kneser-graph

✍ P. Frankl 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

On the Roots of Chromatic Polynomials

✍ Jason I. Brown 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 158 KB

It is proved that the chromatic polynomial of a connected graph with n vertices and m edges has a root with modulus at least (m&1)Â(n&2); this bound is best possible for trees and 2-trees (only). It is also proved that the chromatic polynomial of a graph with few triangles that is not a forest has a

A generalized construction of chromatic

A generalized construction of chromatic index critical graphs from bipartite graphs

✍ Michael Plantholt 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 378 KB

W e prove that any graph with maximum degree n which can be obtained by removing exactly 2n -1 edges from the join K? -K, ,, is n-critical This generalizes special constructions of critical graphs by S Fiorini and H P Yap, and suggests a possible extension of another general construction due to Yap

The generalized acyclic edge chromatic n

The generalized acyclic edge chromatic number of random regular graphs

✍ Stefanie Gerke; Catherine Greenhill; Nicholas Wormald 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB 👁 1 views

## Abstract The __r__‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle __C__ has at least min(|__C__|, __r__) colors. We show that (__r__ − 2)__d

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 chromatic number of the product o

On the chromatic number of the product of graphs

✍ D. Duffus; B. Sands; R. E. Woodrow 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 429 KB 👁 1 views