PaperlayerView exact revision on arXiv

Source-linked AI summary

Progress on Albertson's Conjecture

Daniel W. Cranston

arXiv:2512.08020v1math.CO

TL;DR

Albertson’s Conjecture asks whether every graph with chromatic number r has crossing number at least that of K_r. The paper uses r-critical reductions, edge bounds, crossing-number inequalities, and weak immersions to constrain counterexamples. It proves the conjecture for r ≤ 24 and excludes broad order ranges, with stronger lower-order exclusions for sufficiently large r.

  • Problem

    The paper addresses whether every graph with chromatic number r satisfies cr(G) ≥ cr(K_r), beyond the previously established range r ≤ 18.

    Source: §1 · p. 1

  • Method

    The paper reduces the problem to r-critical graphs and combines edge-density crossing bounds with weak-immersion arguments to exclude counterexample orders.

    Source: §1 · pp. 1–2

  • Results

    The conjecture holds for r ≤ 24; for r ≤ 26, remaining counterexamples are restricted to (25, 48), (26, 50), or (26, 51), while broad order ranges are excluded.

    Source: §1 · p. 1, §3 · p. 4, §5 · pp. 10–11

  • Takeaways & Limitations

    Potential minimum counterexamples must avoid multiple order intervals, with the excluded lower endpoint extending as r becomes very large.

    Source: §1 · pp. 1–2, §5 · pp. 10–11

Abstract

from arXiv · show

Albertson conjectured that every graph with chromatic number $r$ has crossing number at least the crossing number of the complete graph $K_r$. This conjecture was proved for $r\le 12$ by Albertson, Cranston, and Fox; for $r\le 16$ by Bar\'{a}t and T\'{o}th; and for $r\le 18$ by Ackerman. Here we verify it for $r\le 24$; we also greatly restrict the possibilities for counterexamples when $r\in\{25,26\}$. In addition, we strengthen earlier work bounding the order of a minimum counterexample for each choice of $r$: we exclude the possibility that $|G|\ge 2.82r$ and exclude the possibility that $1.228r\le |G|\le 1.768r$. Finally, as $r$ grows, we extend the lower end of this range of excluded orders for a minimum counterexample. In particular: if $r\ge 125{,}000$, then we exclude the possibility that $1.10r\le |G|\le 1.768r$; and if $r\ge 825{,}000$, then we exclude the possibility that $1.05r\le |G|\le 1.768r$.

1 Introduction

The paper advances Albertson’s Conjecture by proving it for additional values of r and sharply narrowing possible minimum counterexample orders. It also develops a critical-graph framework and strengthens crossing-number bounds across several order ranges.

  • Albertson’s Conjecture asserts that χ(G) ≥ r implies cr(G) ≥ cr(K_r), extending the 4 Color Theorem’s zero-crossing case.Source: §1 · p. 1
  • The paper reduces the problem to r-critical graphs, since every r-chromatic graph contains an r-critical subgraph.Source: §1 · p. 1
  • The paper’s main order bounds exclude minimum counterexamples with |G| in [1.212r, 1.768r] or |G| ≥ 2.812r, improving earlier bounds.Source: §1 · p. 1
  • Theorem 2 proves cr(G) ≥ cr(K_r) for every r-critical graph when r ≤ 24.Source: §1 · p. 1
  • For r ≤ 26, any remaining counterexample must have (r, |G|) ∈ {(25, 48), (26, 50), (26, 51)}.Source: §1 · p. 1
  • A weak-immersion approach further excludes |G|/r ∈ [1.10, 1.23] for r ≥ 125,000 and [1.05, 1.23] for r ≥ 825,000.Source: §1 · p. 2

2 Handling r-critical graphs G with |G| ⩾2.82r

This section proves that sufficiently large r-critical graphs cannot be counterexamples to Albertson’s Conjecture, using edge-density lower bounds and crossing-number inequalities.

  • Earlier results lowered the sufficient order threshold from 4r [3] to 3.57r [5] and then 3.03r [1].Source: §2 · p. 2
  • For r ≥ 15, every r-critical graph with |G| ≥ 2.8118r satisfies cr(G) ≥ cr(K_r).Source: §2 · p. 2
  • The proof combines the minimum-degree bound m ≥ n(r − 1)/2 with a Crossing Lemma consequence giving cr(G) ≥ m^3/(27.48n^2) when m ≥ 6.95n.Source: §2 · p. 2
  • For intermediate density ratios, the argument samples k-vertex subgraphs uniformly and applies a strengthened crossing-number inequality.Source: §2 · pp. 2–3
  • Choosing k = 40 and k = 36 verifies the needed inequalities over order-ratio intervals reaching α > 2.8118.Source: §2 · pp. 3–4

3 Handling r-critical graphs G with 1.228r ⩽|G| ⩽1.768r

