𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Computing independent sets in graphs with large girth

✍ Scribed by Owen J. Murphy

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
377 KB
Volume
35
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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

4-chromatic graphs with large odd girth
4-chromatic graphs with large odd girth
✍ Nguyen Van Ngoc; Zsolt Tuza πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 251 KB

It is known that the Mycielski graph can be generalized to obtain an infinite family of 4-chromatic graphs with no short odd cycles. The first proof of this result, due to Stiebitz, applied the topological method of Lov~sz. The proof presented here is elementary combinatorial.