First-Fit Coloring of Incomparability Graphs

DOI10.1137/110854394zbMath1268.05193OpenAlexW2074644541MaRDI QIDQ5300485

Tomasz Krawczyk, Bartłomiej Bosek, 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

posetincomparability graphschain partitioningGrundy numberfirst-fit

Mathematics Subject Classification ID

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

Related Items (4)

A subexponential upper bound for the on-line chain partitioning problem ⋮ Asymmetric coloring games on incomparability graphs ⋮ An easy subexponential bound for online chain partitioning ⋮ A Dichotomy Theorem for First-Fit Chain Partitions

This page was built for publication: First-Fit Coloring of Incomparability Graphs