Premium
On‐line and first fit colorings of graphs
Author(s) -
Gyárfás A.,
Lehel J.
Publication year - 1988
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190120212
Subject(s) - combinatorics , greedy coloring , mathematics , complete coloring , chordal graph , graph coloring , interval graph , fractional coloring , edge coloring , list coloring , discrete mathematics , split graph , bounded function , brooks' theorem , graph , indifference graph , line graph , 1 planar graph , graph power , mathematical analysis
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 we 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.