✦ LIBER ✦

Coloring inductive graphs on-line

✍ Scribed by Sandy Irani

Publisher: Springer
Year: 1994
Tongue: English
Weight: 895 KB
Volume: 11
Category: Article
ISSN: 0178-4617
DOI: 10.1007/bf01294263

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On-line coloring of perfect graphs

✍ H. A. Kierstead; K. Kolossa 📂 Article 📅 1996 🏛 Springer-Verlag 🌐 English ⚖ 655 KB

Coloring quasi-line graphs

✍ Maria Chudnovsky; Alexandra Ovetsky 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract A graph __G__ is a quasi‐line graph if for every vertex __v__, the set of neighbors of __v__ can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. A theorem of Shannon's implies that if __G__ is a line graph, then

Effective on-line coloring ofP5-free gra

Effective on-line coloring ofP5-free graphs

✍ András Gyárfás; Jenő Lehel 📂 Article 📅 1991 🏛 Springer-Verlag 🌐 English ⚖ 235 KB

On-line coloringk-colorable graphs

✍ H. A. Kierstead 📂 Article 📅 1998 🏛 The Hebrew University Magnes Press 🌐 English ⚖ 535 KB

Parallel and On-Line Graph Coloring

✍ Magnus M Halldórsson 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 209 KB

We discover a surprising connection between graph coloring in two orthogonal paradigms: parallel and on-line computing. We present a randomized on-line Ž . coloring algorithm with a performance ratio of O nrlog n , an improvement of log n factor over the previous best known algorithm of Vishwanathan

On-Line Coloring of Sparse Random Graphs

On-Line Coloring of Sparse Random Graphs and Random Trees

✍ Boris Pittel; Robert S. Weishaar 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 164 KB

The performance of the greedy coloring algorithm ''first fit'' on sparse random graphs G and on random trees is investigated. In each case, approximately n, c r n log log n colors are used, the exact number being concentrated almost surely on at 2 most two consecutive integers for a sparse random gr