arXiv preprint ·
FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
FirstFit colors each arriving vertex with the smallest positive integer absent from its previously colored neighborhood. We prove that this rule can require $n^{Ω(1)}$ many colors on certain bipartite graph of $n$ vertices even when the vertices arrive in a uniformly random order. This refutes the conjecture of Bosek, Gutowski, Lasoń, and Przybyło [BGLP24] that FirstFit uses a polylogarithmic expected number of colors on every bipartite graph in the random order model. We obtain the lower bound by analyzing the FirstFit coloring process on random bipartite graphs, where vertices arrive to either side with equal probability, and with an independent edge density $n^{-x}$ for some $0 0$, there are graphs with chromatic number at most $n^ε$ on which FirstFit uses $Ω(n/\log n)$ colors in expectation under a uniformly random order. Our result shows that such poor behavior of FirstFit already occurs for $χ(G) = 2$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
A Quantum Analogue of the Covering Lemma: Limits of Exact Anonymous Computation
Exponential Local Search in Bounded-Occurrence MAX-CSP
Dynamic Conflict Clustering with Lightweight Learning and Strategic Repair for Distributed Constraint Satisfaction
A Practical Combinatorial Interior Point Method for Minimum-Cost Flow
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.