PaperlayerView exact revision on arXiv

Source-linked AI summary

Albertson's Conjecture Holds for r at Most 26

Ankan Sadhu

arXiv:2609.01682v1math.COcs.CGcs.DM

TL;DR

The paper addresses whether r-critical graphs with r in {25, 26} satisfy the crossing-number lower bound cr(K_r). Using published edge and crossing-number bounds, it settles the remaining cases, proves Albertson’s Conjecture for all r <= 26, and derives a structural restriction for potential counterexamples at r = 27.

  • Problem

    The central question is whether every r-chromatic graph has crossing number at least cr(K_r), including the unresolved r-critical cases for r in {25, 26}.

  • Method

    The proofs combine published lower bounds on |E(G)| and cr(G), with the latter obtained from the Crossing Lemma applied to random induced subgraphs, plus join-based arguments when the complement is disconnected.

  • Results

    Albertson’s Conjecture holds for every r <= 26, and any 27-critical graph with cr(G) < cr(K_27) has order 53 or 54 and connected complement.

  • Takeaways & Limitations

    The remaining cases r = 25 and r = 26 are settled, while a possible counterexample at r = 27 is restricted to two orders and connected complements.

  • Takeaways & Limitations

    The proof retains a published-work theorem with the hypothesis n < 3.57r, although a cited result provides a stronger available range.

Abstract

from arXiv · show

Albertson conjectured that every graph with chromatic number r has crossing number at least cr(K_r). The conjecture was verified for r <= 12 by Albertson, Cranston and Fox, for r <= 16 by Bar'at and T'oth, for r <= 18 by Ackerman, and recently for r <= 24 by Cranston, who reduced the remaining cases r in {25, 26} to three orders. We settle those three orders, so that Albertson's Conjecture holds for all r <= 26. Only published results are used, and an appendix reproves the range 19 <= r <= 24 so that the case r <= 26 does not rest on unpublished work. We also show that if chi(G) = 27 and cr(G) < cr(K_27), then G has a 27-critical subgraph of order 53 or 54 whose complement is connected.

1 Introduction

The paper proves Albertson’s Conjecture for r-critical graphs with r in {25, 26}, completing the conjecture for every r <= 26. It combines published edge and crossing-number bounds with new arguments for the remaining orders and also constrains hypothetical counterexamples at r = 27.

  • Conjecture and setup: Albertson’s Conjecture states that every graph with chromatic number at least r has crossing number at least cr(K_r).The crossing number is the minimum number of edge crossings in a plane drawing.
  • Main result: Theorem 1.1 proves cr(G) >= cr(K_r) for every r-critical graph with r in {25, 26}.Because every r-chromatic graph contains an r-critical subgraph and crossing number is monotone under subgraphs, this settles the corresponding cases.
  • Main result: Albertson’s Conjecture therefore holds for every r <= 26.Earlier work had established the conjecture through r <= 24.
  • Further consequence: If a 27-critical graph violates the conjectured bound, it has order 53 or 54 and connected complement.The appendix also reproves the range 19 <= r <= 24 using published results only.
  • Proof strategy: The proof uses published results and combines edge-count lower bounds with crossing-number bounds derived from the Crossing Lemma applied to random induced subgraphs.The resulting inequality is increasing and linear in the number of edges, so stronger edge bounds improve the crossing-number estimate.
  • Proof strategy: New arguments handle the critical boundary n = 2r - 2 by exploiting Gallai’s join structure and splitting according to whether a join part is a single vertex.This dispatch settles the orders 48 and 50; integrality of |E(G)| closes the case (r, |G|) = (26, 51).

2 Preliminaries

The preliminaries reduce Albertson’s Conjecture to crossing-number bounds for critical graphs, supported by edge-density estimates, averaging, structural lemmas, and subdivision arguments.

  • Crossing-number target: The two-circle drawing gives cr(K_r) ≤ Z(r), so proving cr(G) ≥ Z(r) suffices for Albertson’s Conjecture.For large r, the best known lower bound on cr(K_r) is at least 98.5% of Z(r).
  • Crossing-number bounds: Lemma 2.1 supplies the crossing bound cr(G) ≥ 5m/9 − 203/9, with the constant 203/9 essential for settling orders (25,49) and (26,51).The proceedings version’s weaker constant 407/18 does not settle those orders.
  • Averaging: Averaging over induced k-vertex subgraphs transfers edge lower bounds into crossing-number lower bounds because the resulting inequality is increasing and linear in m.The method counts inherited edges and crossings across all k-element vertex subsets.
  • Critical-graph edge bounds: For r-critical graphs, Lemmas 2.3–2.5 provide complementary edge bounds, including m ≥ r^2 − r − 1 when n ≥ 2r − 1 and stronger bounds when no K_r subdivision exists.The bounds cover ranges near 2r and exploit the absence of a subdivision of K_r.
  • Subdivision reduction: A subdivision of K_r in G already implies cr(G) ≥ cr(K_r), because smoothing subdivided paths produces a drawing of K_r with no more crossings.Thus the remaining analysis may assume that no subdivision of K_r exists.

3 Critical graphs with disconnected complement

