pith. sign in

arxiv: 2605.04022 · v1 · submitted 2026-05-05 · 🧮 math.CO

Coloring graphs with independence number two and no odd clique immersions

Henry Echeverr\'ia , Jessica McDonald This is my paper

Pith reviewed 2026-05-07 04:07 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C1505C83
keywords chromatic numberindependence numberstrong odd immersionclique immersiongraph coloringimmersion-free graphs
0
0 comments X

The pith

If a graph has independence number at most two and no strong odd K_t-immersion, then its chromatic number is at most ceil(3(t-1)/2).

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

The paper proves an upper bound on the chromatic number for graphs that have independence number at most two and that exclude strong odd immersions of a clique K_t. The bound is linear in t, specifically the ceiling of three-halves times (t minus one). A sympathetic reader would care because the result ties a restriction on non-adjacent vertices to the absence of a particular topological embedding to control the number of colors needed. This connects two structural conditions that together prevent the graph from requiring arbitrarily many colors. The proof approach combines these conditions to support an inductive or decomposition argument.

Core claim

The authors prove that for any positive integer t, if a graph G satisfies α(G) ≤ 2 and contains no strong odd immersion of K_t, then χ(G) ≤ ⌈3(t−1)/2⌉. The bound follows from the interaction between the small independence number, which limits the spread of non-adjacent vertices, and the exclusion of strong odd clique immersions, which restricts certain path-based embeddings with parity conditions.

What carries the argument

Strong odd immersion of K_t, an embedding of the clique into the graph using internally disjoint paths whose edge parities satisfy specific oddness conditions; its absence, paired with α(G) ≤ 2, limits the possible dense substructures that would otherwise force high chromatic number.

If this is right

  • For t=3 the bound simplifies to χ(G) ≤ 3, so such graphs are 3-colorable.
  • The chromatic number grows at most linearly with the size of the excluded immersion rather than unboundedly.
  • The class of graphs satisfying both conditions admits an explicit coloring bound expressed directly in terms of t.
  • The result applies even to graphs that may contain large cliques, provided the independence number stays at most two and the immersion is absent.

Where Pith is reading between the lines

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

  • Checking the bound for small fixed t, such as t=5 where the ceiling is 6, could reveal whether the constant factor 3/2 is tight by searching for example graphs.
  • The same structural restrictions might be usable to bound other coloring variants such as the list chromatic number in this class of graphs.
  • Analogous linear bounds could be sought when the immersion parameter is replaced by other forbidden substructures or when independence number is allowed to grow slowly with t.

Load-bearing premise

The structural properties of graphs with α(G)≤2 combined with the absence of strong odd immersions permit an inductive or decomposition argument that yields the stated linear bound on χ(G).

What would settle it

A single graph G with α(G)=2, containing no strong odd immersion of K_t, yet with χ(G) > ⌈3(t-1)/2⌉ would falsify the claim; for t=4 this would be a graph requiring 6 colors with no strong odd K_4-immersion.

Figures

Figures reproduced from arXiv: 2605.04022 by Henry Echeverr\'ia, Jessica McDonald.

Figure 1
Figure 1. Figure 1: Illustration of the paths from Claim 3 At this point consider the sets Pv, T ∗ again, noting that we have so far only added to Pv those paths which are single edges from v to T1 ∪ T2. We consider all these paths to be type 1 paths. At 4 view at source ↗
Figure 2
Figure 2. Figure 2: Four types of odd paths in Pv that begin at v ∈ Z1 and end in T1. After adding paths of types 1 through 4 to each Pv, we get the following. We will use the notation that for some vertex v and set X ⊆ V (G), dX(v) is the number of neighbors of v in X. Claim 4. Let {i, j} = {1, 2}. For any v ∈ Zi, t − 1 > |Pv| ≥ d(v) − |Bj | − 1. Proof of Claim. Suppose without loss that that i = 1 and let v ∈ Z1. Note that … view at source ↗
Figure 3
Figure 3. Figure 3: Paths from the proofs of Claims 6 and 7. Claim 6. A1 = B1. Proof of Claim. Suppose there exists an edge aw ∈ E(G) with a ∈ A1, w ∈ Z1. Choose any vertices v ∈ Z1 \ {w} and z1 ∈ Z2 \ zv; we know such vertices exist by Claim 2. See the top-left picture in view at source ↗
read the original abstract

