pith. sign in

arxiv: 1906.09598 · v2 · pith:BXIA6MKWnew · submitted 2019-06-23 · 🧮 math.CO

Counting critical subgraphs in k-critical graphs

Jie Ma , Tianchi Yang This is my paper

Pith reviewed 2026-05-25 17:53 UTC · model grok-4.3

classification 🧮 math.CO
keywords 4-critical graphsodd cyclesGallai's problemcycle countingcritical subgraphs3-connected graphsparity cycles
0
0 comments X

The pith

Any 4-critical graph on n vertices contains Ω(n²) odd cycles.

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

The paper proves a quadratic lower bound on the number of odd cycles in any 4-critical graph. This strengthens the earlier linear bound and matches the growth rate of known infinite families of such graphs. The authors first obtain the same quadratic count in every 3-connected non-bipartite graph, then transfer the tools to the 4-critical setting. The same machinery supplies a short proof that every 4-critical graph contains at least linearly many 3-critical subgraphs and raises the general lower bound on the number of (k-1)-critical subgraphs inside k-critical graphs for k at least 5.

Core claim

Any 4-critical graph on n vertices contains Ω(n²) odd cycles. The same bound holds for every 3-connected non-bipartite graph. These counting results also give a short proof of Gallai's 1984 question in the case k=4 and improve the longstanding Abbott-Zhou bound from Ω(n^{1/(k-1)}) to Ω(n^{1/(k-2)}) for every k at least 5.

What carries the argument

Novel tools for counting cycles of specified parity.

If this is right

  • Every 4-critical graph contains Ω(n²) distinct 3-critical subgraphs.
  • The quadratic bound is tight up to a constant factor.
  • The same quadratic count holds in every 3-connected non-bipartite graph.
  • For k at least 5 the number of (k-1)-critical subgraphs in a k-critical graph is at least Ω(n^{1/(k-2)}).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The parity tools may apply to other hereditary graph classes that are not bipartite.
  • Quadratic growth in one parity may imply similar growth for other fixed cycle lengths inside critical graphs.
  • The improved exponent for general k suggests that further refinements of the exponent 1/(k-2) are possible.

Load-bearing premise

The parity-cycle counting tools suffice to produce a quadratic lower bound once they are applied inside 4-critical graphs.

What would settle it

An explicit infinite family of 4-critical graphs in which the number of odd cycles is o(n²) would refute the main claim.

read the original abstract

Gallai asked in 1984 if any $k$-critical graph on $n$ vertices contains at least $n$ distinct $(k-1)$-critical subgraphs. The answer is trivial for $k\leq 3$. Improving a result of Stiebitz, Abbott and Zhou proved in 1995 that for all $k\geq 4$, such graph contains $\Omega(n^{1/(k-1)})$ distinct $(k-1)$-critical subgraphs. Since then no progress had been made until very recently, Hare resolved the case $k=4$ by showing that any $4$-critical graph on $n$ vertices contains at least $(8n-29)/3$ odd cycles. In this paper, we mainly focus on 4-critical graphs and develop some novel tools for counting cycles of specified parity. Our main result shows that any $4$-critical graph on $n$ vertices contains $\Omega(n^2)$ odd cycles, which is tight up to a constant factor by infinite many graphs. As a crucial step, we prove the same bound for 3-connected non-bipartite graphs, which may be of independent interest. Using the tools, we also give a very short proof for the case $k=4$. Moreover, we improve the longstanding lower bound of Abbott and Zhou to $\Omega(n^{1/(k-2)})$ for the general case $k\geq 5$. We will also discuss some related problems on $k$-critical graphs in the final section.

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.

Referee Report

0 major / 3 minor

Summary. The paper addresses Gallai's 1984 question on the minimum number of distinct (k-1)-critical subgraphs in a k-critical graph on n vertices. Building on Stiebitz and Abbott-Zhou, it develops new tools for counting cycles of specified parity. The main results are: (i) every 4-critical graph on n vertices contains Ω(n²) odd cycles (tight up to a constant factor via infinitely many graphs), with the same quadratic bound first proved for 3-connected non-bipartite graphs; (ii) a short proof of Hare's linear lower bound for k=4; and (iii) an improvement of the Abbott-Zhou exponent from 1/(k-1) to Ω(n^{1/(k-2)}) for all k≥5.

