A Dichotomy Theorem for First-Fit Chain Partitions

DOI10.1137/18M1219862OpenAlexW3010580304MaRDI QIDQ5218437

Kevin G. Milans, Michael C. Wigal

Publication date: 4 March 2020

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

Full work available at URL: https://arxiv.org/abs/1810.03807

zbMATH Keywords

posetonline algorithmdichotomychain partitionFirst-Fit

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07)

Cites Work

• Unnamed Item
• Unnamed Item
• First-fit coloring on interval graphs has performance ratio at least 5
• First-Fit is linear on posets excluding two long incomparable chains
• On First-Fit coloring of ladder-free posets
• A note on first-fit coloring of interval graphs
• An easy subexponential bound for online chain partitioning
• Intransitive indifference with unequal indifference intervals
• The Difference Between Consecutive Primes, II
• First-Fit Algorithm for the On-Line Chain Partitioning Problem
• On-line and first fit colorings of graphs
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• The Difference Between Consecutive Primes
• An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains
• First-Fit Coloring of Incomparability Graphs
• On a problem of K. Zarankiewicz

This page was built for publication: A Dichotomy Theorem for First-Fit Chain Partitions