pith. sign in

arxiv: 2506.23054 · v2 · submitted 2025-06-29 · 🧮 math.CO

Edge-colouring and orientations: applications to degree- and chi-boundedness

Arnab Char , Ken-ichi Kawarabayashi , Lucas Picasarri-Arrieta This is my paper

Pith reviewed 2026-05-19 08:13 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C1505C20
keywords edge-colouringRamsey theoremdegree-boundednessorientationshereditary classestransitive tournamentantidirected digraph
0
0 comments X

The pith

Every 2-edge-coloured graph with large minimum degree has a monochromatic induced subgraph with large minimum degree too.

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

The paper proves a generalization of Ramsey's theorem: every 2-edge-coloured graph with sufficiently large minimum degree contains a monochromatic induced subgraph whose minimum degree remains large. From this it derives a parallel statement for orientations, where a graph with large minimum degree yields either a large transitive tournament or an induced antidirected digraph that keeps large minimum degree. These statements supply two general tools for showing that extensions of degree-bounded hereditary classes remain degree-bounded. Concrete applications include proofs that odd-signable graphs and Burling graphs are degree-bounded, together with an exact characterization of the oriented graphs F such that the class of graphs admitting an F-free orientation is degree-bounded. A reader interested in structural graph theory would care because the results give reusable methods for preserving minimum-degree bounds inside hereditary classes.

Core claim

We prove a new generalisation of Ramsey's theorem by showing that every 2-edge-coloured graph with sufficiently large minimum degree contains a monochromatic induced subgraph whose minimum degree remains large. From this, we also derive that every orientation of a graph with large minimum degree contains either a large transitive tournament or an induced antidirected digraph whose minimum degree is still large. As a consequence, we obtain two general tools showing that certain extensions of degree-bounded graph classes preserve degree-boundedness. With these tools, we obtain for instance that odd-signable graphs and Burling graphs are degree-bounded. We also characterise exactly the oriented

What carries the argument

Monochromatic induced subgraph that preserves large minimum degree inside a 2-edge-coloured graph

If this is right

  • Odd-signable graphs are degree-bounded.
  • Burling graphs are degree-bounded.
  • Extensions of degree-bounded hereditary classes under the paper's two tools preserve degree-boundedness.
  • The graphs admitting an orientation without induced copies of a given oriented graph F are degree-bounded precisely when F meets the paper's exact conditions.

Where Pith is reading between the lines

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

  • The same degree-preservation tools could be applied to other hereditary classes already known to be degree-bounded.
  • Because the title mentions χ-boundedness, parallel statements for chromatic-number bounds may follow from the same arguments.
  • The orientation result offers a template for studying minimum-degree preservation in directed graphs beyond the cases treated here.

Load-bearing premise

The hereditary classes under study satisfy the stated definition of degree-boundedness, namely that for every integer s there exists d(s) such that every member either contains K_{s,s} or has minimum degree at most d.

What would settle it

A single 2-edge-coloured graph whose minimum degree is arbitrarily large yet every monochromatic induced subgraph has bounded minimum degree.

Figures

Figures reproduced from arXiv: 2506.23054 by Arnab Char, Ken-ichi Kawarabayashi, Lucas Picasarri-Arrieta.

