betaFeedback

WorksMathematics

Independence number and odd dominating models

Abstract

A dominating KtK_t-model, introduced by Illingworth and Wood [J. Graph Theory, 2025], is a sequence (T1,…,Tt)(T_1,\dots,T_t) of pairwise vertex-disjoint subtrees of GG such that every vertex of TjT_j has a neighbour in TiT_i for 1≤i<j≤t1\leq i<j\leq t. Let hadd(G)\text{had}_{\text{d}}(G) denote the maximum order of such a model. We prove two dominating-model analogues of improvements to the classical Duchet-Meyniel bound [Ann. Discrete Math., 1982]. The first extends a result of Kawarabayashi, Plummer, and Toft [J. Combin. Theory Ser. B, 2005]. Every nn-vertex graph GG with α(G)≥2α(G)\geq2 satisfies hadd(G)≥(n+ω(G))/(2α(G)−1)\text{had}_{\text{d}}(G)\geq(n+ω(G))/(2α(G)-1). Second, we prove a constant-factor improvement of the Duchet-Meyniel bound for dominating models: every graph GG satisfies hadd(G)>0.51075n/α(G)\text{had}_{\text{d}}(G)>0.51075n/α(G). This qualitatively extends the results of Fox [SIAM J. Discrete Math., 2010] and Balogh and Kostochka [Discrete Math., 2011]. An odd dominating KtK_t-model is a dominating KtK_t-model with an assignment of one of two colours to each vertex of V(T1)∪⋯∪V(Tt)V(T_1)\cup\dots\cup V(T_t), such that every edge of each TiT_i is bichromatic and, for 1≤i<j≤t1\leq i<j\leq t, some edge between TiT_i and TjT_j is monochromatic. Let hadod(G)\text{had}_{\text{od}}(G) denote the maximum order of such a model. Our constant-factor improvement of the Duchet-Meyniel bound relies on our next result: every claw-free graph GG satisfies hadod(G)≥2χ(G)/3\text{had}_{\text{od}}(G)\geq 2χ(G)/3, generalising a result of Chudnovsky and Fradkin [J. Graph Theory, 2010]. The factor 2/3 is best possible [arXiv:2512.20392]. For t≥2t\geq2, we prove that every nn-vertex graph with no odd dominating KtK_t-model has independence number at least (n+t−1)/(2t−2)(n+t-1)/(2t-2). For the stronger notion in which every vertex of TjT_j has a neighbour of the same colour in TiT_i, we prove the analogous results with (n+t−1)/(2t−2)(n+t-1)/(2t-2) replaced by (n+t−1)/(3t−3)(n+t-1)/(3t-3).

Introduction

Hadwiger’s Conjecture [27] has long been considered one of the deepest problems in graph theory4, since it generalises the well-known four-colour theorem [1, 2, 53] and suggests a deep relationship between graph minors and graph colouring; see [8, 15, 33, 44, 56, 61] for surveys.

Conjecture 1 (Hadwiger’s Conjecture). For every graph GG, had⁡(G)≥χ(G)\operatorname{had}(G) \ge\chi(G). Equivalently, if GG is KtK_t-minor-free, then GG is (t−1)(t-1)-colourable.

Hadwiger’s Conjecture and several of its strengthenings have recently been disproved [28, 41, 48], while its linear relaxation has been proved [47, 49, 65] (see § 1.1). Here we study bounds on the independence number for dominating, odd dominating, and strongly odd dominating models, which we define later. Every nn-vertex graph GG with n≥1n \ge1 satisfies χ(G)≥n/α(G)\chi(G) \ge n/\alpha(G). So Hadwiger’s Conjecture would imply:

Conjecture 2. For every nn-vertex graph GG with n≥1n \ge1, had⁡(G)≥n/α(G)\operatorname{had}(G) \ge n/\alpha(G).

