A note on first-fit coloring of interval graphs
From MaRDI portal
Publication:925259
DOI10.1007/s11083-008-9076-6zbMath1149.05044OpenAlexW2013393952MaRDI QIDQ925259
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
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (23)
Grundy Distinguishes Treewidth from Pathwidth ⋮ On-line interval graphs coloring — Modification of the First-Fit algorithm and its performance ratio ⋮ Unnamed Item ⋮ On-line dimension for posets excluding two long incomparable chains ⋮ Online coloring of short intervals ⋮ Computational aspects of greedy partitioning of graphs ⋮ Batch Coloring of Graphs ⋮ A Refined Analysis of Online Path Coloring in Trees ⋮ Unnamed Item ⋮ First-Fit is linear on posets excluding two long incomparable chains ⋮ On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains ⋮ On Computational Aspects of Greedy Partitioning of Graphs ⋮ First-fit coloring on interval graphs has performance ratio at least 5 ⋮ Complexity of Grundy coloring and its variants ⋮ An easy subexponential bound for online chain partitioning ⋮ Batch coloring of graphs ⋮ On the max coloring problem ⋮ First-fit coloring of bounded tolerance graphs ⋮ Unnamed Item ⋮ Reverse Mathematics and Grundy colorings of graphs ⋮ Max-coloring of vertex-weighted graphs ⋮ A Dichotomy Theorem for First-Fit Chain Partitions ⋮ On-line chain partitions of orders: a survey
Cites Work
This page was built for publication: A note on first-fit coloring of interval graphs
