Source-linked AI summary
FirstFit online coloring in the random order model
Xinyu Ye, Yuechuan Xu, Zixuan Wang, Jiaying Zheng, Yaqiao Li
TL;DR
The paper asks how FirstFit behaves under random vertex arrival beyond trees, where recent work showed Θ(log n / log log n) colors instead of Θ(log n) adversarially. It extends the analysis using path counting and examines sparse, dense bipartite, crown, and unit interval graph classes. The results include tree-like bounds for cactus graphs and uniform hypertrees, O(1) colors on crown graphs, and persistent lower bounds for some dense bipartite graphs.
Problem
Random-order performance of FirstFit is less understood beyond trees, especially across sparse and dense graph classes.
Method
The paper extends prior random-order analysis with a path-counting principle and studies explicit constructions across several graph classes.
Results
Θ(log n / log log n) expected colors hold for cactus graphs and uniform hypertrees; crown graphs require at most 2.5 + O(1/n) expected colors, while some bipartite graphs with minimum degree Ω(n) require Ω(log n / log log n).
Takeaways & Limitations
Random arrival can substantially improve FirstFit on some graph classes, but density alone does not guarantee O(1) colors and some classes show limited improvement.
Takeaways & Limitations
The path-counting theorem does not apply to all inductive or bounded-treewidth graphs because their k-path counts can grow too quickly.
Abstract
from arXiv · showhide
The average performance of FirstFit online coloring on trees in the random order model is completely determined in recent works of Frei et al. and Bosek et al., showing $Θ(\log n /\log\log n)$ number of colors, improving the $Θ(\log n)$ colors in the adversarial model. We provide a few further results on slightly more general graph classes. Firstly, we extend their method to obtain a simple path-counting principle for sparse graph classes, which immediately yields for example that cactus graphs and uniform hypertrees exhibit a similar improvement. We then show that FirstFit uses only $O(1)$ colors on crown graphs, a standard example where adversarial arrival forces $Θ(n)$ colors. We further show that density alone (even linear minimum degree) is insufficient to guarantee $O(1)$ colors even on bipartite graphs. Finally, we identify graph classes, including unit interval graphs and some graphs of high chromatic number, for which random arrival provides only limited improvement. We end with some open problems.
1 Introduction
The paper studies FirstFit online coloring under random vertex arrival, extending recent tree results to additional graph classes and identifying both improvements and limitations of random order.
- 1 Introduction: FirstFit colors each arriving vertex with the first color absent from its already arrived neighbors.The algorithm irrevocably assigns the color before the next vertex arrives.
- 1 Introduction: Θ(log n / log log n) colors in expectation on trees improve on the Θ(log n) worst-case bound in the adversarial model.Recent work by Frei et al. and Bosek et al. established this random-order result for trees and forests.
- 1 Introduction: The paper extends the tree method through a path-counting principle for sparse graph classes.This principle yields O(log n / log log n) colors for cactus graphs and uniform hypertrees.
- 1 Introduction: FirstFit uses O(1) colors on crown graphs, despite adversarial arrivals forcing Θ(n) colors there.The paper also investigates dense bipartite graphs and identifies settings where random arrival offers limited improvement.
2 Bounded k-paths graphs
The paper bounds FirstFit through the number of graph paths, obtaining tree-like random-order performance for cactus graphs and uniform hypertrees while showing the method fails for some bounded-treewidth examples.
- Bounded k-paths graphs: A k-path consists of k vertices connected consecutively by edges, and P_k(G) counts distinct such paths.Two paths are distinct when they differ in at least one edge.
- Bounded k-paths graphs: O(log n / log log n) expected colors follow when P_k(G) ≤ O(nab^k) for every relevant k.The bound is obtained by combining path counting with random relative-order probabilities and optimizing over k.
- Bounded k-paths graphs: Θ(log n / log log n) expected colors hold for cactus graphs and s-uniform hypertrees in the random order model.Cactus graphs have P_k(G) ≤ O(n2^2k), while hypertrees have O(n^2) Berge paths because they are Berge-cycle-free.
- Bounded k-paths graphs: The lower bounds for cactus graphs and s-uniform hypertrees extend the tree construction, including a rooted s-uniform hypertree construction.For s-uniform hypertrees, the lower bound is Ω_s(log n / log log n).
- Bounded k-paths graphs: Bounded treewidth and inductive graphs need not have bounded k-path counts, so the theorem does not cover all such sparse-looking classes.The graph G_p,q is presented as a series–parallel, treewidth-2, 2-inductive, planar example family illustrating this limitation.
3 Dense bipartite graphs
Dense bipartite graphs show contrasting random-order behavior: FirstFit uses at most 2.5 + O(1/n) colors in expectation on crown graphs, while another bipartite family with minimum degree Ω(n) still requires Ω(log n/log log n) colors in expectation.
- Crown graphs: Crown graphs force n colors under the adversarial order u1, v1, u2, v2, …, but random arrival reduces FirstFit to at most 2.5 + O(1/n) colors in expectation.The crown graph has two equal vertex sets, with ui adjacent to every vj except vi.
- Crown graphs: When the first U-block has at least two vertices, FirstFit uses exactly 2 colors because subsequent blocks alternate between colors 1 and 2.The random permutation is partitioned into consecutive blocks alternating between U and V.
- Crown graphs: When the first U-block is a singleton and the second V-block has at least three vertices, FirstFit uses at most 3 colors.If the exceptional matching partner lies in the second V-block, color 3 can occur; otherwise the alternating pattern uses colors 1 and 2.
- Crown graphs: The color-3 event occurs with probability at most 1/n, while the remaining exceptional case has probability 1/(2n−1).Outside these cases, FirstFit uses 2 colors; in all cases it uses at most n colors because the crown graph has maximum degree n−1.
- Linear minimum degree: A suitable blow-up of the crown graph yields a bipartite graph family where FirstFit uses Ω(log n/log log n) colors in expectation despite minimum degree Ω(n).The construction has n = Θ(k^(k−1)) vertices and makes FirstFit use at least k colors with constant probability.
- Linear minimum degree: The lower-bound construction starts from disjoint sets A^(j)_k and B^(j)_k of sizes k^(j−1), connects selected cross-part pairs, and then adds copies to raise every degree to Ω(n).The resulting graph remains bipartite, and the added copies preserve the constant-probability coloring event.
4 Limited benefit from random order
Random arrival offers limited improvement for unit interval graphs and some graphs with low relative chromatic number. Finite adversarial constructions can preserve FirstFit’s worst-case color usage under random ordering.
- Unit interval graphs: 2ω −1 colors are used in expectation by FirstFit on unit interval graphs with maximum clique size ω.The adversarial upper bound is matched in expectation under random arrival.
- Unit interval graphs: Finite lower-bound constructions can make FirstFit use 2ω −1 colors with probability tending to 1 under random ordering.Taking many independent copies drives the probability of failing to realize the bound to zero.
- Unit interval graphs: Every graph class admitting a finite adversarial construction offers FirstFit no essential advantage from random ordering.This conclusion follows from repeating the finite construction independently.
- High chromatic number graphs: Trees achieve O(log n / log log n) colors in the random order model, but larger graph classes can still exhibit much worse behavior.The contrast motivates studying graph classes beyond trees.
- High chromatic number graphs: For every ε > 0, some graph with χ(G) = O(n^ε) makes FirstFit use Ω(n / log n) colors in expectation.Thus, random ordering can remain highly non-competitive on graphs with relatively small chromatic number.
5 Open problems
The paper leaves open which graph classes guarantee constant-color FirstFit performance under random arrival and whether known adversarial optimality extends to broader classes. It also asks whether CBIP achieves comparable bounds on trees or bipartite graphs.
- Characterize the graph classes on which FirstFit uses O(1) colors in the random order model.
- Determine whether FirstFit remains optimal on inductive and chordal graphs in the random order model.The paper states that its path-counting technique is insufficient to resolve this question.
- Establish whether CBIP uses Θ(log n / log log n) colors in expectation on trees or possibly bipartite graphs under random arrival.