Coloring interval graphs with First-Fit

DOI10.1016/0012-365X(94)00285-QzbMATH Open0837.05061OpenAlexW2147737694MaRDI QIDQ1898342FDOQ1898342

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

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

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)

Cites Work

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

Cited In (27)

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

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)