𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the mean chromatic number

✍ Scribed by Martin Anthony

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
209 KB
Volume
125
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

The mean chromatic number of paths and c
The mean chromatic number of paths and cycles
✍ Martin Anthony; Norman Biggs πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 245 KB

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,

On the chromatic number of disk graphs
On the chromatic number of disk graphs
✍ Malesi?ska, Ewa; Piskorz, Steffen; WeiοΏ½enfels, Gerhard πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 172 KB πŸ‘ 2 views

Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their

A note on the star chromatic number
A note on the star chromatic number
✍ J. A. Bondy; Pavol Hell πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 176 KB πŸ‘ 1 views

## Abstract A. Vince introduced a natural generalization of graph coloring and proved some basic facts, revealing it to be a concept of interest. His work relies on continuous methods. In this note we make some simple observations that lead to a purely combinatorial treatment. Our methods yield sho

Recent results on the total chromatic nu
Recent results on the total chromatic number
✍ A.J.W. Hilton πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 626 KB

Hilton, A.J.W., Recent results on the total chromatic number, Discrete Mathematics 111 (1993) 323-331. We give a survey of various recent results concerning the total chromatic number of simple graphs.