Online coloring of short interval graphs and two-count interval graphs

Israel R. Curbelo

arxiv: 2412.17193 · v3 · submitted 2024-12-22 · 💻 cs.DS · math.CO

Online coloring of short interval graphs and two-count interval graphs

Israel R. Curbelo This is my paper

Pith reviewed 2026-05-23 06:12 UTC · model grok-4.3

classification 💻 cs.DS math.CO

keywords online coloringinterval graphscompetitive analysissigma-interval graphstwo-count interval graphsFirst-Fit algorithm

0 comments

The pith

For sufficiently large σ, no online algorithm can color σ-interval graphs with competitive ratio less than 3-ε for any ε>0.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves a nearly tight lower bound for the online coloring of σ-interval graphs, showing that the competitive ratio must be at least 3 minus an arbitrarily small ε when the length ratio σ is large enough. It also gives competitive ratio bounds for the special case of interval graphs using only two different interval lengths, including an upper bound of 4 for the First-Fit algorithm. These findings narrow the gap between the known upper bound of 3 and the lower bound of 2 for σ-interval graphs and provide new limits for the two-length case depending on whether the interval representation is known to the algorithm.

Core claim

For every ε > 0 there exists σ > 1 such that no online algorithm for coloring σ-interval graphs has competitive ratio less than 3 - ε. For 2-count interval graphs, First-Fit is at most 4-competitive, no algorithm achieves better than 2.5 when the representation is unknown, and no algorithm achieves better than 2 when the representation is known.

What carries the argument

Adversarial online presentation of σ-interval graphs that forces any coloring algorithm to exceed the ratio 3-ε.

Load-bearing premise

There exist online adversarial sequences of σ-interval graphs that force any algorithm's performance to have competitive ratio at least 3-ε.

What would settle it

Discovery of an online algorithm that colors all σ-interval graphs with competitive ratio below 3-ε for every σ would falsify the main claim.

read the original abstract

We study the online coloring of $\sigma$-interval graphs, which are interval graphs with interval lengths in $[1,\sigma]$ and 2-count interval graphs, which are interval graphs that require at most two distinct interval lengths. For $\sigma$-interval graphs, the Kierstead-Trotter algorithm has competitive ratio 3 and no online algorithm has competitive ratio better than 2. In this paper, we show that for every $\varepsilon>0$, there is a $\sigma>1$ such that there is no online algorithm for $\sigma$-interval coloring with competitive ratio less than $3-\varepsilon$. For 2-count interval graphs, we show that the greedy algorithm First-Fit has competitive ratio at most $4$, that there is no online algorithm with competitive ratio less than $2.5$ when the interval representation is unknown, and that there is no online algorithm with competitive ratio less than $2$ when the interval representation is known.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper claims a lower bound approaching 3 for σ-interval graphs and new 2.5/2 separations for 2-count graphs, but only the abstract exists so nothing can be verified.

read the letter

The main new claims are that for any ε>0 there exists σ>1 where no online algorithm colors σ-interval graphs with ratio better than 3-ε, plus First-Fit at most 4 on 2-count graphs, a 2.5 lower bound when the representation is unknown, and a 2 lower bound when it is known. These improve the generic lower bound of 2 that was already in the literature while sitting under the Kierstead-Trotter upper bound of 3. The separation by representation knowledge for the 2-count case is also new on its face. That is the actual content worth noting. The work stays inside the standard online coloring model with adaptive adversaries, which is the right setting for these questions. The abstract does not supply the adversary constructions or proof sketches, so there is no way to check whether the claimed sequences actually force the ratios or whether the arguments contain gaps. Without those details the soundness cannot be assessed. The citation pattern looks ordinary and points to the right prior results. This paper is for people who work on competitive ratios for interval graphs and their scheduling applications. A reader already following that narrow literature would see the quantitative tightenings as relevant if the proofs check out. It is worth sending to referees because the questions are well-posed and the claimed improvements are specific enough to be worth checking, even though the current version gives no evidence beyond the statements themselves.