The paper proves that r-critical graphs with 1.228r ≤ |G| ≤ 1.768r satisfy Albertson’s crossing-number bound. It combines an edge lower bound with polynomial inequalities, using k = 12, 15, and 19 across subranges of |G|/r.

  • 1.228r ≤ |G| ≤ 1.768r implies cr(G) ≥ cr(K_r) for every r-critical graph G.Source: §3 · p. 4
  • The proof substitutes Theorem B’s edge bound into a crossing-number inequality and seeks k values making that inequality hold for all r.The right side bounds cr(K_r), while the left side lower-bounds cr(G).Source: §3 · p. 4
  • The contour analysis identifies k = 12 for α ∈ [1.23, 1.43], k = 19 for α ∈ [1.53, 1.77], and k = 15 for the intervening range.Here α = |G|/r, and k ∈ {14, 15, 16, 17} would work in the middle interval; the proof chooses k = 15.Source: §3 · pp. 4–5, Figure 2 · p. 5
  • For k = 19, nonnegativity of four polynomial components yields α ∈ (1.525, 1.7689) for all r ≥ 13.Source: §3 · p. 6, Figure 3 · p. 6
  • For k = 15, the corresponding component ranges intersect at α ∈ (1.314, 1.648).Source: §3 · p. 7, Figure 4 · p. 7
  • For k = 12, the component ranges intersect at α ∈ (1.2274, 1.435), completing coverage of the lower end of the target interval.Source: §3 · p. 7, Figure 5 · p. 8

4 Handling r ∈{19, 20, 21, 22, 23, 24} and most of r ∈{25, 26}

The section proves Albertson’s Conjecture for r≤24 and reduces possible counterexamples for r≤26 to three specific (r,|G|) pairs. It combines edge bounds, sampled subgraphs, and random-subgraph estimates across order intervals.

  • Lemma 5 supplies three crossing-number inequalities for r<n<2r, including a stronger bound when G has no subdivision of K_r.Source: §4 · p. 8
  • For r≤24, every r-critical graph satisfies cr(G)≥cr(K_r); for r≤26, any counterexample must have (r,|G|)∈{(25,48),(26,50),(26,51)}.Source: §4 · p. 9
  • Previous results handle r≤18, while this section’s calculations extend the verified range beginning at r=19.Source: §4 · p. 9
  • The proof divides each possible order range into six intervals and excludes them using subdivision results, sampled 12-, 22-, and 24-vertex subgraphs, and a random-subgraph argument.Source: §4 · pp. 9–10
  • The final verification compares each interval’s crossing-number lower bound with the standard lower bound on cr(K_r), with the complete calculation summarized in Table 1.Source: Table 1 · p. 9, §4 · p. 10

5 Excluding more values of |G| when r is Large

This section adapts weak-immersion methods to exclude additional orders of counterexamples, including ranges that apply for sufficiently large r. Its main result covers n≤1.23r and yields stronger lower-order exclusions as r increases.

  • Earlier asymptotic work applied only for very large r, whereas the adapted argument targets smaller r and strengthens the excluded order range to 1.768r.Source: §5 · p. 10
  • The method partitions V(G) into parts, selects subsets U_i and W_i, and obtains a weak immersion of K_r avoiding the edges of G[W].Source: §5 · p. 10
  • Crossings in the immersion are bounded below by cr(K_r) minus an error term, while the induced subgraph G[W] supplies enough additional crossings to recover cr(G)≥cr(K_r).Source: §5 · pp. 10–11
  • Theorem 7 excludes counterexamples for r-critical graphs with n≤1.23r whenever its stated numerical hypothesis holds.Source: §5 · pp. 10–11
  • If r≥125,000 and 1.10r≤n≤1.23r, or r≥825,000 and 1.05r≤n≤1.23r, then an r-critical graph is not a counterexample.Source: §5 · pp. 10–11

Appendix A: Proof of Theorem I

The appendix proves the weak-immersion crossing bound by converting a drawing into a plane embedding containing a subdivision of K_r. It counts the crossings introduced by rerouting paths around branch and non-branch vertices.

  • A weak immersion of K_r satisfies cr(G′)≥cr(K_r)−n(n−r)(n+2r)/8.Source: Appendix A · p. 11
  • The proof reroutes paths that pass through branch vertices until the resulting plane embedding contains a subdivision of K_r.Source: Appendix A · p. 11
  • New crossings are separated into those already present in the original drawing and those created during rerouting.Source: Appendix A · p. 11
  • Rerouting near branch vertices creates at most r(n−r)n/4 crossings, while rerouting near non-branch vertices creates at most (n−r)n^2/8.Source: Appendix A · p. 12
  • Adding both contributions gives the total introduced-crossing bound n(n−r)(n+2r)/8.Source: Appendix A · p. 12

Appendix B: Python Code to Generate Table 1

Appendix B provides Python code that generates the table used to verify Proposition 2. The code evaluates interval bounds for r from 15 through 26 using several sampling inequalities and probabilities.

  • The helper function rounds interval endpoints outward so the generated ranges are conservative integer intervals.Source: Appendix B · p. 12
  • The k=12, k=22, and k=24 inequalities use different edge bounds to compute excluded order intervals.Source: Appendix B · p. 12
  • The final lemma calculation uses a prescribed vertex-inclusion probability p together with the Kostochka–Stiebitz edge bound and the crossing estimate from Theorem A.Source: Appendix B · p. 12

Related papers

Loading 2512.08020v1…