Conjecture 2 has also been disproved [48]. Nevertheless, Duchet and Meyniel Duchet and Meyniel [19] proved using an elegant argument that every nn-vertex graph GG with n≥1n \ge1 satisfies had⁡(G)≥n/(2α(G)−1)\operatorname{had}(G) \ge n/(2\alpha(G)-1), which is within a factor of 2 of the bound predicted by Conjecture 2. We shall refer to this as the Duchet–Meyniel bound. For graphs with independence number 2, no constant-factor improvement of the resulting bound had⁡(G)≥n/3\operatorname{had}(G) \ge n/3 is known. More specifically, it is open if there is an absolute constant ε>0\varepsilon> 0 such that every nn-vertex graph GG with α(G)=2\alpha(G)=2 satisfies had⁡(G)≥(1/3+ε)n\operatorname{had}(G) \ge(1/3+\varepsilon)n. This question, due to Seymour Seymour [56], has been the focus of much research [3, 14, 20, 51, 56]. The recent counterexamples of OpenAI [48] have independence number 2, and in this class the constant 1/31/3 cannot be replaced by any constant greater than 26/7526/75.

Several improvements to the Duchet–Meyniel bound are known. Kawarabayashi, Plummer, and Toft Kawarabayashi, Plummer, and Toft [34] proved that every nn-vertex graph GG with α(G)≥2\alpha(G) \ge2 satisfies had⁡(G)≥(n+ω(G))/(2α(G)−1)\operatorname{had}(G) \ge(n+\omega(G))/(2\alpha(G)-1). This bound was improved by Pedersen and Toft Pedersen and Toft [50] to had⁡(G)≥(n+ω(G)+2α(G)−4)/(2α(G)−1)\operatorname{had}(G) \ge(n+\omega(G)+2\alpha(G)-4)/(2\alpha(G)-1) for every nn-vertex graph GG with n≥1n \ge1 that is neither complete nor edgeless. For graphs with α(G)=2\alpha(G)=2, Chudnovsky and Seymour Chudnovsky and Seymour [14] established the stronger bound had⁡(G)≥n/2\operatorname{had}(G) \ge n/2, provided that ω(G)≥n/4\omega(G) \ge n/4 when nn is even, or ω(G)≥(n+3)/4\omega(G) \ge(n+3)/4 when nn is odd.

For α(G)≥3\alpha(G) \ge3, the bound had⁡(G)≥n/(2α(G)−1.5)\operatorname{had}(G) \ge n/(2\alpha(G)-1.5) of Kawarabayashi et al. [34] was improved to had⁡(G)≥n/(2α(G)−2)\operatorname{had}(G) \ge n/(2\alpha(G)-2) by Kawarabayashi and Song Kawarabayashi and Song [35]. Wood Wood [64] obtained the related bound had⁡(G)≥(n+5α(G)−5)/(2α(G)−1)\operatorname{had}(G) \ge(n+5\alpha(G)-5)/(2\alpha(G)-1). Balogh, Lenz, and Wu Balogh, Lenz, and Wu [4] then proved that every nn-vertex graph GG with n≥1n \ge1 satisfies

had⁡(G)≥n2α(G)−⌈log⁡τ(τα(G)/2)⌉,τ:=222−1,\operatorname{had}(G) \ge\frac{n}{2\alpha(G)-\left\lceil\log_{\tau}(\tau\alpha(G)/2)\right\rceil}, \qquad\tau:= \frac{2\sqrt{2}}{\sqrt{2}-1},

which improves the bound of Kawarabayashi and Song [35] when α(G)≥14\alpha(G) \ge14.