Referee Report

2 major / 0 minor

Summary. The paper studies online coloring of σ-interval graphs (interval graphs with lengths in [1,σ]) and 2-count interval graphs (at most two distinct lengths). It recalls that the Kierstead-Trotter algorithm achieves competitive ratio 3 for σ-interval graphs with a general lower bound of 2, but claims that for every ε>0 there exists σ>1 such that no online algorithm achieves ratio less than 3−ε. For 2-count interval graphs it claims First-Fit has ratio at most 4, with lower bounds of 2.5 (unknown representation) and 2 (known representation).

Significance. If the lower-bound constructions hold, the results would be significant for online algorithms on interval graphs: they would show the ratio 3 is nearly tight for sufficiently large σ, narrowing the gap to the known lower bound of 2, and would supply the first concrete ratios for the 2-count subclass while distinguishing known vs. unknown representations.

major comments (2)

[Abstract] Abstract: the central claim that for every ε>0 there exists σ>1 with no online algorithm of ratio <3−ε is asserted via existence of adversarial sequences, but the abstract supplies no construction, no explicit graph family, and no proof details. This is load-bearing for the main result and cannot be verified from the provided text.
[Abstract] Abstract: the lower bounds of 2.5 (unknown representation) and 2 (known representation) for 2-count interval graphs are stated without any indication of the adversary construction or derivation, preventing assessment of whether they correctly force the claimed ratios against an adaptive online adversary.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the comments on our manuscript. The abstract is a concise summary, with full constructions and proofs in the body; we address the points below.

read point-by-point responses

Referee: [Abstract] Abstract: the central claim that for every ε>0 there exists σ>1 with no online algorithm of ratio <3−ε is asserted via existence of adversarial sequences, but the abstract supplies no construction, no explicit graph family, and no proof details. This is load-bearing for the main result and cannot be verified from the provided text.

Authors: Abstracts are not intended to contain full constructions or proofs. The adversarial sequences, explicit graph families, and complete proof for the σ-interval lower bound (showing the ratio can be forced arbitrarily close to 3) appear in the main body of the paper. Since the query provides only the abstract, those details are not visible here, but they are present in the submitted manuscript. revision: no
Referee: [Abstract] Abstract: the lower bounds of 2.5 (unknown representation) and 2 (known representation) for 2-count interval graphs are stated without any indication of the adversary construction or derivation, preventing assessment of whether they correctly force the claimed ratios against an adaptive online adversary.

Authors: The same applies to the 2-count lower bounds: the adversary constructions and derivations establishing the 2.5 (unknown representation) and 2 (known representation) bounds are given in full in the body of the paper. The abstract summarizes the results without derivations, which is standard. revision: no

Circularity Check

0 steps flagged

No circularity; lower bound via standard adversarial construction

full rationale

The abstract asserts existence of σ-dependent adversarial sequences forcing competitive ratio arbitrarily close to 3, but supplies no equations, fitted parameters, or self-citations. Lower bounds in online algorithms are constructed explicitly via adversary sequences against the definition of competitive ratio; this is independent of the claimed result and does not reduce by definition or self-reference. No load-bearing self-citation, ansatz smuggling, or renaming of known results appears. The result is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on the standard mathematical definitions of interval graphs, σ-interval graphs, 2-count interval graphs, and the competitive ratio of online algorithms; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)

standard math Standard definitions of interval graphs and the online coloring model with competitive ratio measured against an adaptive adversary
The entire analysis presupposes these established notions from graph theory and online computation.

pith-pipeline@v0.9.0 · 5661 in / 1291 out tokens · 35733 ms · 2026-05-23T06:12:24.893690+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 5.1: for every ε>0 there is σ>1 such that no online algorithm for σ-interval coloring has competitive ratio <3−ε
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 6.1: 2-COUNT First-Fit ≤4 (via short/long interval case analysis)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.