Significance. If the derivations hold, the quadratic lower bound for 4-critical graphs is a substantial advance, matching the order of magnitude of the extremal constructions and improving the prior linear bound of Hare. The parity-specific cycle-counting tools and the extension to 3-connected non-bipartite graphs are of independent interest. The improved general exponent for k≥5 is a modest but clean strengthening of a long-standing result. The manuscript ships explicit constructions establishing tightness and a short proof of the k=4 case.

minor comments (3)
  1. [Abstract] Abstract, line 8: 'infinite many graphs' should read 'infinitely many graphs'.
  2. [Introduction] The statement that the Ω(n²) bound is 'tight up to a constant factor' should be accompanied by an explicit reference to the construction (or a brief description) already in the introduction, rather than deferred entirely to the final section.
  3. [Section 2] Notation for the parity-specific counting functions (e.g., the functions introduced to count odd cycles) should be defined once in a dedicated notation subsection or table rather than re-introduced piecemeal in each lemma.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive evaluation of our manuscript and for recommending minor revision. The report accurately summarizes our contributions, and we appreciate the recognition of the quadratic bound for 4-critical graphs and the improved exponent for k≥5 as advances over prior work.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation relies on newly developed tools for parity-specific cycle counting, applied first to 3-connected non-bipartite graphs and then to 4-critical graphs. The quadratic bound is presented as a novel improvement over Hare's linear bound (from independent prior work) and is shown tight by explicit infinite families. No self-citations are load-bearing, no parameters are fitted then renamed as predictions, and no ansatz or uniqueness claim reduces to the authors' own prior definitions. The central result is obtained by direct counting arguments rather than by construction from the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no details on parameters, axioms, or new entities; the work appears to rely on standard graph theory definitions and new combinatorial arguments without introducing fitted parameters or invented entities.

pith-pipeline@v0.9.0 · 5801 in / 1230 out tokens · 42165 ms · 2026-05-25T17:53:40.263800+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

  1. [1]

    Abbott and B

    H. Abbott and B. Zhou, Some remarks on ( k − 1)-critical subgraphs of k-critical graphs, Combinatorica 15 (1995), 469–474

    work page 1995

  2. [2]

    G. A. Dirac, The structure of k-chromatic graphs, Fund. Math. 40 (1953), 42–55

    work page 1953

  3. [3]

    G. A. Dirac, On the structure of 5- and 6-chromatic abstra ct graphs, J. Reine Angew. Math. 214/215 (1964), 43–52

    work page 1964

  4. [4]

    Hare, Tools for counting odd cycles in graph, J

    D. Hare, Tools for counting odd cycles in graph, J. Combin. Theory Ser. B , in press (30 pages), https://doi.org/10.1016/j.jctb.2019.03.003

    work page doi:10.1016/j.jctb.2019.03.003 2019

  5. [5]

    Jensen and B

    T.R. Jensen and B. Toft, Graph Coloring Problems, Wiley- Intersci. Ser. Discrete Math. Optim., John Wiley & Sons, New York, 1995

    work page 1995

  6. [6]

    Kawarabayashi, B

    K. Kawarabayashi, B. Reed and O. Lee, Removable cycles in non-bipartite graphs, J. Combin. Theory Ser. B 99 (2009), 30–38

    work page 2009

  7. [7]

    Kostochka and M

    A. Kostochka and M. Yancey, Ore’s conjecture for k = 4 and Gr¨ otzsch’s theorem,Combinatorica 34 (2014), 323–329

    work page 2014

  8. [8]

    Krusenstjerna-Hafstrøm and B.Toft, Special subdivi sions of K4 and 4-chromatic graphs, Monatsh

    U. Krusenstjerna-Hafstrøm and B.Toft, Special subdivi sions of K4 and 4-chromatic graphs, Monatsh. Math. 89 (1980), 101–110

    work page 1980

  9. [9]

    Shapira and R

    A. Shapira and R. Thomas, Color-critical graphs have log arithmic circumference, Adv. Math. 227 (2011), 2309–2326

    work page 2011

  10. [10]

    Stiebitz, Subgraphs of colour-critical graphs, Combinatorica 7 (1987), 303–312

    M. Stiebitz, Subgraphs of colour-critical graphs, Combinatorica 7 (1987), 303–312. 15

    work page 1987