✦ LIBER ✦

4-chromatic graphs with large odd girth

✍ Scribed by Nguyen Van Ngoc; Zsolt Tuza

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 251 KB
Volume: 138
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00221-4

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

List edge chromatic number of graphs wit

List edge chromatic number of graphs with large girth

✍ A.V. Kostochka 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 785 KB

Kostochka, A.V., List edge chromatic number of graphs with large girth, Discrete Mathematics 101 (1992) 189-201. It is shown that the list edge chromatic number of any graph with maximal degree A and girth at least 8A(ln A + 1.1) is equal to A + 1 or to A. Conjecture 1. The list edge chromatic numbe

(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

The circular chromatic number of series-

The circular chromatic number of series-parallel graphs with large girth

✍ Chien, Chihyun; Zhu, Xuding 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It was proved by Hell and Zhu that, if G is a series-parallel graph of girth at least 2 (3k -1)/2 , then χ c (G) ≤ 4k/(2k -1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series-parallel graph G of girth 2 (3k -1)/2 -1 such that χ c (G) > 4k/(2k -1)

Smallest regular graphs with prescribed

Smallest regular graphs with prescribed odd girth

✍ Guo-Hui Zhang 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 484 KB 👁 1 views

## Abstract The odd girth of a graph __G__ gives the length of a shortest odd cycle in __G.__ Let __f(k,g)__ denote the smallest __n__ such that there exists a __k__‐regular graph of order __n__ and odd girth __g.__ The exact values of __f(k,g)__ are determined if one of the following holds: __k__

Extremal Regular Graphs with Prescribed

Extremal Regular Graphs with Prescribed Odd Girth

✍ G.H. Zhang 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 496 KB

The odd girth of a graph \(G\) gives the length of a shortest odd cycle in \(G\). Let \(f(k, g)\) denote the smallest \(n\) such that there exists a \(k\)-regular graph of order \(n\) and odd girth \(g\). It is known that \(f(k, g) \geqslant k g / 2\) and that \(f(k, g)=k g / 2\) if \(k\) is even. T

Short odd cycles in 4-chromatic graphs

✍ Nilli, A. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB 👁 3 views

It is shown that any 4-chromatic graph on n vertices contains an odd cycle of length smaller than √ 8n.