Figure 1
Figure 1. Figure 1: An edge-labelling of the cube witnessing that it is odd-signable. [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
read the original abstract

We prove a new generalisation of Ramsey's theorem by showing that every $2$-edge-coloured graph with sufficiently large minimum degree contains a monochromatic induced subgraph whose minimum degree remains large. From this, we also derive that every orientation of a graph with large minimum degree contains either a large transitive tournament or an induced antidirected digraph whose minimum degree is still large. As a consequence, we obtain two general tools showing that certain extensions of degree-bounded graph classes preserve degree-boundedness. A hereditary class $\mathcal{G}$ is {\it degree-bounded} if, for every integer $s$, there exists $d=d(s)$ such that every graph $G\in \mathcal{G}$ either contains $K_{s,s}$ or has minimum degree at most $d$. With these tools, we obtain for instance that odd-signable graphs and Burling graphs are degree-bounded. We also characterise exactly the oriented graphs $F$ such that the graphs admitting an orientation without any induced copy of $F$ are degree-bounded.

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 / 2 minor

Summary. The paper proves a Ramsey-type theorem: every 2-edge-coloured graph with sufficiently large minimum degree contains a monochromatic induced subgraph whose minimum degree is also large. It derives an analogous statement for orientations, guaranteeing either a large transitive tournament or an induced antidirected digraph with large minimum degree. These tools are applied to show that certain hereditary extensions preserve the degree-bounded property (for every s there exists d(s) such that every graph in the class contains K_{s,s} or has minimum degree at most d), yielding that odd-signable graphs and Burling graphs are degree-bounded, together with an exact characterisation of the oriented graphs F for which the class of graphs admitting an F-free orientation is degree-bounded.

Significance. The main combinatorial statement supplies a new, flexible tool for controlling minimum degree in monochromatic or oriented induced subgraphs. When the proofs are complete, the preservation results for degree-bounded classes constitute a genuine advance, directly implying the stated applications to odd-signable graphs, Burling graphs, and the forbidden-oriented-F characterisation. These consequences are concrete and falsifiable once the degree thresholds are made explicit.

minor comments (2)
  1. The abstract states the main Ramsey result but does not indicate the dependence of the minimum-degree threshold on the target minimum degree of the monochromatic subgraph; a brief remark on this dependence (even if only existential) would help readers assess the strength of the tool.
  2. In the definition of degree-bounded classes, the quantifiers are clear, yet the subsequent preservation theorems would benefit from an explicit statement of how the new d'(s) is obtained from the original d(s) and the Ramsey numbers appearing in the main theorem.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript, accurate summary of the main results, and recommendation for minor revision. We are pleased that the combinatorial tools and their applications to degree-boundedness are viewed positively.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper's central result is a new Ramsey-type theorem asserting that every 2-edge-coloured graph with large minimum degree contains a monochromatic induced subgraph that itself has large minimum degree. This statement is introduced and proved directly as a combinatorial fact rather than being obtained by fitting parameters to data or by reducing to a prior self-citation. The definition of a hereditary class being degree-bounded (for every s there exists d(s) such that every member either contains K_{s,s} or has minimum degree at most d) is stated explicitly in the abstract and functions as the input assumption for the subsequent preservation tools; it is not redefined in terms of the new theorem. The applications to odd-signable graphs, Burling graphs, and the exact characterisation of forbidden oriented subgraphs F are presented as direct consequences once the monochromatic-subgraph tool is available, without any load-bearing self-citation chain, uniqueness theorem imported from the authors' prior work, or ansatz smuggled via citation. The derivation therefore remains self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard definitions and axioms of graph theory; no free parameters, fitted constants, or newly invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard definitions of undirected graphs, edge-colorings, orientations, induced subgraphs, hereditary classes, and the degree-bounded property.
    The abstract invokes these conventional combinatorial notions to state the theorem and its consequences.

pith-pipeline@v0.9.0 · 5720 in / 1278 out tokens · 52865 ms · 2026-05-19T08:13:52.256582+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On the list version of a conjecture of Erd\H{o}s and Neumann-Lara

    math.CO 2026-03 unverdicted novelty 6.0

    Graphs with large list chromatic number admit orientations with arbitrarily large list dichromatic number.

Reference graph

Works this paper leans on

46 extracted references · 46 canonical work pages · cited by 1 Pith paper

  1. [1]

    Aboulker, J

    P. Aboulker, J. Bang-Jensen, N. Bousquet, P. Charbit, F. Havet, F. Maffray, and J. Zamora.χ-bounded families of oriented graphs.Journal of Graph Theory, 89(3):304–326, 2018

    work page 2018

  2. [2]

    Abrishami, M

    T. Abrishami, M. Chudnovsky, and K. Vušković. Induced subgraphs and tree decompositions I. Even- hole-free graphs of bounded degree.Journal of Combinatorial Theory, Series B, 157:144–175, 2022

    work page 2022

  3. [3]

    Addario-Berry, M

    L. Addario-Berry, M. Chudnovsky, F. Havet, B. Reed, and P. Seymour. Bisimplicial vertices in even- hole-free graphs. Journal of Combinatorial Theory, Series B, 98(6):1119–1164, 2008. 11

    work page 2008

  4. [4]

    Bonamy, N

    M. Bonamy, N. Bousquet, M. Pilipczuk, P. Rzążewski, S. Thomassé, and B. Walczak. Degeneracy of Pt-free and C⩾t-free graphs with no large complete bipartite subgraphs.Journal of Combinatorial Theory, Series B, 152:353–378, 2022

    work page 2022

  5. [5]

    J. A. Bondy and U. S. R. Murty.Graph Theory. Springer London, 2008

    work page 2008

  6. [6]

    Bourneuf, L

    R. Bourneuf, L. Cook, and J. Davies. On polynomial degree-boundedness.Advances in Combinatorics, 2024

    work page 2024

  7. [7]

    Briański, J

    M. Briański, J. Davies, and B. Walczak. Separating polynomialχ-boundedness from χ-boundedness. Combinatorica, 44(1):1–8, 2024

    work page 2024

  8. [8]

    J. P. Burling.On coloring problems of families of polytopes. PhD thesis, University of Colorado, Boulder, 1965

    work page 1965

  9. [9]

    Chalopin, L

    J. Chalopin, L. Esperet, Z. Li, and P. Ossona de Mendez. Restricted frame graphs and a conjecture of Scott. The Electronic Journal of Combinatorics, 23(P1.30), 2016

    work page 2016

  10. [10]

    Chudnovsky, A

    M. Chudnovsky, A. Scott, and P. Seymour. Induced subgraphs of graphs with large chromatic number. XI. Orientations.European Journal of Combinatorics, 76:53–61, 2019

    work page 2019

  11. [11]

    Chudnovsky and P

    M. Chudnovsky and P. Seymour. Even-hole-free graphs still have bisimplicial vertices. Journal of Combinatorial Theory, Series B, 161:331–381, 2023

    work page 2023

  12. [12]

    Conforti, G

    M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković. Even and odd holes in cap-free graphs. Journal of Graph Theory, 30(4):289–308, 1999

    work page 1999

  13. [13]

    Conforti, G

    M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković. Even-hole-free graphs part I: Decomposition theorem. Journal of Graph Theory, 39(1):6–49, 2002

    work page 2002

  14. [14]

    J. Davies. Box and segment intersection graphs with large girth and chromatic number.Advances in Combinatorics, 2021

    work page 2021

  15. [15]

    Diestel.Graph Theory

    R. Diestel.Graph Theory. Graduate Texts in Mathematics. Springer, New York, NY, 2nd edition, 2000

    work page 2000

  16. [16]

    R. Diestel. Graph Theory. Graduate texts in mathematics. Springer, Berlin, Germany, 5th edition, 2017

    work page 2017

  17. [17]

    X. Du, A. Girão, Z. Hunter, R. McCarty, and A. Scott. InducedC4-free subgraphs with large average degree. Journal of Combinatorial Theory, Series B, 173:305–328, 2025

    work page 2025

  18. [18]

    Du and R

    X. Du and R. McCarty. A survey of degree-boundedness.European Journal of Combinatorics, page 104092, 2024

    work page 2024

  19. [19]

    P. Erdős. Some remarks on the theory of graphs. Bulletin of the American Mathematical Society, 53(4):292 – 294, 1947

    work page 1947

  20. [20]

    P. Erdős. Graph theory and probability.Canadian Journal of Mathematics, 11:34–38, 1959

    work page 1959

  21. [21]

    Erdős and A

    P. Erdős and A. Hajnal. On chromatic number of infinite graphs. InTheory of Graphs (Proc. Colloq., Tihany, 1966), pages 83–98, 1968

    work page 1966

  22. [22]

    Erdős and L

    P. Erdős and L. Moser. On the representation of directed graphs as unions of orderings.Magyar Tud. Akad. Mat. Kutató Int. Közl., 9:125–132, 1964

    work page 1964

  23. [23]

    L. Esperet. Graph colorings, flows and perfect matchings. Habilitation à Diriger des Recherches, Université Grenoble Alpes, 2017

    work page 2017

  24. [24]

    Esperet, R

    L. Esperet, R. J. Kang, and S. Thomassé. Separation choosability and dense bipartite induced sub- graphs. Combinatorics, Probability and Computing, 28(5):720–732, 2019

    work page 2019

  25. [25]

    Aseparatortheoremforstringgraphsanditsapplications

    J.FoxandJ.Pach. Aseparatortheoremforstringgraphsanditsapplications. Combinatorics Probability and Computing, 19(3):371 – 390, 2010. 12

    work page 2010

  26. [26]

    Girão and Z

    A. Girão and Z. Hunter. Induced subdivisions in Ks,s-free graphs with polynomial average degree. International Mathematics Research Notices, 2025(4), 2025

    work page 2025

  27. [27]

    A. Gyárfás. On Ramsey covering-numbers.Infinite and Finite Sets, 2:801–816, 1975

    work page 1975

  28. [28]

    A. Gyárfás. Problem 115.Discrete Mathematics, 79(1):109–110, 1990

    work page 1990

  29. [29]

    Kővári, V

    T. Kővári, V. T. Sós, and P. Turán. On a problem of K. Zarankiewicz.Colloquium Mathematicum, 3(1):50–57, 1954

    work page 1954

  30. [30]

    H. A. Kierstead and S. G. Penrice. Radius two trees specify χ-bounded classes. Journal of Graph Theory, 18(2):119–129, 1994

    work page 1994

  31. [31]

    H. A. Kierstead and W. T. Trotter. Colorful induced subgraphs.Discrete mathematics, 101(1-3):165– 169, 1992

    work page 1992

  32. [32]

    Krawczyk, A

    T. Krawczyk, A. Pawlik, and B. Walczak. Coloring triangle-free rectangle overlap graphs with O(log logn) colors. Discrete & Computational Geometry, 53(1):199–220, 2014

    work page 2014

  33. [33]

    M. Kwan, S. Letzter, B. Sudakov, and T. Tran. Dense induced bipartite subgraphs in triangle-free graphs. Combinatorica, 40(2):283–305, 2020

    work page 2020

  34. [34]

    Inducedsubdivisionsin Ks,s-freegraphsoflargeaveragedegree

    D.KühnandD.Osthus. Inducedsubdivisionsin Ks,s-freegraphsoflargeaveragedegree. Combinatorica, 24(2):287–304, 2004

    work page 2004

  35. [35]

    Homomorphieeigenschaftenundmittlerekantendichtevongraphen

    W.Mader. Homomorphieeigenschaftenundmittlerekantendichtevongraphen. Mathematische Annalen, 174(4):265–268, 1967

    work page 1967

  36. [36]

    R. McCarty. Dense induced subgraphs of dense bipartite graphs.SIAM Journal on Discrete Mathe- matics, 35(2):661–667, 2021

    work page 2021

  37. [37]

    Pawlik, J

    A. Pawlik, J. Kozik, T. Krawczyk, M. Lasoń, P. Micek, W. T. Trotter, and B. Walczak. Triangle- free geometric intersection graphs with large chromatic number.Discrete & Computational Geometry, 50(3):714–726, 2013

    work page 2013

  38. [38]

    Pawlik, J

    A. Pawlik, J. Kozik, T. Krawczyk, M. Lasoń, P. Micek, W. T. Trotter, and B. Walczak. Triangle-free intersection graphs of line segments with large chromatic number.Journal of Combinatorial Theory, Series B, 105:6–10, 2014

    work page 2014

  39. [39]

    Pournajafi

    P. Pournajafi. Chi-boundedness, Geometric Graph Theory, and Burling Graphs. PhD thesis, École normale supérieure de Lyon, 2023

    work page 2023

  40. [40]

    Pournajafi and N

    P. Pournajafi and N. Trotignon. Burling graphs revisited, part II: Structure. European Journal of Combinatorics, 116:103849, 2024

    work page 2024

  41. [41]

    F. P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society, s2- 30(1):264–286, 1930

    work page 1930

  42. [42]

    Scott, P

    A. Scott, P. Seymour, and S. Spirkl. Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree.Journal of Graph Theory, 102(3):458–471, Sept. 2022

    work page 2022

  43. [43]

    Inducedtreesingraphsoflargechromaticnumber

    A.D.Scott. Inducedtreesingraphsoflargechromaticnumber. Journal of Graph Theory, 24(4):297–311, 1997

    work page 1997

  44. [44]

    D. P. Sumner. Subtrees of a graph and chromatic number.The Theory and Applications of Graphs,(G. Chartrand, ed.), John Wiley & Sons, New York, 557:576, 1981

    work page 1981

  45. [45]

    Vušković

    K. Vušković. Even-hole-free graphs: A survey.Applicable Analysis and Discrete Mathematics, 4(2):219– 240, 2010

    work page 2010

  46. [46]

    A. A. Zykov. On some properties of linear complexes.Matematicheskii Sbornik, 24(66):163–188, 1949. 13

    work page 1949