Coloring Inductive Graphs On-Line

Online graph coloring, in which the vertices are presented one at a time, is considered. Each vertex must be assigned a color, different from the colors of its neighbors, before the next vertex is given. The class of d-inductive graphs is treated. A graph G is said to be d-inductive if the vertices of G can be numbered so that each vertex has at most d edges to higher numbered vertices. First Fit (FF) is the algorithm that assigns each vertex the lowest numbered color possible. It is shown that if G is d-inductive, then FF uses O(d log n) colors on G. This yields an upper bound of O(log n) on the performance ratio of FF on chordal and planar graphs. FF does as well as any online algorithm for d-inductive graphs; it is shown that for any d and any online graph-coloring algorithm A, there is a d-inductive graph that forces A to use Omega (d log n) colors to color G. Online graph coloring with lookahead is also investigated. >

Authors

• Sandy Irani

Keywords

• Registers
• Costs
• Computer science
• Algorithm design and analysis
• Delay
• Processor scheduling
• Upper Bound
• Online Algorithm
• Planar Graphs
• Class Of Graphs
• Previous Phase
• Vertices
• Online Problem
• Family Of Graphs