We study the chromatic number of graphs that exclude a clique as a strong odd immersion and have independence number two. Given a graph $G$ and $t\in\mathbb{Z}^+$, we prove that if $\alpha(G)\leq 2$ and $G$ has no strong odd $K_t$-immersion, then $\chi(G)\leq \lceil \frac{3(t-1)}{2}\rceil$.

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 proves that if a graph G satisfies α(G) ≤ 2 and contains no strong odd K_t-immersion, then χ(G) ≤ ⌈3(t−1)/2⌉. The argument proceeds by induction on |V(G)|: a minimal counterexample either has a vertex of degree at most ⌈3(t−1)/2⌉−1 (which can be colored after removing it) or admits a cut-set whose components inherit the forbidden-immersion property and can be colored inductively, with the α ≤ 2 condition used to control common neighbors and extend the coloring.

Significance. The result supplies a concrete linear bound on chromatic number for a natural class of graphs defined by a forbidden strong odd immersion together with bounded independence number. The derivation is parameter-free and relies on a direct inductive decomposition that exploits the α ≤ 2 hypothesis to close coloring extensions; these features make the claim falsifiable and potentially useful for further work on immersion-chromatic number relations.

minor comments (3)
  1. [§2] §2: the definition of a strong odd K_t-immersion (branch vertices joined by internally disjoint odd-length paths) should be accompanied by a brief comparison to the ordinary odd-immersion notion to make the strengthening explicit.
  2. [Proof of Theorem 1.1] Proof of the main theorem: while the inductive step is outlined, an explicit verification of the base cases t = 1 and t = 2 (where the bound gives χ ≤ 1 or 2) would remove any doubt about the starting point of the induction.
  3. [Throughout] Throughout: a uniform notation for the paths realizing the immersion (e.g., consistently labeling the internal vertices) would improve readability when the same paths are reused in the cut-set argument.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful summary of our main theorem and for the positive assessment of its significance. The recommendation of minor revision is noted. No major comments appear in the report, so we have no specific points requiring rebuttal or clarification at this stage. Any minor editorial adjustments will be incorporated in the revised version.

Circularity Check

0 steps flagged

No significant circularity: standard inductive structural proof

full rationale

The manuscript proves the stated bound by induction on |V(G)| for a minimal counterexample G satisfying α(G)≤2 and containing no strong odd K_t-immersion. It locates either a vertex of degree at most ⌈3(t-1)/2⌉−1 or a cut-set whose components inherit both hypotheses, then extends a proper coloring from the smaller graphs using the α≤2 condition to guarantee that non-adjacent vertices share at most one common neighbor. All steps are derived directly from the definitions of strong odd immersion (branch vertices joined by internally disjoint odd-length paths) and independence number; no parameter is fitted to data and then renamed a prediction, no self-citation supplies a load-bearing uniqueness theorem, and no ansatz is smuggled in. The derivation is therefore self-contained against the given forbidden-structure hypotheses.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The proof rests on the standard axiomatic framework of graph theory (undirected simple graphs, paths, immersions defined via vertex mappings and edge-disjoint paths) plus the specific definition of 'strong odd' immersion; no new entities or fitted constants are introduced.

axioms (1)
  • standard math Standard definitions of chromatic number, independence number, clique immersion, and strong odd immersion as used in the literature on graph immersions.
    The paper invokes these established notions without re-deriving them.

pith-pipeline@v0.9.0 · 5357 in / 1239 out tokens · 62305 ms · 2026-05-07T04:07:00.084081+00:00 · methodology

Review history (2 revisions) →

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