The section strengthens edge lower bounds for critical graphs whose complement is disconnected, using Gallai’s join structure and a separate treatment when one join part is a single vertex. These bounds settle the exceptional order n = 2r −2 cases needed in the main proof.

  • Scope of the argument: The join argument is specific to complements with a singleton part or sufficiently dense disconnected structure; it is not extended to joins whose two parts both have order greater than 1.The authors explicitly leave the routing problem for missing pairs in such joins untreated.
  • Singleton join part: A join with one singleton part has the form G = K1 ∨H, where H is (r −1)-critical and contains no subdivision of K_{r−1}.A subdivision of K_{r−1} in H would lift to a subdivision of K_r in G.
  • Singleton join part: Applying the edge bound to H and counting the edges incident with the universal vertex gives a lower bound on m = |E(G)|.The bound uses m = (n −1) + |E(H)| together with Theorem 2.5 applied to H.
  • No singleton part: When no join part is a singleton, every part has at least 5 vertices, so the number of parts satisfies 2 ⩽t ⩽r/3.The argument combines criticality, the absence of subdivisions, and complete adjacency between distinct parts.
  • No singleton part: For fixed t, the relevant bound is minimized by maximizing the product of the part chromatic numbers, and σ(t) −σ(2) is nonnegative.The comparison yields σ(t) ⩾σ(2), with equality handled at the two-part configuration.
  • No singleton part: The resulting estimate is m ⩾σ(2) = r^2 + 3r −19 for the non-singleton case.This is the second quantity in the proposition’s lower bound.

4 Proof of Theorem 1.1

The proof reduces possible counterexamples for r ∈{25, 26} to finitely many orders, dispatches all orders except n = 2r −2 by tabulated crossing estimates, and handles the exceptional order using disconnected complements. This proves the critical-graph theorem and hence Albertson’s Conjecture through r = 26.

  • Reduction to finite orders: A hypothetical counterexample has no subdivision of K_r and satisfies r + 5 ⩽n < 3.57r, reducing the analysis to a finite range of orders.The lower and upper order bounds come from Theorems 2.6 and 2.7.
  • Non-exceptional orders: For every admissible n other than n = 2r −2, evaluating the crossing estimate at m = f(r, n) gives cr(G) > Z(r), a contradiction.Table 1 records the order where the bound is least on each interval and its exact value.
  • Exceptional order: At n = 2r −2, disconnectedness of the complement invokes the join-based theorem, yielding m ⩾609 for r = 25 and m ⩾659 for r = 26.Substituting these bounds into the crossing estimate again produces a contradiction.
  • Conclusion: Theorem 1.1 follows for r ∈{25, 26}, and the appendix independently supplies the range 19 ⩽r ⩽24 using published results.Together with earlier results, this establishes the conjecture for every r ⩽26.
  • Numerical verification: The numerical margins are narrow: the smallest tabulated ratio to Z(r) is less than 1.001 at (r, n) = (25, 52).This motivates recording the tabulated values as exact rationals.
  • Scope of the proof: The proof retains the published bound n < 3.57r even though stronger published or unpublished alternatives could shorten the finite ranges.The stated reason is to keep the tables based on published work alone.

5 The orders left open at r = 27

For a hypothetical 27-critical counterexample, the proof excludes every order except 52, 53, and 54, then uses connectivity and edge bounds to restrict the order to 53 or 54. The remaining ranges are exact for the present Z(27)-based estimate, whose target value is unknown.

  • Order reduction: 32 ≤ n ≤ 96 initially, but all orders outside 52, 53, and 54 yield cr(G) > Z(27) = 6084.The excluded orders are dispatched using the lower bound m = f(27, n) and the k values in Table 2.
  • Connectivity: 712, 725, and 739 are the disconnected-case lower bounds for m at n = 52, 53, and 54, respectively.Applying the crossing-number estimate with k = 23 for n = 52, 53 and k = 24 for n = 54 exceeds Z(27).
  • Connectivity: n = 52 is impossible because connectivity contradicts the theorem forbidding connected graphs of order 2 · 27 − 2 in this setting.Thus only n = 53 and n = 54 survive, and the complement of G is connected.
  • Order reduction: The three exceptional orders are treated separately because Table 2 dispatches only the other orders.Table 2 records values exceeding Z(27) = 6084, while orders 52, 53, and 54 require a separate argument.
  • Remaining edge cases: The surviving edge cases are m = 726 at n = 54 and m ∈ {713, 714, 715} at n = 53.At n = 54, the lower bound gives m ≥ 726 while 727 would be needed, so equality is the only surviving possibility.
  • Scope: The ranges are exact only for the present Z(27)-based estimate because cr(K27) is unknown.Improving constants in the crossing-number bound could close the n = 54 case directly.

A The range 19 ⩽r ⩽24

The appendix independently proves Albertson’s Conjecture for 19 ≤ r ≤ 24 using published results. It dispatches all admissible orders through tabulated bounds, treating n = 2r − 2 separately via disconnected complements.

  • Statement: Albertson’s Conjecture holds for 19 ≤ r ≤ 24, so the result does not rely on the unpublished source [9].The appendix records this range as Proposition A.1.
  • Dispatch: For admissible orders other than n = 2r − 2, the tabulated estimates give cr(G) > Z(r) ≥ cr(Kr).The proof uses m = f(r, n) and the k values in Table 3.
  • Exceptional order: n = 2r − 2 is handled separately because the complement is disconnected and Theorem 3.2 supplies a stronger lower bound on m.The resulting estimates again give cr(G) > Z(r).
  • Numerical thresholds: The comparison values are Z(19) = 1296, Z(20) = 1620, Z(21) = 2025, Z(22) = 2475, Z(23) = 3025, and Z(24) = 3630.Each Table 3 value exceeds the corresponding Z(r).
  • Exceptional order: For n = 2r − 2, the second quantity r^2 + 3r − 19 exceeds the first quantity in every listed case.These values are recorded in Table 4.
Loading 2609.01682v1…