On First-Fit coloring of ladder-free posets

DOI10.1016/J.EJC.2012.07.007zbMATH Open1288.06004OpenAlexW1971238463MaRDI QIDQ691598FDOQ691598

Authors: Matt Earl Smith, H. A. Kierstead 

Publication date: 3 December 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2012.07.007

Recommendations

• First-Fit Algorithm for the On-Line Chain Partitioning Problem
• An easy subexponential bound for online chain partitioning
• On-line dimension for posets excluding two long incomparable chains
• First-Fit is linear on posets excluding two long incomparable chains
• An improved bound for first-fit on posets without two long incomparable chains

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Partial orders, general (06A06)

Cited In (8)

• On colorings of the Boolean lattice avoiding a rainbow copy of a poset
• On first-order definable colorings
• A subexponential upper bound for the on-line chain partitioning problem
• First-Fit is linear on posets excluding two long incomparable chains
• An easy subexponential bound for online chain partitioning
• An improved bound for first-fit on posets without two long incomparable chains
• A Dichotomy Theorem for First-Fit Chain Partitions
• On-line dimension for posets excluding two long incomparable chains

This page was built for publication: On First-Fit coloring of ladder-free posets

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