On-line coloring of perfect graphs (Q1375694)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On-line coloring of perfect graphs |
scientific article |
Statements
On-line coloring of perfect graphs (English)
0 references
11 January 1998
0 references
An algorithm is presented which colors on-line \(k\)-colorable perfect graphs with \(n^{10/\log\log n}\) colors. By modifying Vishwanathan's construction a \(\bigl(\log_3 n\bigr)^{k-1}/2^k k^{k-1}\) lower bound is given.
0 references
on-line coloring
0 references
perfect graphs=20
0 references
