A note on first-fit coloring of interval graphs
DOI10.1007/S11083-008-9076-6zbMATH Open1149.05044OpenAlexW2013393952MaRDI QIDQ925259FDOQ925259
R. Subhash Babu, N. S. Narayanaswamy
Publication date: 3 June 2008
Published in: Order (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11083-008-9076-6
Recommendations
- Coloring interval graphs with First-Fit
- Online coloring co-interval graphs
- First-fit coloring on interval graphs has performance ratio at least 5
- The Linearity of First-Fit Coloring of Interval Graphs
- On-line interval graphs coloring — Modification of the First-Fit algorithm and its performance ratio
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)
Cites Work
Cited In (24)
- On-line interval graphs coloring — Modification of the First-Fit algorithm and its performance ratio
- First-fit coloring of bounded tolerance graphs
- Grundy Distinguishes Treewidth from Pathwidth
- On the max coloring problem
- Title not available (Why is that?)
- First-Fit is linear on posets excluding two long incomparable chains
- Reverse Mathematics and Grundy colorings of graphs
- On-line chain partitions of orders: a survey
- An easy subexponential bound for online chain partitioning
- Batch coloring of graphs
- Computational aspects of greedy partitioning of graphs
- Title not available (Why is that?)
- On Computational Aspects of Greedy Partitioning of Graphs
- A Refined Analysis of Online Path Coloring in Trees
- On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains
- Max-coloring of vertex-weighted graphs
- Coloring interval graphs with First-Fit
- Batch Coloring of Graphs
- Online coloring of short intervals
- A Dichotomy Theorem for First-Fit Chain Partitions
- First-fit coloring on interval graphs has performance ratio at least 5
- Forbidden structures for efficient first-fit chain partitioning (extended abstract)
- Complexity of Grundy coloring and its variants
- On-line dimension for posets excluding two long incomparable chains
This page was built for publication: A note on first-fit coloring of interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q925259)
