𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Polyhedral Approach for Graph Coloring1

✍ Scribed by Isabel Méndez Díaz -; Paula Zabala

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
255 KB
Volume
7
Category
Article
ISSN
1571-0653

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On Markov Chains for Randomly H-Coloring
On Markov Chains for Randomly H-Coloring a Graph
✍ Colin Cooper; Martin Dyer; Alan Frieze 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 144 KB

Let H = W F be a graph without multiple edges, but with the possibility of having loops. Let G = V E be a simple graph. A homomorphism c is a map c V → W with the property that v w ∈ E implies that c v c w ∈ F. We will often refer to c v as the color of v and c as an H-coloring of G. We consider the

A special k-coloring for a connected k-c
A special k-coloring for a connected k-chromatic graph
✍ Guantao Chen; Richard H. Schelp; Warren E. Shreve 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 293 KB

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number x(G) --k can be properly vertex colored by k colors so that for each pair of vertices x0 and x~ in any color class there exist