A lower bound on the chromatic number of Mycielski graphs (Q5937920)
From MaRDI portal
scientific article; zbMATH DE number 1621229
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A lower bound on the chromatic number of Mycielski graphs |
scientific article; zbMATH DE number 1621229 |
Statements
A lower bound on the chromatic number of Mycielski graphs (English)
0 references
28 November 2001
0 references
The family of Mycielski graphs is widely used for testing graph algorithms. This paper presents a new lower bound on the chromatic numbers of Mycielski graphs. This bound is based on a correspondence between the coloring problem for Mycielski graphs and a multiprocessor task scheduling problem. The present bound is tight for the first eight Mycielski graphs.
0 references
lower bound of chromatic number
0 references
Mycielski graph
0 references
multiprocessor task scheduling problem
0 references
