✦ LIBER ✦

Chromatic Roots and Hamiltonian Paths

✍ Scribed by C. Thomassen

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 89 KB
Volume: 80
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2000.1976

No coin nor oath required. For personal study only.

✦ Synopsis

We present a new connection between colorings and hamiltonian paths: If the chromatic polynomial of a graph has a noninteger root less than or equal to

then the graph has no hamiltonian path. This result is best possible in the sense that it becomes false if t 0 is replaced by any larger number.

📜 SIMILAR VOLUMES

Subdivisions and Chromatic Roots

✍ Jason I. Brown 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 77 KB

Hamiltonian paths and cycles in hypertou

Hamiltonian paths and cycles in hypertournaments

✍ Gutin, Gregory; Yeo, Anders 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB

Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V | = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertour

Powers of Hamiltonian paths in interval

Powers of Hamiltonian paths in interval graphs

✍ Isaak, Garth 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 232 KB 👁 3 views

We give a simple proof that the obvious necessary conditions for a graph to contain the k th power of a Hamiltonian path are sufficient for the class of interval graphs. The proof is based on showing that a greedy algorithm tests for the existence of Hamiltonian path powers in interval graphs. We wi

Mutually independent hamiltonian paths i

Mutually independent hamiltonian paths in star networks

✍ Cheng-Kuan Lin; Hua-Min Huang; Lih-Hsing Hsu; Sheng Bau 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

Trees and unicyclic graphs with hamilton

Trees and unicyclic graphs with hamiltonian path graphs

✍ Xingxing Yu 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## Abstract We prove two conjectures of Broersma and Hoede about path graphs of trees and unicyclic graphs.

Line graphs of bipartite graphs with Ham

Line graphs of bipartite graphs with Hamiltonian paths

✍ Francis K. Bell 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

It is shown that, if t is an integer !3 and not equal to 7 or 8, then there is a unique maximal graph having the path P t as a star complement for the eigenvalue À2: The maximal graph is the line graph of K m,m if t ¼ 2mÀ1, and of K m,m þ1 if t ¼ 2m. This result yields a characterization of L(G ) wh