20 extracted references · 20 canonical work pages

  1. [1]

    Abu-Khzam, and M.A

    F.N. Abu-Khzam, and M.A. Langston,Graph coloring and the immersion order. In: T. Warnow, and B. Zhu (eds) Computing and Combinatorics. COCOON 2003. Lecture Notes in Computer Science, vol 2697. Springer, Berlin, Heidelberg. 7

    work page 2003

  2. [2]

    Botler, C

    F. Botler, C. G. Fernandes, C. N. Lintzmayer, R. A. Lopes, S. Mishra, B. L. Netto, and M. Sam- binelli,Immersions of large cliques in graphs with independence number 2 and bounded maximum degree. Preprint, arXiv:2506.09768 [math.CO]

    work page arXiv

  3. [3]

    Bustamante, D.A

    S. Bustamante, D.A. Quiroz, M. Stein, and J. Zamora,Clique immersions and independence number. European J. Combin., 106:103550, 2022

    work page 2022

  4. [4]

    Churchley,Odd disjoint trails and totally odd graph immersions

    R. Churchley,Odd disjoint trails and totally odd graph immersions. PhD thesis, Simon Fraser University, 2017

    work page 2017

  5. [5]

    DeVos, Z

    M. DeVos, Z. Dvoˇ r´ ak, J. Fox, J. McDonald, B. Mohar, and D. Scheide,A minimum degree condition forcing complete graph immersion. Combinatorica, 34:279–298, 2014

    work page 2014

  6. [6]

    DeVos, K

    M. DeVos, K. Kawarabayashi, B. Mohar, and H. Okamura, Immersing small complete graphs, Ars Mathematics Contemporanea3(2010), 139–146

    work page 2010

  7. [7]

    Diestel,Graph Theory, Graduate Texts in Mathematics, vol

    R. Diestel,Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer, 2012

    work page 2012

  8. [8]

    Echeverr´ ıa, A

    H. Echeverr´ ıa, A. Jim´ enez, S. Mishra, A. Pastine, D. A. Quiroz, and M. Y´ epez,Totally odd subdivisions in Kneser graphs. Preprint, arXiv:2505.02812 [math.CO]

    work page arXiv

  9. [9]

    Echeverr´ ıa, A

    H. Echeverr´ ıa, A. Jim´ enez, S. Mishra, D. A. Quiroz, and M. Y´ epez,Totally odd immersions of complete graphs in graph products. Preprint, arXiv:2502.10227 [math.CO]

    work page arXiv

  10. [10]

    Gallai,Kritische Graphen

    T. Gallai,Kritische Graphen. II. Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl.8(1963), 373–395

    work page 1963

  11. [11]

    Gauthier, T.-N

    G. Gauthier, T.-N. Le, and P. Wollan,Forcing clique immersions through chromatic number. European J. Combin., 81:98–118, 2019

    work page 2019

  12. [12]

    Jim´ enez, D.A

    A. Jim´ enez, D.A. Quiroz, and C. Thraves Caro,Totally odd immersions in line graphs. Discrete Math., 347(4):113862, 2024

    work page 2024

  13. [13]

    K¨ uhn, L

    M. K¨ uhn, L. Sauermann, R. Steiner, and Y. Wigderson,Disproof of the Odd Hadwiger Conjecture. Preprint, arXiv:2512.20392 [math.CO]

    work page arXiv

  14. [14]

    McFarland,Coloring graphs with no totally odd clique immersion

    C. McFarland,Coloring graphs with no totally odd clique immersion. Preprint, arXiv:2508.08119 [math.CO]

    work page arXiv

  15. [15]

    K.-i Kawarabayashi.Totally odd subdivisions and parity subdivisions: Structures and Coloring. Proc. of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1013–1029, 2013

    work page 2013

  16. [16]

    Lescure, and H

    F. Lescure, and H. Meyniel,On a problem upon configurations contained in graphs with given chromatic number. Ann. Discrete Math., 41:325–331, 1989

    work page 1989

  17. [17]

    Quiroz, personal communication, 2026

    D.A. Quiroz, personal communication, 2026

    work page 2026

  18. [18]

    Thomassen,Totally Odd -subdivisions in 4-chromatic Graphs

    C. Thomassen,Totally Odd -subdivisions in 4-chromatic Graphs. Combinatorica, 21:417–443, 2001

    work page 2001

  19. [19]

    Vergara,Complete graph immersions in dense graphs

    S. Vergara,Complete graph immersions in dense graphs. Discrete Mathematics340(5) (2017), 1019–1027

    work page 2017

  20. [20]

    Zang,Proof of Toft’s Conjecture: Every Graph Containing No Fully OddK 4 is 3-Colorable

    W. Zang,Proof of Toft’s Conjecture: Every Graph Containing No Fully OddK 4 is 3-Colorable. J. Comb. Optim. 2:117–188, 1998. 8 Appendix Theorem A.1.Everyn-vertex graphGwithα(G)≤2has a strong oddK ⌈n/3⌉-immersion. Proof.Suppose not, and choose a counterexampleGwithnminimum;Gis ann-vertex graph with α(G)≤2 that has no strong oddK ⌈n/3⌉-immersion. Denote the ...

    work page 1998