Fox Fox [20] gave the first improvement of the Duchet–Meyniel bound by an absolute constant factor: had⁡(G)>0.504 n/α(G)\operatorname{had}(G) > 0.504\,n/\alpha(G) for every nn-vertex graph GG with n≥1n \ge1. This is asymptotically stronger than the bound of Balogh et al. [4] when α(G)\alpha(G) is large. Balogh and Kostochka [3] then improved Fox’s constant, proving that every nn-vertex graph GG with n≥1n \ge1 satisfies had⁡(G)≥n/((2−c)α(G))\operatorname{had}(G) \ge n/((2-c)\alpha(G)) for a constant c>1/19.2c > 1/19.2.

We consider the following four strengthenings of KtK_t-models. In (a), (c) and (d), a colouring is any function c:⋃iV(Ti)→{red,blue}c : \bigcup_i V(T_i) \to\{\text{red}, \text{blue}\} (not necessarily a proper colouring of GG). An edge vwvw is bichromatic if c(v)≠c(w)c(v) \ne c(w), and monochromatic if c(v)=c(w)c(v) = c(w).

  • (a) An odd KtK_t-model (Gerards and Seymour, see [30]) is a KtK_t-model (T1,…,Tt)(T_1,\ldots,T_t) together with a colouring cc such that every edge of every TiT_i is bichromatic and, for $1 \le i < j \le t$, some edge of GG between TiT_i and TjT_j is monochromatic.

  • (b) A dominating KtK_t-model (Illingworth and Wood [29]) is a sequence (T1,…,Tt)(T_1,\ldots,T_t) of pairwise vertex-disjoint subtrees of GG such that for $1 \le i < j \le t$ every vertex of TjT_j has a neighbour in TiT_i.

  • (c) An odd dominating KtK_t-model is a dominating KtK_t-model (T1,…,Tt)(T_1,\ldots,T_t) together with a colouring cc such that every edge of every TiT_i is bichromatic and, for $1 \le i < j \le t$, some edge of GG between TiT_i and TjT_j is monochromatic. That is, ((T1,…,Tt),c)((T_1,\ldots,T_t),c) is an odd KtK_t-model and (T1,…,Tt)(T_1,\ldots,T_t) is a dominating KtK_t-model.

  • (d) A strongly odd dominating KtK_t-model is a dominating KtK_t-model (T1,…,Tt)(T_1,\ldots,T_t) together with a colouring cc such that every edge of every TiT_i is bichromatic and, for $1 \le i < j \le t$, every vertex vv of TjT_j has a neighbour uu in TiT_i with c(u)=c(v)c(u) = c(v). That is, the domination is witnessed by monochromatic edges.

For each type of model, we define a Hadwiger-type parameter. Let had⁡o(G)\operatorname{had}_{\mathrm{o}}(G), had⁡d(G)\operatorname{had}_{\mathrm{d}}(G), had⁡od(G)\operatorname{had}_{\mathrm{od}}(G) and had⁡sod(G)\operatorname{had}_{\mathrm{sod}}(G) be the maximum integer tt such that GG has an odd, dominating, odd dominating and strongly odd dominating KtK_t-model, respectively. Every strongly odd dominating KtK_t-model is an odd dominating KtK_t-model, and every odd dominating KtK_t-model is an odd KtK_t-model and a dominating KtK_t-model. Thus every graph GG satisfies

ω(G)≤had⁡sod(G)≤had⁡od(G)≤had⁡o(G)≤had⁡(G),\omega(G) \le\operatorname{had}_{\mathrm{sod}}(G) \le\operatorname{had}_{\mathrm{od}}(G) \le\operatorname{had}_{\mathrm{o}}(G) \le\operatorname{had}(G),

and

