𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Chromatic number, girth and maximal degree

✍ Scribed by Béla Bollobás

Publisher
Elsevier Science
Year
1978
Tongue
English
Weight
544 KB
Volume
24
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

It is proved that for every k a4 there is a A(k) such that for eve:y g there is a graph G with maximal degree at most A(k), chromatic number at least k and girth at least g. In fact, for a fixed k, the restriction of the maximal degree to A(k) does not seem to slow down the ptiih of the maximal girth of a k-chromatic graph of order n as n -+ w

📜 SIMILAR VOLUMES

Girth and fractional chromatic number of
Girth and fractional chromatic number of planar graphs
✍ Amir Pirnazar; Daniel H. Ullman 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB 👁 1 views

## Abstract In 1959, even before the Four‐Color Theorem was proved, Grötzsch showed that planar graphs with girth at least 4 have chromatic number at the most 3. We examine the fractional analogue of this theorem and its generalizations. For any fixed girth, we ask for the largest possible fraction

Maximal antiramsey graphs and the strong
Maximal antiramsey graphs and the strong chromatic number
✍ S. A. Burr; P. Erdös; R. L. Graham; V. T. Sós 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 916 KB

A typical problem arising in Ramsey graph theory is the following. For given graphs G and L, how few colors can be used to color the edges of G in order that no monochromatic subgraph isomorphic to L is formed? In this paper w e investigate the opposite extreme. That is, w e will require that in any

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

Hadwiger number and chromatic number for
Hadwiger number and chromatic number for near regular degree sequences
✍ Neil Robertson; Zi-Xia Song 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB

## Abstract We consider a problem related to Hadwiger's Conjecture. Let __D__=(__d__~1~, __d__~2~, …, __d__~__n__~) be a graphic sequence with 0⩽__d__~1~⩽__d__~2~⩽···⩽__d__~__n__~⩽__n__−1. Any simple graph __G__ with __D__ its degree sequence is called a realization of __D__. Let __R__[__D__] denot

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)