1988/06/01 by András Gyárfás, Jenő Lehel · 6 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Optimization and Search Problems #Complexity and Algorithms in Graphs #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
paper · doi:10.1002/jgt.3190120212
openalex publication_date 1988/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
Abstract 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.