References

  1. [1]Kenneth Appel and Wolfgang Haken. Every planar map is four colorable. Part I: discharging. Illinois J. Math., 21(3):429–490, 1977.DOI
  2. [2]Kenneth Appel, Wolfgang Haken, and John Koch. Every planar map is four colorable. Part II: reducibility. Illinois J. Math., 21(3):491–567, 1977.DOI
  3. [3]József Balogh and Alexandr V. Kostochka. Large minors in graphs with given independence number. Discrete Math., 311(20):2203–2215, 2011.DOI
  4. [4]József Balogh, John Lenz, and Hehui Wu. Complete minors, independent sets, and chordal graphs. Discuss. Math. Graph Theory, 31(4):639–674, 2011.arxiv.org/abs/0907.2421
  5. [5]Jonah Blasiak. A special case of Hadwiger’s conjecture. J. Combin. Theory Ser. B, 97(6):1056–1073, 2007.DOI
  6. [6]Béla Bollobás, Paul A. Catlin, and Paul Erdős. Hadwiger’s conjecture is true for almost every graph. Eur. J. Combin., 1(3):195–199, 1980.
  7. [7]Christian Bosse. A note on Hadwiger’s conjecture for W₅-free graphs with independence number two. Discrete Math., 342(12):111595, 2019.DOI
  8. [8]Kathie Cameron and Kristina Vušković. Hadwiger’s conjecture for some hereditary classes of graphs: a survey. Bull. EATCS, 131:20–37, 2020.
  9. [9]Maria Chudnovsky and Alexandra Ovetsky Fradkin. An approximate version of Hadwiger’s conjecture for claw-free graphs. J. Graph Theory, 63(4):259–278, 2010.
  10. [10]Maria Chudnovsky, Aurélie Lagoutte, Paul Seymour, and Sophie Spirkl. Colouring perfect graphs with bounded clique number. J. Combin. Theory Ser. B, 122:757–775, 2017.DOI
  11. [11]Maria Chudnovsky and Alexandra Ovetsky Fradkin. Hadwiger’s conjecture for quasi-line graphs. J. Graph Theory, 59(1):17–33, 2008.DOI
  12. [12]Maria Chudnovsky and Paul Seymour. The structure of claw-free graphs. In Bridget S. Webb, ed., Surveys in Combinatorics 2005, vol. 327 of London Mathematical Society Lecture Note Series, pp. 153–172. Cambridge University Press, 2005.DOI
  13. [13]Maria Chudnovsky and Paul Seymour. Claw-free graphs. VI: colouring. J. Combin. Theory Ser. B, 100(6):560–572, 2010.DOI
  14. [14]Maria Chudnovsky and Paul Seymour. Packing seagulls. Combinatorica, 32(3):251–282, 2012.DOI
  15. [15]Jofre Costa, Eric Luu, David R. Wood, and Jung Hoi Yip. Verifying Hadwiger’s conjecture for examples of graphs with α(G) = 2. 2025, arXiv:2512.17114.arxiv.org/abs/2512.17114
  16. [16]Michelle Delcourt and Luke Postle. Reducing linear Hadwiger’s conjecture to coloring small graphs. J. Amer. Math. Soc., 38(2):481–507, 2025.arxiv.org/abs/2108.01633
  17. [17]Reinhard Diestel. Graph theory, vol. 173 of Graduate Texts in Mathematics. Springer, 3rd edn., 2005.
  18. [18]Gabriel A. Dirac. A property of 4-chromatic graphs and some remarks on critical graphs. J. London Math. Soc., 27:85–92, 1952.DOI
  19. [19]Pierre Duchet and Henri Meyniel. On Hadwiger’s number and the stability number. Ann. Discrete Math., 13:71–73, 1982.DOI
  20. [20]Jacob Fox. Complete minors and independence number. SIAM J. Discrete Math., 24(4):1313–1321, 2010.DOI
  21. [21]Shinya Fujita and Boram Park. The optimal proper connection number of a graph with given independence number. Discrete Optim., 41:100660, 2021.arxiv.org/abs/2003.08779
  22. [22]Tibor Gallai. Kritische Graphen II. Publ. Math. Inst. Hungar. Acad. Sci., 8:373–395, 1963.
  23. [23]Jim Geelen, Bert Gerards, Bruce A. Reed, Paul D. Seymour, and Adrian Vetta. On the odd-minor variant of Hadwiger’s conjecture. J. Comb. Theory, Ser. B, 99(1):20–29, 2009.
  24. [24]António Girão, Freddie Illingworth, Bojan Mohar, Sergey Norin, Raphael Steiner, Youri Tamitegama, Jane Tan, David R. Wood, and Jung Hon Yip. The dominating 4-colour theorem. Int. Math. Res. Not., 2026(20):rnag219, 2026.
  25. [25]António Girão, Sergey Norin, Youri Tamitegama, and Jane Tan. Two relaxations of the dominating Hadwiger’s conjecture. 2026, arXiv:2608.12126.arxiv.org/abs/2608.12126
  26. [26]Bertrand Guenin. Odd-K₅-free graphs are 4-colourable. In Oberwolfach Report No. 3/2005, pp. 176–178. 2005.
  27. [27]Hugo Hadwiger. Über eine Klassifikation der Streckenkomplexe. Viertelj schr. Naturforsch. Ges. Zürich, 88:133–142, 1943.
  28. [28]Freddie Illingworth and Raphael Steiner. Disproof of the dominating Hadwiger conjecture. 2026, arXiv:2609.35361.arxiv.org/abs/2609.35361
  29. [29]Freddie Illingworth and David R. Wood. Dominating Kₜ-models. J. Graph Theory, 110(4):448–456, 2025. arXiv:2405.14299.
  30. [30]Tommy R. Jensen and Bjarne Toft. Graph coloring problems. John Wiley, 1995.DOI
  31. [32]Ken-ichi Kawarabayashi. Note on coloring graphs without odd-Kₖ-minors. J. Combin. Theory Ser. B, 99(4):728–731, 2009.DOI
  32. [33]Ken-ichi Kawarabayashi. Hadwiger’s conjecture. In Topics in chromatic graph theory, vol. 156 of Encyclopedia Math. Appl., pp. 73–93. Cambridge Univ. Press, 2015.DOI
  33. [34]Ken-ichi Kawarabayashi, Michael D. Plummer, and Bjarne Toft. Improvements of the theorem of Duchet and Meyniel on Hadwiger’s conjecture. J. Combin. Theory Ser. B, 95(1):152–167, 2005.DOI
  34. [35]Ken-ichi Kawarabayashi and Zi-Xia Song. Independence number and clique minors. J. Graph Theory, 56(3):219–226, 2007.DOI
  35. [36]Ken-ichi Kawarabayashi and Zi-Xia Song. Some remarks on the odd Hadwiger’s conjecture. Combinatorica, 27:429–438, 2007.DOI
  36. [37]Jeong Han Kim. The Ramsey number R(3, t) has order of magnitude t² / log t. Random Struct. Algorithms, 7(3):173–207, 1995.DOI
  37. [38]Andrew D. King and Bruce A. Reed. Claw-free graphs, skeletal graphs, and a stronger conjecture on ω, Δ, and χ. J. Graph Theory, 78(3):157–194, 2015.
  38. [39]Alexandr V. Kostochka. The minimum Hadwiger number for graphs with a given mean degree of vertices. Metody Diskret. Analiz., 38:37–58, 1982.
  39. [40]Alexandr V. Kostochka. Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica, 4(4):307–316, 1984.DOI
  40. [41]Marcus Kühn, Lisa Sauermann, Raphael Steiner, and Yuval Wigderson. Disproof of the odd Hadwiger conjecture. 2025, arXiv:2512.20392.arxiv.org/abs/2512.20392
  41. [42]Xin Heng Lin. Coloring small Kₜ-minor-free graphs. 2026, arXiv:2609.08713.arxiv.org/abs/2609.08713
  42. [43]Chun-Hung Liu and Jason Luo. Beyond halfway to Hadwiger’s conjecture. 2026, arXiv:2609.06867.arxiv.org/abs/2609.06867
  43. [44]Sergey Norin. Recent progress towards Hadwiger’s conjecture. In ICM—International Congress of Mathematicians. Vol. 6. Sections 12–14, pp. 4606–4620. EMS Press, 2023.DOI
  44. [45]Sergey Norin, Luke Postle, and Zi-Xia Song. Breaking the degeneracy barrier for coloring graphs with no Kₜ minor. Adv. Math., 422:109020, 2023.
  45. [46]Sergey Norin and Paul Seymour. Dense minors of graphs with independence number two. J. Combin. Theory Ser. B, 176:101–110, 2026.arxiv.org/abs/2206.00186
  46. [47]Sergey Norin and Raphael Steiner. A proof of the linear Hadwiger conjecture. 2026, arXiv:2610.05291.arxiv.org/abs/2610.05291
  47. [48]OpenAI. A counterexample to Hadwiger’s conjecture. 2026.
  48. [49]OpenAI. A linear list-coloring bound in terms of the Hadwiger number. 2026.
  49. [50]Anders Sune Pedersen and Bjarne Toft. A basic elementary extension of the Duchet-Meyniel theorem. Discrete Math., 310(3):480–488, 2010.arxiv.org/abs/0810.0846
  50. [51]Michael D. Plummer, Michael Stiebitz, and Bjarne Toft. On a special case of Hadwiger’s conjecture. Discuss. Math. Graph Theory, 23(2):333–363, 2003.DOI
  51. [52]Bruce Reed. ω, Δ, and χ. J. Graph Theory, 27(4):177–212, 1998.
  52. [53]Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas. The four-colour theorem. J. Combin. Theory Ser. B, 70(1):2–44, 1997.DOI
  53. [54]Neil Robertson, Paul Seymour, and Robin Thomas. Hadwiger’s conjecture for K₆-free graphs. Combinatorica, 13(3):279–361, 1993.
  54. [55]Michael Scully and Zi-Xia Song. Dominating Hadwiger’s conjecture for graphs G with α(G) = 2. 2025, arXiv:2510.12564.arxiv.org/abs/2510.12564
  55. [56]Paul Seymour. Hadwiger’s conjecture. In John Forbes Nash, Jr. and Michael Th. Rassias, eds., Open problems in mathematics, pp. 417–437. Springer, 2016.DOI
  56. [57]Zi-Xia Song and Thomas Tibbets. Dominating Hadwiger’s conjecture holds for all 2K₂-free graphs. 2025, arXiv:2510.12567.arxiv.org/abs/2510.12567
  57. [58]Matěj Stehlík. Critical graphs with connected complements. J. Combin. Theory Ser. B, 89(2):189–194, 2003.DOI
  58. [59]Raphael Steiner. Asymptotic equivalence of Hadwiger’s conjecture and its odd minor-variant. J. Combin. Theory Ser. B, 155:45–51, 2022.arxiv.org/abs/2109.02302
  59. [60]Andrew Thomason. An extremal function for contractions of graphs. Math. Proc. Camb. Philos. Soc., 95(2):261–265, 1984.DOI
  60. [61]Bjarne Toft. A survey of Hadwiger’s conjecture. Congr. Numer., 115:249–283, 1996.
  61. [62]Klaus Wagner. Über eine Eigenschaft der ebenen Komplexe. Math. Ann., 114:570–590, 1937.DOI
  62. [63]Klaus Wagner. Beweis einer Abschwächung der Hadwiger-Vermutung. Math. Ann., 153:139–141, 1964.DOI
  63. [64]David R. Wood. Independent sets in graphs with an excluded clique minor. Discrete Math. Theor. Comput. Sci., 9(1):171–175, 2007.arxiv.org/abs/math/0601172
  64. [65]David R. Wood. Tweaking the constant in the linear Hadwiger theorem. 2026, arXiv:2610.10831.arxiv.org/abs/2610.10831

Paper details

vlnc:W_gdppe5gf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents