Coloring interval graphs with First-Fit

DOI10.1016/0012-365X(94)00285-QMaRDI QIDQ1898342zbMATH OpenOpenAlexFDO

Authors Jun Qin, H. 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

interval graphschordal graphson-line coloringfirst-fitgraph coloring algorithmon-line coloring algorithmon-line graph

Mathematics Subject Classification ID

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

Recommendations

• A note on first-fit coloring of interval graphs
• scientific article; zbMATH DE number 820116
• The Linearity of First-Fit Coloring of Interval Graphs
• First-fit coloring on interval graphs has performance ratio at least 5
• scientific article; zbMATH DE number 17824
• Intervalizing \(k\)-colored graphs
• First-fit coloring of bounded tolerance graphs
• First-fit coloring of incomparability graphs
• On-line interval graphs coloring — Modification of the First-Fit algorithm and its performance ratio
• Exact algorithms for intervalizing colored graphs

Cites work

• scientific article; zbMATH DE number 3769624 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A polynomial time approximation algorithm for dynamic storage allocation
• An Effective Version of Dilworth's Theorem
• Covering and coloring problems for relatives of intervals
• On some packing problem related to dynamic storage allocation
• On-Line Coloring and Recursive Graph Theory
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• On-line and first fit colorings of graphs
• The Bay Restaurant--A Linear Storage Problem
• The Linearity of First-Fit Coloring of Interval Graphs

Cited in

(28)

• Online interval coloring with packing constraints
• A note on the online first-fit algorithm for coloring \(k\)-inductive graphs
• On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains
• On the performance guarantee of first fit for sum coloring
• A graph coloring approach to the deployment scheduling and unit assignment problem
• First-fit chromatic numbers of \(d\)-degenerate graphs
• Forbidden structures for efficient first-fit chain partitioning (extended abstract)
• On the max coloring problem
• Online coloring of short intervals
• The Linearity of First-Fit Coloring of Interval Graphs
• scientific article; zbMATH DE number 17824 (Why is no real title available?)
• First-fit coloring of incomparability graphs
• scientific article; zbMATH DE number 820116 (Why is no real title available?)
• Online promise problems with online width metrics
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• On-line dimension of semi-orders
• On-line chain partitions of orders: a survey
• On-line interval graphs coloring — Modification of the First-Fit algorithm and its performance ratio
• On the Max Coloring Problem
• An improved algorithm for online coloring of intervals with bandwidth
• A note on first-fit coloring of interval graphs
• First-fit coloring on interval graphs has performance ratio at least 5
• On-line dimension for posets excluding two long incomparable chains
• First-fit coloring of bounded tolerance graphs
• scientific article; zbMATH DE number 7407778 (Why is no real title available?)
• On the performance of the first-fit coloring algorithm on permutation graphs
• First-Fit is linear on posets excluding two long incomparable chains
• An easy subexponential bound for online chain partitioning

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1898342)