𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On-line and first fit colorings of graphs

✍ Scribed by A. Gyárfás; J. Lehel

Publisher
John Wiley and Sons
Year
1988
Tongue
English
Weight
537 KB
Volume
12
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

A graph coloring algorithm that immediately colors the vertices taken from a list without looking ahead or changing colors already assigned is called "on-line coloring." The properties of on-line colorings are investigated in several classes of graphs. In many cases w e find on-line colorings that use no more colors than some function of the largest clique size of the graph. We show that the first fit on-line coloring has an absolute performance ratio of two for the complement of chordal graphs. We prove an upper bound for the performance ratio of the first fit coloring on interval graphs. It is also shown that there are simple families resisting any on-line algorithm: no on-line algorithm can color all trees by a bounded number of colors.

📜 SIMILAR VOLUMES

Coloring interval graphs with first-fit
Coloring interval graphs with first-fit
✍ H.A. Kierstead; Jun Qin 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 569 KB

Improved bounds on the performance of the on-line graph coloring algorithm First-Fit on interval graphs are obtained.

Parallel and On-Line Graph Coloring
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 Total Colorings of Graphs
On Total Colorings of Graphs
✍ C. Mcdiarmid; B. Reed 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 299 KB

AND Bruce Reed Department of Combinatorics and Optimisation, University of Waterloo, Waterloo, Ontario, Canada

On splittable colorings of graphs and hy
On splittable colorings of graphs and hypergraphs
✍ Zoltán Füredi; Radhika Ramamurthi 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB

## Abstract The notion of a split coloring of a complete graph was introduced by Erdős and Gyárfás [7] as a generalization of split graphs. In this work, we offer an alternate interpretation by comparing such a coloring to the classical Ramsey coloring problem via a two‐round game played against an