✦ LIBER ✦

List edge chromatic number of graphs with large girth

✍ Scribed by A.V. Kostochka

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 785 KB
Volume: 101
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90602-c

No coin nor oath required. For personal study only.

✦ Synopsis

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 number lee of any graph G does not exceed A(G) + 1. Conjecture 2. The list edge chromatic number of any multigraph is equal to its edge chromatic number (i.e. chromatic index). The notion of list colouring was also independently introduced by Erdiis, Rubin and Taylor [4], and Conjecture 2-by Albertson and Tucker. Conjecture 1 implies that Total Colouring Conjecture is 'almost true'. Conjectures 1 and 2 are proved only for very small classes of graphs: snarks, trees, cycles (cf. [3]), planar graphs with maximal degree at least 9 [2]. As far as we know the best general bounds for ZeX(G) and Q(G) are the following.

📜 SIMILAR VOLUMES

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)

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.

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

Domination number of cubic graphs with l

Domination number of cubic graphs with large girth

✍ Daniel Král'; Petr Škoda; Jan Volec 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

We show that every n-vertex cubic graph with girth at least g have domination number at most 0.299871n+O(n / g) < 3n / 10+O(n / g) This research was done when the Petr Škoda was a student of

Edge-face chromatic number and edge chro

Edge-face chromatic number and edge chromatic number of simple plane graphs

✍ Rong Luo; Cun-Quan Zhang 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB

## Abstract Given a simple plane graph __G__, an edge‐face __k__‐coloring of __G__ is a function ϕ : __E__(__G__) ∪ __F__(G) → {1,…,__k__} such that, for any two adjacent or incident elements __a__, __b__ ∈ __E__(__G__) ∪ __F__(__G__), ϕ(__a__) ≠ ϕ(__b__). Let χ~e~(__G__), χ~ef~(__G__), and Δ(__G_

Acyclic edge chromatic number of outerpl

Acyclic edge chromatic number of outerplanar graphs

✍ Jian-Feng Hou; Jian-Liang Wu; Gui-Zhen Liu; Bin Liu 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 176 KB

## Abstract A proper edge coloring of a graph __G__ is called acyclic if there is no 2‐colored cycle in __G__. The acyclic edge chromatic number of __G__, denoted by χ(__G__), is the least number of colors in an acyclic edge coloring of __G__. In this paper, we determine completely the acyclic edge