Coloring interval graphs with First-Fit

DOI10.1016/0012-365X(94)00285-QzbMath0837.05061OpenAlexW2147737694MaRDI QIDQ1898342

Jun Qin, Henry A. Kierstead

Publication date: 13 May 1996

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(94)00285-q

zbMATH Keywords

chordal graphsinterval graphson-line coloringfirst-fitgraph coloring algorithmon-line coloring algorithmon-line graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (19)

A graph coloring approach to the deployment scheduling and unit assignment problem ⋮ On-line dimension of semi-orders ⋮ Online promise problems with online width metrics ⋮ An improved algorithm for online coloring of intervals with bandwidth ⋮ On-line interval graphs coloring — Modification of the First-Fit algorithm and its performance ratio ⋮ On-line dimension for posets excluding two long incomparable chains ⋮ First-fit chromatic numbers of \(d\)-degenerate graphs ⋮ First-Fit is linear on posets excluding two long incomparable chains ⋮ A note on first-fit coloring of interval graphs ⋮ On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains ⋮ First-fit coloring on interval graphs has performance ratio at least 5 ⋮ Online interval coloring with packing constraints ⋮ An easy subexponential bound for online chain partitioning ⋮ On the max coloring problem ⋮ First-fit coloring of bounded tolerance graphs ⋮ Unnamed Item ⋮ On the Max Coloring Problem ⋮ On-line chain partitions of orders: a survey ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Covering and coloring problems for relatives of intervals
• A polynomial time approximation algorithm for dynamic storage allocation
• On-line and first fit colorings of graphs
• The Linearity of First-Fit Coloring of Interval Graphs
• On some packing problem related to dynamic storage allocation
• An Effective Version of Dilworth's Theorem
• On-Line Coloring and Recursive Graph Theory
• The Bay Restaurant--A Linear Storage Problem
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $

This page was built for publication: Coloring interval graphs with First-Fit