✦ LIBER ✦

A bound on the chromatic number using the longest odd cycle length

✍ Scribed by Sreyash Kenkre; Sundar Vishwanathan

Publisher: John Wiley and Sons
Year: 2007
Tongue: English
Weight: 120 KB
Volume: 54
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20209

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let G be a non‐bipartite graph with ℓ as the length of the longest odd cycle. Erdös and Hajnal proved that χ(G) ≤ ℓ + 1. We show that the only graphs for which this is tight are those that contain K~ℓ~ + 1 and further, if G does not contain K~ℓ~ then χ(G) ≤ ℓ −1. We then extend these results and show that if we exclude a large clique, we can prove better bounds for χ(G) as a function of ℓ. Specifically, we show that if ω(G) ≤ ⌈ℓ(1 − ϵ)⌉ for ϵ ≤ 4/15, then χ(G) ≤ ⌈ℓ(1 − ϵ/2)⌉. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 267–276, 2007

📜 SIMILAR VOLUMES

A New Bound on the Cyclic Chromatic Numb

A New Bound on the Cyclic Chromatic Number

✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 116 KB

In 1969, Ore and Plummer defined an angular coloring as a natural extension of the Four Color Problem: a face coloring of a plane graph where faces meeting even at a vertex must have distinct colors. A natural lower bound is the maximum degree 2 of the graph. Some graphs require w 3 2 2x colors in a

A new upper bound on the cyclic chromati

A new upper bound on the cyclic chromatic number

✍ O. V. Borodin; H. J. Broersma; A. Glebov; J. van den Heuvel 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB 👁 1 views

## Abstract A cyclic coloring of a plane graph is a vertex coloring such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a graph is its cyclic chromatic number χ^__c__^. Let Δ^\*^ be the maximum face degree of a graph. There exist

A lower bound on the chromatic number of

A lower bound on the chromatic number of a graph

✍ B. R. Myers; R. Liu 📂 Article 📅 1971 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 1 views

A Note on the m-Bounded Chromatic Number

A Note on the m-Bounded Chromatic Number of a Tree

✍ Bor-Liang Chen; Ko-Wei Lih 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 77 KB

The \(m\)-bounded chromatic number of a graph \(G\) is the smallest number of colors required for a proper coloring of \(G\) in which each color is used at most \(m\) times. We will establish an exact formula for the \(m\)-bounded chromatic number of a tree.

A Lower Bound for the One-Chromatic Numb

A Lower Bound for the One-Chromatic Number of a Surface

✍ V.P. Korzhik 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 487 KB

On an upper bound for the harmonious chr

On an upper bound for the harmonious chromatic number of a graph

✍ Zhikang Lu 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph that has been given by Sin‐Min Lee and John Mitchem is improved.