First-fit coloring of incomparability graphs

DOI10.1137/110854394MaRDI QIDQ5300485zbMATH OpenOpenAlexFDO

Authors Bartłomiej Bosek, Tomasz Krawczyk, Grzegorz Matecki

Publication date 27 June 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/110854394

zbMATH Keywords

chain partitioningfirst-fitGrundy numberincomparability graphsposet

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics of partially ordered sets (06A07) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the performance of the first-fit coloring algorithm on permutation graphs
• Coloring interval graphs with First-Fit
• scientific article; zbMATH DE number 65699
• First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs
• First-fit coloring on interval graphs has performance ratio at least 5

Cited in

(6)

• An easy subexponential bound for online chain partitioning
• Coloring interval graphs with First-Fit
• A subexponential upper bound for the on-line chain partitioning problem
• On the performance of the first-fit coloring algorithm on permutation graphs
• First-fit chromatic numbers of \(d\)-degenerate graphs
• A Dichotomy Theorem for First-Fit Chain Partitions

This page was built for publication: First-fit coloring of incomparability graphs

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