𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Fractional colorings with large denominators

✍ Scribed by David C. Fisher

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
299 KB
Volume
20
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The m‐chromatic number Ο‡~m~(G) of a graph G is the fewest colors needed so each node has m colors and no color appears on adjacent nodes. The fractional chromatic number is Ο‡*(G)=lim~mβ†’βˆž~Ο‡~m~(G)/m. Let m(G) be the least m so that Ο‡* (G) = Ο‡~m~(G)/m. For n node graphs, ChvΓ‘tal, Garey and Johnson showed m(G) ≦ n^n/2^ and gave example, where m(G) is asymptotically magnified image. This note gives examples where m(G) is asymptotically Ξ»^n^, where Ξ» β‰ˆοΈ 1.346193. Β© 1995 John Wiley & Sons, Inc.

πŸ“œ SIMILAR VOLUMES

Total colorings of planar graphs with la
Total colorings of planar graphs with large maximum degree
✍ Borodin, O. V.; Kostochka, A. V.; Woodall, D. R. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 97 KB πŸ‘ 3 views

It is proved that a planar graph with maximum degree βˆ† β‰₯ 11 has total (vertex-edge) chromatic number βˆ† + 1.

UniquelyH-colorable graphs with large gi
UniquelyH-colorable graphs with large girth
✍ Zhu, Xuding πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 498 KB πŸ‘ 2 views

Suppose G and H are graphs. We say G is H-colorable if there is a homomorphism (edge-preserving vertex mapping) from G to H. We say a graph G is uniquely H-colorable if there is an onto homomorphism c from G to H, and any other homomorphism from G to H is the composition o o c of c with an automorph

(2 + ?)-Coloring of planar graphs with l
(2 + ?)-Coloring of planar graphs with large odd-girth
✍ Klostermeyer, William; Zhang, Cun Quan πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 258 KB πŸ‘ 3 views

The odd-girth of a graph is the length of a shortest odd circuit. A conjecture by Pavol Hell about circular coloring is solved in this article by showing that there is a function f ( ) for each : 0 < < 1 such that, if the odd-girth of a planar graph G is at least f ( ), then G is (2 + )-colorable. N