✦ LIBER ✦

The mean chromatic number of paths and cycles

✍ Scribed by Martin Anthony; Norman Biggs

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 245 KB
Volume: 120
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90581-d

No coin nor oath required. For personal study only.

✦ Synopsis

The mean chromatic number of a graph is defined. This is a measure of the expected performance of the greedy vertex-colouring algorithm when each ordering of the vertices is equally likely. In this note, we analyse the asymptotic behaviour of the mean chromatic number for the paths and even cycles, using generating function techniques.

📜 SIMILAR VOLUMES

Induced Cycles and Chromatic Number

✍ A.D. Scott 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 87 KB

We prove that, for any pair of integers k, l 1, there exists an integer N(k, l ) such that every graph with chromatic number at least N(k, l ) contains either K k or an induced odd cycle of length at least 5 or an induced cycle of length at least l.

On the mean chromatic number

✍ Martin Anthony 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 209 KB

The mean chromatic number of a graph is a measure of the expected performance of the greedy vertex-colouring algorithm when each ordering of the vertices is equally likely. Some results on the value of the mean chromatic number and its asymptotic behaviour are presented.

Chromaticity of the complements of paths

Chromaticity of the complements of paths and cycles

✍ Qingyan Du 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 742 KB

Path chromatic numbers of graphs

✍ Jin Akiyama; Hiroshi Era; Severino V. Gervacio; Mamoru Watanabe 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

Cycle length parities and the chromatic

Cycle length parities and the chromatic number

✍ Christian Löwenstein; Dieter Rautenbach; Ingo Schiermeyer 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB

## Abstract In 1966 Erdös and Hajnal proved that the chromatic number of graphs whose odd cycles have lengths at most __l__ is at most __l__+1. Similarly, in 1992 Gyárfás proved that the chromatic number of graphs which have at most __k__ odd cycle lengths is at most 2__k__+2 which was originally c

Digraphs with maximum number of paths an

Digraphs with maximum number of paths and cycles

✍ Yehoshua Perl 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 482 KB