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 G G G , had ( G ) ≥ χ ( G ) \operatorname{had}(G) \ge\chi(G) had ( G ) ≥ χ ( G ) . Equivalently, if G G G is K t K_t K t -minor-free, then G G G is ( t − 1 ) (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 n n n -vertex graph G G G with n ≥ 1 n \ge1 n ≥ 1 satisfies χ ( G ) ≥ n / α ( G ) \chi(G) \ge n/\alpha(G) χ ( G ) ≥ n / α ( G ) . So Hadwiger’s Conjecture would imply:
Conjecture 2. For every n n n -vertex graph G G G with n ≥ 1 n \ge1 n ≥ 1 , had ( G ) ≥ n / α ( G ) \operatorname{had}(G) \ge n/\alpha(G) had ( G ) ≥ n / α ( G ) .
Conjecture 2 has also been disproved [48 ] . Nevertheless, Duchet and Meyniel Duchet and Meyniel [19 ] proved using an elegant argument that every n n n -vertex graph G G G with n ≥ 1 n \ge1 n ≥ 1 satisfies had ( G ) ≥ n / ( 2 α ( G ) − 1 ) \operatorname{had}(G) \ge n/(2\alpha(G)-1) had ( G ) ≥ n / ( 2 α ( 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 had ( G ) ≥ n /3 is known. More specifically, it is open if there is an absolute constant ε > 0 \varepsilon> 0 ε > 0 such that every n n n -vertex graph G G G with α ( G ) = 2 \alpha(G)=2 α ( G ) = 2 satisfies had ( G ) ≥ ( 1 / 3 + ε ) n \operatorname{had}(G) \ge(1/3+\varepsilon)n had ( G ) ≥ ( 1/3 + ε ) 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 / 3 1/3 1/3 cannot be replaced by any constant greater than 26 / 75 26/75 26/75 .
Several improvements to the Duchet–Meyniel bound are known. Kawarabayashi, Plummer, and Toft Kawarabayashi, Plummer, and Toft [34 ] proved that every n n n -vertex graph G G G with α ( G ) ≥ 2 \alpha(G) \ge2 α ( G ) ≥ 2 satisfies had ( G ) ≥ ( n + ω ( G ) ) / ( 2 α ( G ) − 1 ) \operatorname{had}(G) \ge(n+\omega(G))/(2\alpha(G)-1) had ( G ) ≥ ( n + ω ( G )) / ( 2 α ( 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) had ( G ) ≥ ( n + ω ( G ) + 2 α ( G ) − 4 ) / ( 2 α ( G ) − 1 ) for every n n n -vertex graph G G G with n ≥ 1 n \ge1 n ≥ 1 that is neither complete nor edgeless. For graphs with α ( G ) = 2 \alpha(G)=2 α ( G ) = 2 , Chudnovsky and Seymour Chudnovsky and Seymour [14 ] established the stronger bound had ( G ) ≥ n / 2 \operatorname{had}(G) \ge n/2 had ( G ) ≥ n /2 , provided that ω ( G ) ≥ n / 4 \omega(G) \ge n/4 ω ( G ) ≥ n /4 when n n n is even, or ω ( G ) ≥ ( n + 3 ) / 4 \omega(G) \ge(n+3)/4 ω ( G ) ≥ ( n + 3 ) /4 when n n n is odd.
For α ( G ) ≥ 3 \alpha(G) \ge3 α ( G ) ≥ 3 , the bound had ( G ) ≥ n / ( 2 α ( G ) − 1.5 ) \operatorname{had}(G) \ge n/(2\alpha(G)-1.5) had ( G ) ≥ n / ( 2 α ( 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) had ( G ) ≥ n / ( 2 α ( 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) had ( G ) ≥ ( n + 5 α ( G ) − 5 ) / ( 2 α ( G ) − 1 ) . Balogh, Lenz, and Wu Balogh, Lenz, and Wu [4 ] then proved that every n n n -vertex graph G G G with n ≥ 1 n \ge1 n ≥ 1 satisfies
had ( G ) ≥ n 2 α ( G ) − ⌈ log τ ( τ α ( G ) / 2 ) ⌉ , τ : = 2 2 2 − 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}, had ( G ) ≥ 2 α ( G ) − ⌈ log τ ( τ α ( G ) /2 ) ⌉ n , τ := 2 − 1 2 2 ,
which improves the bound of Kawarabayashi and Song [35 ] when α ( G ) ≥ 14 \alpha(G) \ge14 α ( G ) ≥ 14 .
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) had ( G ) > 0.504 n / α ( G ) for every n n n -vertex graph G G G with n ≥ 1 n \ge1 n ≥ 1 . This is asymptotically stronger than the bound of Balogh et al. [4 ] when α ( G ) \alpha(G) α ( G ) is large. Balogh and Kostochka [3 ] then improved Fox’s constant, proving that every n n n -vertex graph G G G with n ≥ 1 n \ge1 n ≥ 1 satisfies had ( G ) ≥ n / ( ( 2 − c ) α ( G ) ) \operatorname{had}(G) \ge n/((2-c)\alpha(G)) had ( G ) ≥ n / (( 2 − c ) α ( G )) for a constant c > 1 / 19.2 c > 1/19.2 c > 1/19.2 .
We consider the following four strengthenings of K t K_t K t -models. In (a), (c) and (d), a colouring is any function c : ⋃ i V ( T i ) → { red , blue } c : \bigcup_i V(T_i) \to\{\text{red}, \text{blue}\} c : ⋃ i V ( T i ) → { red , blue } (not necessarily a proper colouring of G G G ). An edge v w vw v w is bichromatic if c ( v ) ≠ c ( w ) c(v) \ne c(w) c ( v ) = c ( w ) , and monochromatic if c ( v ) = c ( w ) c(v) = c(w) c ( v ) = c ( w ) .
(a) An odd K t K_t K t -model (Gerards and Seymour, see [30 ] ) is a K t K_t K t -model ( T 1 , … , T t ) (T_1,\ldots,T_t) ( T 1 , … , T t ) together with a colouring c c c such that every edge of every T i T_i T i is bichromatic and, for $1 \le i < j \le t$, some edge of G G G between T i T_i T i and T j T_j T j is monochromatic.
(b) A dominating K t K_t K t -model (Illingworth and Wood [29 ] ) is a sequence ( T 1 , … , T t ) (T_1,\ldots,T_t) ( T 1 , … , T t ) of pairwise vertex-disjoint subtrees of G G G such that for $1 \le i < j \le t$ every vertex of T j T_j T j has a neighbour in T i T_i T i .
(c) An odd dominating K t K_t K t -model is a dominating K t K_t K t -model ( T 1 , … , T t ) (T_1,\ldots,T_t) ( T 1 , … , T t ) together with a colouring c c c such that every edge of every T i T_i T i is bichromatic and, for $1 \le i < j \le t$, some edge of G G G between T i T_i T i and T j T_j T j is monochromatic. That is, ( ( T 1 , … , T t ) , c ) ((T_1,\ldots,T_t),c) (( T 1 , … , T t ) , c ) is an odd K t K_t K t -model and ( T 1 , … , T t ) (T_1,\ldots,T_t) ( T 1 , … , T t ) is a dominating K t K_t K t -model.
(d) A strongly odd dominating K t K_t K t -model is a dominating K t K_t K t -model ( T 1 , … , T t ) (T_1,\ldots,T_t) ( T 1 , … , T t ) together with a colouring c c c such that every edge of every T i T_i T i is bichromatic and, for $1 \le i < j \le t$, every vertex v v v of T j T_j T j has a neighbour u u u in T i T_i T i with c ( u ) = c ( v ) 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 o ( G ) , had d ( G ) \operatorname{had}_{\mathrm{d}}(G) had d ( G ) , had o d ( G ) \operatorname{had}_{\mathrm{od}}(G) had od ( G ) and had s o d ( G ) \operatorname{had}_{\mathrm{sod}}(G) had sod ( G ) be the maximum integer t t t such that G G G has an odd, dominating, odd dominating and strongly odd dominating K t K_t K t -model, respectively. Every strongly odd dominating K t K_t K t -model is an odd dominating K t K_t K t -model, and every odd dominating K t K_t K t -model is an odd K t K_t K t -model and a dominating K t K_t K t -model. Thus every graph G G G satisfies
ω ( G ) ≤ had s o d ( G ) ≤ had o d ( 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), ω ( G ) ≤ had sod ( G ) ≤ had od ( G ) ≤ had o ( G ) ≤ had ( G ) ,
and
ω ( G ) ≤ had s o d ( G ) ≤ had o d ( G ) ≤ had d ( G ) ≤ had ( G ) . \omega(G) \le\operatorname{had}_{\mathrm{sod}}(G) \le\operatorname{had}_{\mathrm{od}}(G) \le\operatorname{had}_{\mathrm{d}}(G) \le\operatorname{had}(G). ω ( G ) ≤ had sod ( G ) ≤ had od ( G ) ≤ had d ( G ) ≤ had ( G ) .
In some ways, dominating models resemble ordinary complete graph models. For t ≤ 4 t \le4 t ≤ 4 , Illingworth and Wood [29 ] proved that every graph with no dominating K t K_t K t -model is ( t − 1 ) (t-1) ( t − 1 ) -colourable. The case t = 5 t=5 t = 5 was proved by Girão, Illingworth, Mohar, Norin, Steiner, Tamitegama, Tan, Wood, and Yip [24 ] : every graph with no dominating K 5 K_5 K 5 -model is 4-colourable, thus extending the four-colour theorem. Moreover, Illingworth and Wood [29 ] proved that had d ( G ) ≥ χ ( G ) \operatorname{had}_{\mathrm{d}}(G) \ge\chi(G) had d ( G ) ≥ χ ( G ) for almost every graph5 , mirroring the corresponding result of Bollobás, Catlin, and Erdős [6 ] for ordinary models. Graphs with no dominating K t K_t K t -model are also reasonably sparse: Girão, Norin, Tamitegama, and Tan [25 ] proved that graphs with no dominating K t K_t K t -model are O ( t ( log t ) 2 ) O(t(\log t)^2) O ( t ( log t ) 2 ) -degenerate, while classical results of Kostochka [39 , 40 ] and Thomason [60 ] show that K t K_t K t -minor-free graphs are O ( t log t ) O(t\sqrt{\log t}) O ( t log t ) -degenerate.
Our first goal is to extend two refinements of the Duchet–Meyniel bound to dominating models, adding to the growing collection of parallel results between ordinary and dominating models. As mentioned above, Kawarabayashi et al. [34 Theorem 1.2] proved that every graph G G G with α ( G ) ≥ 2 \alpha(G) \ge2 α ( G ) ≥ 2 satisfies had ( G ) ≥ ( ∣ V ( G ) ∣ + ω ( G ) ) / ( 2 α ( G ) − 1 ) \operatorname{had}(G) \ge(|V(G)|+\omega(G))/(2\alpha(G)-1) had ( G ) ≥ ( ∣ V ( G ) ∣ + ω ( G )) / ( 2 α ( G ) − 1 ) , strengthening the Duchet–Meyniel bound by incorporating the clique number. In the dominating setting, Illingworth and Wood [29 ] proved that had d ( G ) ≥ ∣ V ( G ) ∣ / ( 2 α ( G ) − 1 ) \operatorname{had}_{\mathrm{d}}(G) \ge|V(G)|/(2\alpha(G)-1) had d ( G ) ≥ ∣ V ( G ) ∣/ ( 2 α ( G ) − 1 ) for every graph G G G . We extend both these results.
Theorem 3. Every n n n -vertex graph G G G with α ( G ) ≥ 2 \alpha(G) \ge2 α ( G ) ≥ 2 satisfies
had d ( G ) ≥ n + ω ( G ) 2 α ( G ) − 1 . \operatorname{had}_{d}(G) \ge\frac{n+\omega(G)}{2\alpha(G)-1}. had d ( G ) ≥ 2 α ( G ) − 1 n + ω ( G ) .
Our next result gives a constant-factor improvement of the Duchet–Meyniel bound in the dominating setting, which qualitatively extends the results of Fox [20 ] and Balogh and Kostochka [3 ] .
Theorem 4. Let c : = ( 49 − 2113 ) / 72 c := (49-\sqrt{2113})/72 c := ( 49 − 2113 ) /72 . Every n n n -vertex graph G G G with n ≥ 1 n \ge1 n ≥ 1 satisfies
had d ( G ) ≥ n ( 2 − c ) α ( G ) = 72 95 + 2113 n α ( G ) > 0.51075 n α ( G ) . \operatorname{had}_{d}(G) \ge\frac{n}{(2-c)\alpha(G)}=\frac{72}{95+\sqrt{2113}}\frac{n}{\alpha(G)}>0.51075\frac{n}{\alpha(G)}. had d ( G ) ≥ ( 2 − c ) α ( G ) n = 95 + 2113 72 α ( G ) n > 0.51075 α ( G ) n .
Our proof follows the ideas of Fox [20 ] and Balogh and Kostochka [3 ] , but uses a simpler analysis at the expense of a weaker constant.
A key additional ingredient in the proof of Theorem 4 is the following result on claw-free graphs. A claw is an induced K 1 , 3 K_{1,3} K 1 , 3 , and a graph is claw-free if no induced subgraph is isomorphic to a claw. Chudnovsky and Fradkin [9 ] proved that every non-empty claw-free graph G G G satisfies had ( G ) ≥ 2 χ ( G ) / 3 \operatorname{had}(G) \ge2\chi(G)/3 had ( G ) ≥ 2 χ ( G ) /3 , proving an approximate version of Hadwiger’s Conjecture for claw-free graphs. We strengthen this to odd dominating models.
Theorem 5. Every non-empty claw-free graph G G G satisfies had o d ( G ) ≥ 2 χ ( G ) / 3 \operatorname{had}_{\mathrm{od}}(G) \ge2\chi(G)/3 had od ( G ) ≥ 2 χ ( G ) /3 .
The proof of the original claw-free result of Chudnovsky and Fradkin [9 ] relies on a detailed analysis using the structure theorem for claw-free graphs [12 ] . Subsequent results [13 , 14 , 38 ] allow us to give a shorter proof that generalises the bound to odd dominating models. Our proof of Theorem 5 still relies indirectly on the structure theorem of claw-free graphs since we use a bound of King and Reed [38 ] (see Theorem 14).
The Duchet–Meyniel theorem has been extended to settings (a) and (b). In setting (a), Kawarabayashi and Song [36 ] proved that every n n n -vertex graph G G G with n ≥ 1 n \ge1 n ≥ 1 satisfies had o d ( G ) ≥ n / ( 2 α ( G ) − 1 ) \operatorname{had}_{\mathrm{od}}(G) \ge n/(2\alpha(G)-1) had od ( G ) ≥ n / ( 2 α ( G ) − 1 ) . In setting (b), Illingworth and Wood [29 Theorem 14] proved that for every graph G G G with n ≥ 1 n \ge1 n ≥ 1 vertices there is an integer h h h with 1 ≤ h ≤ had d ( G ) 1 \le h \le\operatorname{had}_{d}(G) 1 ≤ h ≤ had d ( G ) such that G G G has an h h h -colourable induced subgraph on at least ( n + h ) / 2 (n+h)/2 ( n + h ) /2 vertices. Hence had d ( G ) ≥ n / ( 2 α ( G ) − 1 ) \operatorname{had}_{d}(G) \ge n/(2\alpha(G)-1) had d ( G ) ≥ n / ( 2 α ( G ) − 1 ) . Our next result extends the Duchet–Meyniel theorem to setting (c).
Theorem 6. For every n n n -vertex graph G G G with n ≥ 1 n \ge1 n ≥ 1 , there is an integer h h h with 1 ≤ h ≤ had o d ( G ) 1 \le h \le\operatorname{had}_{\mathrm{od}}(G) 1 ≤ h ≤ had od ( G ) such that G G G has an h h h -colourable induced subgraph on at least ( n + h ) / 2 (n+h)/2 ( n + h ) /2 vertices. In particular,
had o d ( G ) ≥ n 2 α ( G ) − 1 . \operatorname{had}_{\mathrm{od}}(G) \ge\frac{n}{2\alpha(G)-1}. had od ( G ) ≥ 2 α ( G ) − 1 n .
Since had o d ( G ) ≤ min { had o d ( G ) , had d ( G ) } \operatorname{had}_{\mathrm{od}}(G) \le\min\{\operatorname{had}_{\mathrm{od}}(G),\operatorname{had}_{d}(G)\} had od ( G ) ≤ min { had od ( G ) , had d ( G )} , Theorem 6 implies the above results of Duchet and Meyniel [19 ] , Kawarabayashi and Song [36 ] , and Illingworth and Wood [29 ] . In § 4 we prove a slightly stronger result (Theorem 18 ).
Does the Duchet–Meyniel bound also hold for strongly odd dominating models? no6 . Nevertheless, we show an analogue of Theorem 6 , with ( n + h ) / 2 (n+h)/2 ( n + h ) /2 replaced by ( n + h ) / 3 (n+h)/3 ( n + h ) /3 and 2 α ( G ) − 1 2\alpha(G)-1 2 α ( G ) − 1 replaced by 3 α ( G ) − 1 3\alpha(G)-1 3 α ( G ) − 1 .
Theorem 7. For every graph G G G with n ≥ 1 n \ge1 n ≥ 1 vertices, there is an integer h h h with 1 ≤ h ≤ hadsod ( G ) 1 \le h \le\operatorname{hadsod}(G) 1 ≤ h ≤ hadsod ( G ) such that G G G has an h h h -colourable induced subgraph on at least ( n + h ) / 3 (n+h)/3 ( n + h ) /3 vertices. In particular,
hadsod ( G ) ≥ n 3 α ( G ) − 1 . \operatorname{hadsod}(G) \ge\frac{n}{3\alpha(G)-1}. hadsod ( G ) ≥ 3 α ( G ) − 1 n .
Outline. We discuss related colouring problems in § 1.1 . We then prove Theorem 3 in § 2 , followed by Theorem 5 in § 2.1 . Next we prove Theorem 4 in § 3 . Finally, § 4 and § 5 establish the odd dominating and strongly odd dominating bounds (Theorems 6 and 7 ), together with the corresponding upper bounds on chromatic number (Propositions 22 and 26 ).
Graph Minors and Colouring
We now place Theorems 3 –7 in the context of more general conjectures and related problems studied in the literature.
Hadwiger’s Conjecture holds for t ≤ 4 t \le4 t ≤ 4 [18 , 27 ] . Wagner [62 ] proved that the t = 5 t=5 t = 5 case is equivalent to the four-colour theorem, and the t = 6 t=6 t = 6 case was proved by Robertson, Seymour, and Thomas [54 ] , also using the four-colour theorem.
For every K t K_t K t -minor-free graph G G G , Kostochka [40 ] and Thomason [60 ] independently proved that χ ( G ) = O ( t log t ) \chi(G)=O(t\sqrt{\log t}) χ ( G ) = O ( t log t ) . This was improved to χ ( G ) = O ( t ( log t ) 1 / 4 + ε ) \chi(G)=O(t(\log t)^{1/4+\varepsilon}) χ ( G ) = O ( t ( log t ) 1/4 + ε ) for every fixed ε > 0 \varepsilon>0 ε > 0 by Norin, Postle, and Song [45 ] . The bound was subsequently improved to χ ( G ) = O ( t log log t ) \chi(G)=O(t\log\log t) χ ( G ) = O ( t log log t ) by Delcourt and Postle [16 ] , to χ ( G ) = O ( t log log t ) \chi(G)=O(t\sqrt{\log\log t}) χ ( G ) = O ( t log log t ) by Lin [42 ] , and to χ ( G ) = O ( t log log log t ) \chi(G)=O(t\log\log\log t) χ ( G ) = O ( t log log log t ) by Liu and Luo [43 ] . Recently, Norin and Steiner [47 ] proved the linear Hadwiger Conjecture: every K t K_t K t -minor-free graph satisfies χ ( G ) ≤ C t \chi(G) \le Ct χ ( G ) ≤ C t for an absolute constant C C C . Wood [65 ] obtained an explicit bound χ ( G ) ≤ 1 , 118 , 430 t \chi(G) \le1,118,430t χ ( G ) ≤ 1 , 118 , 430 t . OpenAI also announced a qualitatively stronger linear list-colouring bound: χ l i s t ( G ) ≤ C t \chi_{\mathrm{list}}(G) \le Ct χ list ( G ) ≤ C t for every K t K_t K t -minor-free graph G G G [49 ] , where χ l i s t ( G ) \chi_{\mathrm{list}}(G) χ list ( G ) is the least k k k such that G G G can be properly coloured from any assignment of a list of k k k available colours to each vertex.
The case of Hadwiger’s Conjecture for graphs with independence number 2 has attracted particular attention [5 , 7 , 11 , 14 , 15 , 46 , 51 ] . Plummer et al. [51 ] proved that, for graphs with independence number 2, Hadwiger’s Conjecture is equivalent to Conjecture 2. Seymour [56 ] writes “My own belief is, if Hadwiger’s Conjecture is true for graphs with stability number two then it is probably true in general, so it would be very nice to decide this case”. Every graph of independence number 2 is claw-free. However, Hadwiger’s Conjecture is false, shown recently by OpenAI [48 ] , and their counterexamples have independence number 2. They showed:
Since the branch sets are pairwise vertex-disjoint, there are t − s t-s t − s branch sets containing at least four vertices. Therefore n ≥ s + 4 ( t − s ) = 4 t − 3 s n\ge s+4(t-s)=4t-3s n ≥ s + 4 ( t − s ) = 4 t − 3 s , and so t ≤ n / 4 + 3 s / 4 = n / 4 + O ( n log n ) t\le n/4+3s/4=n/4+O(\sqrt{n\log n}) t ≤ n /4 + 3 s /4 = n /4 + O ( n log n ) , which is much less than the predicted bound of n / 3 n/3 n /3 .
Theorem 8 (OpenAI [48 Corollary 1.2] ). There are n n n -vertex graphs G G G of independence number 2, for arbitrarily large n n n , for which
χ ( G ) > 75 52 had ( G ) − 25 26 . \chi(G) > \frac{75}{52}\operatorname{had}(G) - \frac{25}{26}. χ ( G ) > 52 75 had ( G ) − 26 25 . Thus Hadwiger’s Conjecture is false.
Another strengthening of Hadwiger’s Conjecture is the Odd Hadwiger Conjecture, proposed by Gerards and Seymour [56 ] . It asserts that for every graph G G G , had o ( G ) ≥ χ ( G ) \operatorname{had}_{\mathrm{o}}(G) \ge\chi(G) had o ( G ) ≥ χ ( G ) .
The Odd Hadwiger Conjecture holds for t ≤ 4 t \le4 t ≤ 4 , and Guenin [26 ] announced a proof for t = 5 t = 5 t = 5 ; see Seymour [56 ] for background. Geelen, Gerards, Reed, Seymour, and Vetta [23 ] proved that every graph with no odd K t K_t K t -minor is O ( t log t ) O(t\sqrt{\log t}) O ( t log t ) -colourable; Kawarabayashi [32 ] subsequently gave a shorter proof. Steiner [59 ] proved that if every K t K_t K t -minor-free graph is f ( t ) f(t) f ( t ) -colourable, then every graph with no odd K t K_t K t -minor is 2 f ( t ) 2f(t) 2 f ( t ) -colourable. Together with the linear bound of Norin and Steiner [47 ] , this implies that every graph with no odd K t K_t K t -minor satisfies χ ( G ) ≤ C t \chi(G) \le Ct χ ( G ) ≤ C t for some absolute constant C C C .
Nevertheless, Kühn, Sauermann, Steiner, and Wigderson [41 ] disproved the Odd Hadwiger Conjecture. Their counterexamples also have independence number 2. Since these graphs are claw-free, their construction also shows that the constant 2 / 3 2/3 2/3 in Theorem 5 is asymptotically best possible.
Theorem 9 (Kühn et al. [41 Theorem 1.3] ). For every ε > 0 \varepsilon> 0 ε > 0 and all sufficiently large t t t , there is a graph G G G with independence number 2 with no odd K t K_t K t -minor, and χ ( G ) ≥ ( 3 / 2 − ε ) t \chi(G) \ge(3/2 - \varepsilon)t χ ( G ) ≥ ( 3/2 − ε ) t .
Illingworth and Wood [29 ] asked whether χ ( G ) ≤ had d ( G ) \chi(G) \le\operatorname{had}_{\mathrm{d}}(G) χ ( G ) ≤ had d ( G ) for every graph G G G . This question became known as the Dominating Hadwiger Conjecture. For t ≤ 3 t \le3 t ≤ 3 , a graph has a dominating K t K_t K t -model if and only if it has a K t K_t K t -model [29 ] . So had d ( G ) = had ( G ) \operatorname{had}_{\mathrm{d}}(G) = \operatorname{had}(G) had d ( G ) = had ( G ) whenever had d ( G ) ≤ 2 \operatorname{had}_{\mathrm{d}}(G) \le2 had d ( G ) ≤ 2 , and the Dominating Hadwiger Conjecture holds for graphs G G G with had d ( G ) ≤ 2 \operatorname{had}_{\mathrm{d}}(G) \le2 had d ( G ) ≤ 2 . Illingworth and Wood [29 ] proved that every graph G G G with had d ( G ) ≤ 3 \operatorname{had}_{\mathrm{d}}(G) \le3 had d ( G ) ≤ 3 is 3-colourable, and that χ ( G ) ≤ 2 had d ( G ) − 1 \chi(G) \le2^{\operatorname{had}_{\mathrm{d}}(G)}-1 χ ( G ) ≤ 2 had d ( G ) − 1 for every graph G G G . Girão et al. [24 ] proved that every graph G G G with had d ( G ) ≤ 4 \operatorname{had}_{\mathrm{d}}(G) \le4 had d ( G ) ≤ 4 is 4-colourable. Girão et al. [25 ] proved that every graph with average degree at least C t ( log t ) 2 Ct(\log t)^2 C t ( log t ) 2 has a dominating K t K_t K t -model, where C C C is an absolute constant. Since a dominating K t K_t K t -model in a subgraph of G G G is also a dominating K t K_t K t -model in G G G , it follows that every graph with no dominating K t K_t K t -model is O ( t ( log t ) 2 ) O(t(\log t)^2) O ( t ( log t ) 2 ) -degenerate, and is thus O ( t ( log t ) 2 ) O(t(\log t)^2) O ( t ( log t ) 2 ) -colourable. Scully and Song [55 ] proved the Dominating Hadwiger Conjecture for several classes of graphs G G G with α ( G ) ≤ 2 \alpha(G) \le2 α ( G ) ≤ 2 , and Song and Tibbetts [57 ] proved it for 2 K 2 2K_2 2 K 2 -free graphs. Illingworth and Steiner [28 ] disproved the Dominating Hadwiger Conjecture, using graphs G G G with α ( G ) ≤ 2 \alpha(G) \le2 α ( G ) ≤ 2 . Since had d ( G ) ≤ had ( G ) \operatorname{had}_{\mathrm{d}}(G) \le\operatorname{had}(G) had d ( G ) ≤ had ( G ) , the OpenAI counterexample [48 ] is also a counterexample to the Dominating Hadwiger Conjecture.
For odd dominating and strongly odd dominating models, the case t = 3 t = 3 t = 3 is easy. For every graph G G G ,7
had s o d ( G ) ≤ 2 ⟺ had o d ( G ) ≤ 2 ⟺ G is bipartite . \operatorname{had}_{\mathrm{sod}}(G) \le2 \Longleftrightarrow\operatorname{had}_{\mathrm{od}}(G) \le2 \Longleftrightarrow G\text{ is bipartite}. had sod ( G ) ≤ 2 ⟺ had od ( G ) ≤ 2 ⟺ G is bipartite .
Consequently, χ ( G ) ≤ had o d ( G ) \chi(G) \le\operatorname{had}_{od}(G) χ ( G ) ≤ had o d ( G ) for every graph G G G with had o d ( G ) ≤ 2 \operatorname{had}_{od}(G) \le2 had o d ( G ) ≤ 2 , and χ ( G ) ≤ had s o d ( G ) \chi(G) \le\operatorname{had}_{sod}(G) χ ( G ) ≤ had so d ( G ) for every graph G G G with had s o d ( G ) ≤ 2 \operatorname{had}_{sod}(G) \le2 had so d ( G ) ≤ 2 . Further, for every non-empty graph G G G , Propositions 22 and 26 give the exponential bounds χ ( G ) ≤ 2 had o d ( G ) − 1 \chi(G) \le2^{\operatorname{had}_{od}(G)-1} χ ( G ) ≤ 2 had o d ( G ) − 1 and χ ( G ) ≤ 3 ⋅ 2 had s o d ( G ) − 5 \chi(G) \le3 \cdot2^{\operatorname{had}_{sod}(G)} - 5 χ ( G ) ≤ 3 ⋅ 2 had so d ( G ) − 5 .
In light of OpenAI [48 ] ’s construction showing that had ( G ) / χ ( G ) \operatorname{had}(G)/\chi(G) had ( G ) / χ ( G ) can be asymptotically at most 52 / 75 = 2 / 3 + 2 / 75 52/75 = 2/3 + 2/75 52/75 = 2/3 + 2/75 , together with the recent proof of the linear Hadwiger Conjecture [47 , 49 , 65 ] , it is natural to ask for the best possible ratio between the Hadwiger number and chromatic number for a graph class. For a class G \mathcal{G} G of graphs, define
ρ ( G ) : = inf { had ( G ) χ ( G ) : G ∈ G is non-empty } , \rho(\mathcal{G}) := \inf\left\{ \frac{\operatorname{had}(G)}{\chi(G)} : G \in\mathcal{G}\text{ is non-empty} \right\}, ρ ( G ) := inf { χ ( G ) had ( G ) : G ∈ G is non-empty } ,
and define ρ d ( G ) \rho_d(\mathcal{G}) ρ d ( G ) and ρ o ( G ) \rho_o(\mathcal{G}) ρ o ( G ) analogously using had d ( G ) \operatorname{had}_d(G) had d ( G ) and had o ( G ) \operatorname{had}_o(G) had o ( G ) , respectively. For the class of claw-free graphs, we write ρ : = ρ ( claw-free ) \rho:= \rho(\text{claw-free}) ρ := ρ ( claw-free ) , ρ d : = ρ d ( claw-free ) \rho_d := \rho_d(\text{claw-free}) ρ d := ρ d ( claw-free ) , and ρ o : = ρ o ( claw-free ) \rho_o := \rho_o(\text{claw-free}) ρ o := ρ o ( claw-free ) . For claw-free graphs, Chudnovsky and Fradkin [9 ] and Theorems 5 and 8 give
2 3 ≤ ρ d ≤ ρ ≤ 2 3 + 2 75 , \frac{2}{3} \le\rho_d \le\rho\le\frac{2}{3} + \frac{2}{75}, 3 2 ≤ ρ d ≤ ρ ≤ 3 2 + 75 2 ,
where the upper bound follows from OpenAI [48 ] . Moreover, Theorems 5 and 9 give ρ o = 2 / 3 \rho_o = 2/3 ρ o = 2/3 , with the upper bound due to Kühn et al. [41 ] .
Dominating models and the clique number
We need the following preliminary results.
Lemma 10 (Illingworth and Wood [29 ] ). Every n n n -vertex graph G G G with n ≥ 1 n \ge1 n ≥ 1 satisfies
n ≤ ( 2 α ( G ) − 1 ) had d ( G ) . (1) n \le(2\alpha(G)-1)\operatorname{had}_d(G). \tag*{(1)} n ≤ ( 2 α ( G ) − 1 ) had d ( G ) . (1)
We also use the following lemma of Fujita and Park [21 Lemma 2.5] ; see also Chudnovsky, Lagoutte, Seymour, and Spirkl [10 10.1] for a short proof.
Lemma 11 (Fujita and Park [21 ] ). Every non-empty connected graph H H H has a set S ⊆ V ( H ) S \subseteq V(H) S ⊆ V ( H ) such that H [ S ] H[S] H [ S ] is connected, ∣ S ∣ ≤ 2 α ( H ) − 1 |S| \le2\alpha(H)-1 ∣ S ∣ ≤ 2 α ( H ) − 1 and α ( H [ S ] ) = α ( H ) \alpha(H[S]) = \alpha(H) α ( H [ S ]) = α ( H ) .
We now prove Theorem 3 , following the proof of Theorem 1.2 of Kawarabayashi et al. [34 ] . Using Lemma 11 yields a slightly shorter argument than the original proof of Kawarabayashi et al. [34 ] .
Proof of Theorem 3. Equivalently, we show that every n n n -vertex graph G G G with α ( G ) ≥ 2 \alpha(G) \ge2 α ( G ) ≥ 2 satisfies
n + ω ( G ) ≤ ( 2 α ( G ) − 1 ) had d ( G ) . n + \omega(G) \le(2\alpha(G)-1)\operatorname{had}_d(G). n + ω ( G ) ≤ ( 2 α ( G ) − 1 ) had d ( G ) .
We proceed by induction on n n n . Let a : = α ( G ) ≥ 2 a := \alpha(G) \ge2 a := α ( G ) ≥ 2 and h : = had d ( G ) h := \operatorname{had}_d(G) h := had d ( G ) . Let Q Q Q be a maximum clique of G G G , and let H : = G − Q H := G - Q H := G − Q . Then ∣ Q ∣ = ω ( G ) ≤ h |Q| = \omega(G) \le h ∣ Q ∣ = ω ( G ) ≤ h .
Case 1: α ( H ) ≤ a − 1 \alpha(H) \le a - 1 α ( H ) ≤ a − 1 . Since a ≥ 2 a \ge2 a ≥ 2 , the graph G G G is not complete, so H H H is non-empty, and (1) applied to H H H gives ∣ V ( H ) ∣ ≤ ( 2 α ( H ) − 1 ) had d ( H ) ≤ ( 2 a − 3 ) h |V(H)| \le(2\alpha(H)-1)\operatorname{had}_d(H) \le(2a-3)h ∣ V ( H ) ∣ ≤ ( 2 α ( H ) − 1 ) had d ( H ) ≤ ( 2 a − 3 ) h . Hence
n + ω ( G ) = ∣ V ( H ) ∣ + 2 ∣ Q ∣ ≤ ( 2 a − 3 ) h + 2 h = ( 2 a − 1 ) h . n + \omega(G) = |V(H)| + 2|Q| \le(2a-3)h + 2h = (2a-1)h. n + ω ( G ) = ∣ V ( H ) ∣ + 2∣ Q ∣ ≤ ( 2 a − 3 ) h + 2 h = ( 2 a − 1 ) h .
Case 2: α ( H ) = a \alpha(H) = a α ( H ) = a and H H H is connected. By Lemma 11, there is a set S ⊆ V ( H ) S \subseteq V(H) S ⊆ V ( H ) such that G [ S ] G[S] G [ S ] is connected, ∣ S ∣ ≤ 2 a − 1 |S| \le2a - 1 ∣ S ∣ ≤ 2 a − 1 and α ( G [ S ] ) = a \alpha(G[S]) = a α ( G [ S ]) = a . Every vertex v ∈ V ( G ) ∖ S v \in V(G) \setminus S v ∈ V ( G ) ∖ S has a neighbour in S S S , since otherwise v v v together with a maximum independent set of G [ S ] G[S] G [ S ] is an independent set of size $a+1 in G G G . Let G ′ : = G − S G' := G - S G ′ := G − S . If ( T 1 , … , T k ) (T_1, \ldots, T_k) ( T 1 , … , T k ) is a dominating K k K_k K k -model in G ′ G' G ′ , then ( T 0 , T 1 , … , T k ) (T_0, T_1, \ldots, T_k) ( T 0 , T 1 , … , T k ) is a dominating K k + 1 K_{k+1} K k + 1 -model in G G G , where T 0 T_0 T 0 is a spanning tree of G [ S ] G[S] G [ S ] . Thus had d ( G ′ ) ≤ h − 1 \operatorname{had}_{\mathrm{d}}(G') \le h - 1 had d ( G ′ ) ≤ h − 1 . Since Q ⊆ V ( G ′ ) Q \subseteq V(G') Q ⊆ V ( G ′ ) , we have ω ( G ′ ) = ∣ Q ∣ \omega(G') = |Q| ω ( G ′ ) = ∣ Q ∣ , and G ′ G' G ′ is non-empty. If α ( G ′ ) ≥ 2 \alpha(G') \ge2 α ( G ′ ) ≥ 2 , then by induction, ∣ V ( G ′ ) ∣ + ∣ Q ∣ ≤ ( 2 α ( G ′ ) − 1 ) had d ( G ′ ) |V(G')| + |Q| \le(2\alpha(G') - 1)\operatorname{had}_{\mathrm{d}}(G') ∣ V ( G ′ ) ∣ + ∣ Q ∣ ≤ ( 2 α ( G ′ ) − 1 ) had d ( G ′ ) . If α ( G ′ ) = 1 \alpha(G') = 1 α ( G ′ ) = 1 , then G ′ G' G ′ is complete. Since Q Q Q is a maximum clique of G G G and Q ⊆ V ( G ′ ) Q \subseteq V(G') Q ⊆ V ( G ′ ) , we have V ( G ′ ) = Q V(G') = Q V ( G ′ ) = Q , so ∣ V ( G ′ ) ∣ + ∣ Q ∣ = 2 ∣ V ( G ′ ) ∣ = 2 had d ( G ′ ) |V(G')| + |Q| = 2|V(G')| = 2\operatorname{had}_{\mathrm{d}}(G') ∣ V ( G ′ ) ∣ + ∣ Q ∣ = 2∣ V ( G ′ ) ∣ = 2 had d ( G ′ ) . Since α ( G ′ ) ≤ a \alpha(G') \le a α ( G ′ ) ≤ a and a ≥ 2 a \ge2 a ≥ 2 , in both cases
∣ V ( G ′ ) ∣ + ∣ Q ∣ ≤ ( 2 a − 1 ) ( h − 1 ) . |V(G')| + |Q| \le(2a - 1)(h - 1). ∣ V ( G ′ ) ∣ + ∣ Q ∣ ≤ ( 2 a − 1 ) ( h − 1 ) .
Adding ∣ S ∣ ≤ 2 a − 1 |S| \le2a - 1 ∣ S ∣ ≤ 2 a − 1 gives n + ω ( G ) ≤ ( 2 a − 1 ) h n + \omega(G) \le(2a - 1)h n + ω ( G ) ≤ ( 2 a − 1 ) h .
Case 3: α ( H ) = a \alpha(H) = a α ( H ) = a and H H H is disconnected. Partition V ( H ) V(H) V ( H ) into non-empty sets A 1 A_1 A 1 and A 2 A_2 A 2 with no edge between A 1 A_1 A 1 and A 2 A_2 A 2 , and let a i : = α ( H [ A i ] ) a_i := \alpha(H[A_i]) a i := α ( H [ A i ]) for i ∈ { 1 , 2 } i \in\{1,2\} i ∈ { 1 , 2 } . Then a 1 + a 2 = a a_1 + a_2 = a a 1 + a 2 = a and a 1 , a 2 ≥ 1 a_1, a_2 \ge1 a 1 , a 2 ≥ 1 . For each q ∈ Q q \in Q q ∈ Q there exists i ∈ { 1 , 2 } i \in\{1,2\} i ∈ { 1 , 2 } such that q q q has a neighbour in every maximum independent set of H [ A i ] H[A_i] H [ A i ] . Otherwise, for each i ∈ { 1 , 2 } i \in\{1,2\} i ∈ { 1 , 2 } there is a maximum independent set J i J_i J i of H [ A i ] H[A_i] H [ A i ] containing no neighbour of q q q , and then J 1 ∪ J 2 ∪ { q } J_1 \cup J_2 \cup\{q\} J 1 ∪ J 2 ∪ { q } is an independent set of size a + 1 a + 1 a + 1 in G G G , which is a contradiction. Assign each q ∈ Q q \in Q q ∈ Q to one such i i i , let Q i Q_i Q i be the set of vertices of Q Q Q assigned to i i i , and let G i : = G [ A i ∪ Q i ] G_i := G[A_i \cup Q_i] G i := G [ A i ∪ Q i ] .
We claim that α ( G i ) = a i \alpha(G_i) = a_i α ( G i ) = a i . Since H [ A i ] H[A_i] H [ A i ] is an induced subgraph of G i G_i G i , we have α ( G i ) ≥ a i \alpha(G_i) \ge a_i α ( G i ) ≥ a i . For the reverse inequality, let X X X be an independent set in G i G_i G i . Since Q i Q_i Q i is a clique, ∣ X ∩ Q i ∣ ≤ 1 |X \cap Q_i| \le1 ∣ X ∩ Q i ∣ ≤ 1 . If X ∩ Q i = ∅ X \cap Q_i = \varnothing X ∩ Q i = ∅ , then ∣ X ∣ ≤ a i |X| \le a_i ∣ X ∣ ≤ a i . If X ∩ Q i = { q } X \cap Q_i = \{q\} X ∩ Q i = { q } , then X ∖ { q } X \setminus\{q\} X ∖ { q } is an independent set of H [ A i ] H[A_i] H [ A i ] containing no neighbour of q q q , so X ∖ { q } X \setminus\{q\} X ∖ { q } is not a maximum independent set of H [ A i ] H[A_i] H [ A i ] , and ∣ X ∣ ≤ ( a i − 1 ) + 1 = a i |X| \le(a_i - 1) + 1 = a_i ∣ X ∣ ≤ ( a i − 1 ) + 1 = a i . This proves the claim.
Moreover, ∣ Q i ∣ ≤ ω ( G i ) |Q_i| \le\omega(G_i) ∣ Q i ∣ ≤ ω ( G i ) and had d ( G i ) ≤ h \operatorname{had}_{\mathrm{d}}(G_i) \le h had d ( G i ) ≤ h , and
n + ∣ Q ∣ = ∑ i = 1 2 ( ∣ V ( G i ) ∣ + ∣ Q i ∣ ) . n + |Q| = \sum_{i=1}^{2} \left(|V(G_i)| + |Q_i|\right). n + ∣ Q ∣ = i = 1 ∑ 2 ( ∣ V ( G i ) ∣ + ∣ Q i ∣ ) .
If a = 2 a = 2 a = 2 , then a 1 = a 2 = 1 a_1 = a_2 = 1 a 1 = a 2 = 1 , so each G i G_i G i is complete and ∣ V ( G i ) ∣ ≤ ∣ Q ∣ |V(G_i)| \le|Q| ∣ V ( G i ) ∣ ≤ ∣ Q ∣ . Hence n + ∣ Q ∣ = ∣ V ( G 1 ) ∣ + ∣ V ( G 2 ) ∣ + ∣ Q ∣ ≤ 3 ∣ Q ∣ ≤ 3 h = ( 2 a − 1 ) h n + |Q| = |V(G_1)| + |V(G_2)| + |Q| \le3|Q| \le3h = (2a - 1)h n + ∣ Q ∣ = ∣ V ( G 1 ) ∣ + ∣ V ( G 2 ) ∣ + ∣ Q ∣ ≤ 3∣ Q ∣ ≤ 3 h = ( 2 a − 1 ) h .
Now assume that a ≥ 3 a \ge3 a ≥ 3 . Each G i G_i G i has fewer vertices than G G G (since A 3 − i ≠ ∅ A_{3-i} \ne\varnothing A 3 − i = ∅ ), and
n + ∣ Q ∣ ≤ ∑ i = 1 2 ( ∣ V ( G i ) ∣ + ω ( G i ) ) . n + |Q| \le\sum_{i=1}^{2} \left(|V(G_i)| + \omega(G_i)\right). n + ∣ Q ∣ ≤ i = 1 ∑ 2 ( ∣ V ( G i ) ∣ + ω ( G i ) ) .
If a 1 , a 2 ≥ 2 a_1, a_2 \ge2 a 1 , a 2 ≥ 2 , then by induction the right-hand side is at most ( 2 a 1 − 1 ) h + ( 2 a 2 − 1 ) h = ( 2 a − 2 ) h (2a_1 - 1)h + (2a_2 - 1)h = (2a - 2)h ( 2 a 1 − 1 ) h + ( 2 a 2 − 1 ) h = ( 2 a − 2 ) h . Otherwise, without loss of generality, a 1 = 1 a_1 = 1 a 1 = 1 and a 2 = a − 1 ≥ 2 a_2 = a - 1 \ge2 a 2 = a − 1 ≥ 2 . Then G 1 G_1 G 1 is complete, so ∣ V ( G 1 ) ∣ + ω ( G 1 ) = 2 ∣ V ( G 1 ) ∣ = 2 had d ( G 1 ) ≤ 2 h |V(G_1)| + \omega(G_1) = 2|V(G_1)| = 2\operatorname{had}_{\mathrm{d}}(G_1) \le2h ∣ V ( G 1 ) ∣ + ω ( G 1 ) = 2∣ V ( G 1 ) ∣ = 2 had d ( G 1 ) ≤ 2 h , and ∣ V ( G 2 ) ∣ + ω ( G 2 ) ≤ ( 2 a − 3 ) h |V(G_2)| + \omega(G_2) \le(2a - 3)h ∣ V ( G 2 ) ∣ + ω ( G 2 ) ≤ ( 2 a − 3 ) h by induction. Thus the right-hand side is at most ( 2 a − 1 ) h (2a - 1)h ( 2 a − 1 ) h . In both cases, n + ω ( G ) ≤ ( 2 a − 1 ) h n + \omega(G) \le(2a - 1)h n + ω ( G ) ≤ ( 2 a − 1 ) h .
Claw-free graphs
We need the following results. The first result is a straightforward extension of a deep result of Chudnovsky and Seymour [14, 1.3] to odd dominating models. For completeness, we provide the proof in the Appendix. We remark that related results for had d \operatorname{had}_{\mathrm{d}} had d and had o \operatorname{had}_{\mathrm{o}} had o were previously proved by Scully and Song [55, Theorem 1.6] and Ji, Song, Weiss, and Zhang [31, Theorem 1.7], respectively.
Lemma 12. Every n n n -vertex graph G G G with n ≥ 1 n \ge1 n ≥ 1 , α ( G ) ≤ 2 \alpha(G) \le2 α ( G ) ≤ 2 and 2 ω ( G ) ≥ ⌈ n / 2 ⌉ + 1 2\omega(G) \ge\lceil n/2\rceil+ 1 2 ω ( G ) ≥ ⌈ n /2 ⌉ + 1 has had o ( G ) ≥ ⌈ n / 2 ⌉ \operatorname{had}_{\mathrm{o}}(G) \ge\lceil n/2\rceil had o ( G ) ≥ ⌈ n /2 ⌉ .
A graph G G G is tame if there is a connected claw-free graph H H H with α ( H ) ≥ 3 \alpha(H) \ge3 α ( H ) ≥ 3 such that G G G is an induced subgraph of H H H .
Theorem 13 (Chudnovsky and Seymour [13 1.7] ). Let G G G be tame . Then either α ( G ) ≥ 3 \alpha(G) \ge3 α ( G ) ≥ 3 , or V ( G ) V(G) V ( G ) is the union of four cliques.
In particular, if G G G is tame and α ( G ) ≤ 2 \alpha(G) \le2 α ( G ) ≤ 2 , then Theorem 13 implies that V ( G ) V(G) V ( G ) is the union of four cliques, so ω ( G ) ≥ ∣ V ( G ) ∣ / 4 \omega(G) \ge|V(G)|/4 ω ( G ) ≥ ∣ V ( G ) ∣/4 . This linear bound is stronger than what Ramsey theory gives: there are graphs with α ( G ) = 2 \alpha(G)=2 α ( G ) = 2 and ω ( G ) = Θ ( ∣ V ( G ) ∣ log ∣ V ( G ) ∣ ) \omega(G)=\Theta(\sqrt{|V(G)|}\log|V(G)|) ω ( G ) = Θ ( ∣ V ( G ) ∣ log ∣ V ( G ) ∣ ) [37 ] .
The next result concerns Reed’s ( ω , Δ , χ ) (\omega,\Delta,\chi) ( ω , Δ , χ ) -conjecture. Reed [52 ] conjectured that every non-empty graph G G G satisfies χ ( G ) ≤ ⌈ ( Δ ( G ) + 1 + ω ( G ) ) / 2 ⌉ \chi(G) \le\lceil(\Delta(G)+1+\omega(G))/2\rceil χ ( G ) ≤ ⌈( Δ ( G ) + 1 + ω ( G )) /2 ⌉ . The conjecture remains open in general, but it was proved for claw-free graphs by King and Reed [38 ] using the structure theorem of claw-free graphs [12 ] .
Theorem 14 (King and Reed [38 Theorem 1.6] ). If G G G is a non-empty claw-free graph, then χ ( G ) ≤ ⌈ ( Δ ( G ) + 1 + ω ( G ) ) / 2 ⌉ \chi(G) \le\lceil(\Delta(G)+1+\omega(G))/2\rceil χ ( G ) ≤ ⌈( Δ ( G ) + 1 + ω ( G )) /2 ⌉ .
A graph G G G is vertex-critical if χ ( G − v ) < χ ( G ) \chi(G-v)<\chi(G) χ ( G − v ) < χ ( G ) for every v ∈ V ( G ) v\in V(G) v ∈ V ( G ) . A graph G G G is decomposable if V ( G ) V(G) V ( G ) can be partitioned into two subsets A A A and B B B with A , B ≠ ∅ A,B\ne\varnothing A , B = ∅ such that each vertex of A A A is adjacent to each vertex of B B B . Equivalently, G G G is decomposable if the complement G ‾ \overline{G} G is disconnected. We need the following deep theorem of Gallai [22 ] (see Stehlík [58 ] for a strengthening).
Theorem 15 (Gallai [22 ] ). Every vertex-critical graph G G G with ∣ V ( G ) ∣ < 2 χ ( G ) − 1 |V(G)|<2\chi(G)-1 ∣ V ( G ) ∣ < 2 χ ( G ) − 1 is decomposable.
Lastly, we need the following modification of a result of Plummer, Stiebitz, and Toft [51 Theorem 3.3] to odd dominating models. The proof of Lemma 16 is a straightforward modification of the proof in Plummer et al. [51 Theorem 3.3] ; we provide the proof in the Appendix. Observe that Lemma 16 is a strengthening of Theorem 3 in the α ( G ) ≤ 2 \alpha(G)\le2 α ( G ) ≤ 2 case.
Lemma 16 (Plummer et al. [51 Theorem 3.3(a)] , modified). Every n n n -vertex graph G G G with n ≥ 1 n\ge1 n ≥ 1 and α ( G ) ≤ 2 \alpha(G)\le2 α ( G ) ≤ 2 satisfies had o d ( G ) ≥ ⌈ ( ω ( G ) + n ) / 3 ⌉ \operatorname{had}_{\mathrm{od}}(G)\ge\lceil(\omega(G)+n)/3\rceil had od ( G ) ≥ ⌈( ω ( G ) + n ) /3 ⌉ .
We now prove Theorem 5.
Theorem 5. Every non-empty claw-free graph G G G satisfies had o d ( G ) ≥ 2 χ ( G ) / 3 \operatorname{had}_{\mathrm{od}}(G)\ge2\chi(G)/3 had od ( G ) ≥ 2 χ ( G ) /3 .
Proof. Let G G G be a minimal claw-free counterexample, and let n : = ∣ V ( G ) ∣ n:=|V(G)| n := ∣ V ( G ) ∣ . The graph G G G is connected, since otherwise a component of maximum chromatic number is a smaller counterexample. Then had o d ( G ) < 2 χ ( G ) / 3 \operatorname{had}_{\mathrm{od}}(G)<2\chi(G)/3 had od ( G ) < 2 χ ( G ) /3 . If α ( G ) = 1 \alpha(G)=1 α ( G ) = 1 , then the result is immediate. First suppose that α ( G ) = 2 \alpha(G)=2 α ( G ) = 2 . Since G G G is a minimal counterexample, for each vertex v ∈ V ( G ) v\in V(G) v ∈ V ( G ) , had o d ( G − v ) ≥ 2 χ ( G − v ) / 3 \operatorname{had}_{\mathrm{od}}(G-v)\ge2\chi(G-v)/3 had od ( G − v ) ≥ 2 χ ( G − v ) /3 . Since had o d ( G − v ) ≤ had o d ( G ) \operatorname{had}_{\mathrm{od}}(G-v)\le\operatorname{had}_{\mathrm{od}}(G) had od ( G − v ) ≤ had od ( G ) , we have 2 χ ( G − v ) / 3 ≤ had o d ( G − v ) ≤ had o d ( G ) < 2 χ ( G ) / 3 2\chi(G-v)/3\le\operatorname{had}_{\mathrm{od}}(G-v)\le\operatorname{had}_{\mathrm{od}}(G)<2\chi(G)/3 2 χ ( G − v ) /3 ≤ had od ( G − v ) ≤ had od ( G ) < 2 χ ( G ) /3 . Thus χ ( G − v ) < χ ( G ) \chi(G-v)<\chi(G) χ ( G − v ) < χ ( G ) , and we deduce that G G G is vertex-critical. If G G G is decomposable, then V ( G ) = A ∪ B V(G)=A\cup B V ( G ) = A ∪ B , where A ∩ B = ∅ A\cap B=\varnothing A ∩ B = ∅ , A ≠ ∅ A\ne\varnothing A = ∅ and B ≠ ∅ B\ne\varnothing B = ∅ , and each vertex of A A A is adjacent to each vertex of B B B . Since G G G is a minimal counterexample, had o d ( G [ A ] ) ≥ 2 χ ( G [ A ] ) / 3 \operatorname{had}_{\mathrm{od}}(G[A])\ge2\chi(G[A])/3 had od ( G [ A ]) ≥ 2 χ ( G [ A ]) /3 and had o d ( G [ B ] ) ≥ 2 χ ( G [ B ] ) / 3 \operatorname{had}_{\mathrm{od}}(G[B])\ge2\chi(G[B])/3 had od ( G [ B ]) ≥ 2 χ ( G [ B ]) /3 . By swapping red and blue if necessary8 , choose the colourings of odd dominating models in G [ A ] G[A] G [ A ] and G [ B ] G[B] G [ B ] so that blue occurs in every branch set. Since every vertex of A A A is adjacent to every vertex of B B B , these models can
be concatenated, so had o d ( G ) ≥ had o d ( G [ A ] ) + had o d ( G [ B ] ) \operatorname{had}_{\mathrm{od}}(G) \ge\operatorname{had}_{\mathrm{od}}(G[A]) + \operatorname{had}_{\mathrm{od}}(G[B]) had od ( G ) ≥ had od ( G [ A ]) + had od ( G [ B ]) . Since χ ( G ) = χ ( G [ A ] ) + χ ( G [ B ] ) \chi(G) = \chi(G[A]) + \chi(G[B]) χ ( G ) = χ ( G [ A ]) + χ ( G [ B ]) , we obtain had o d ( G ) ≥ 2 χ ( G ) / 3 \operatorname{had}_{\mathrm{od}}(G) \ge2\chi(G)/3 had od ( G ) ≥ 2 χ ( G ) /3 , a contradiction. Consequently G G G is not decomposable, and Theorem 15 implies that n ≥ 2 χ ( G ) − 1 n \ge2\chi(G) - 1 n ≥ 2 χ ( G ) − 1 .9 By Lemma 16 , had o d ( G ) ≥ ( n + 1 ) / 3 \operatorname{had}_{\mathrm{od}}(G) \ge(n + 1)/3 had od ( G ) ≥ ( n + 1 ) /3 . Thus 3 had o d ( G ) − 1 ≥ n ≥ 2 χ ( G ) − 1 3\operatorname{had}_{\mathrm{od}}(G) - 1 \ge n \ge2\chi(G) - 1 3 had od ( G ) − 1 ≥ n ≥ 2 χ ( G ) − 1 and 3 had o d ( G ) ≥ 2 χ ( G ) 3\operatorname{had}_{\mathrm{od}}(G) \ge2\chi(G) 3 had od ( G ) ≥ 2 χ ( G ) , as desired.
Hence we may assume that α ( G ) ≥ 3 \alpha(G) \ge3 α ( G ) ≥ 3 . Let v v v be a vertex of maximum degree and let Z : = G [ N G ( v ) ] Z := G[N_G(v)] Z := G [ N G ( v )] . Then ∣ V ( Z ) ∣ = Δ ( G ) |V(Z)| = \Delta(G) ∣ V ( Z ) ∣ = Δ ( G ) and α ( Z ) ≤ 2 \alpha(Z) \le2 α ( Z ) ≤ 2 , since G G G is claw-free. Moreover, Z Z Z is tame, since G G G is connected and α ( G ) ≥ 3 \alpha(G) \ge3 α ( G ) ≥ 3 . By Theorem 13 , Z Z Z is the union of four cliques, so ω ( Z ) ≥ Δ ( G ) / 4 \omega(Z) \ge\Delta(G)/4 ω ( Z ) ≥ Δ ( G ) /4 .
First suppose that had o d ( G ) \operatorname{had}_{\mathrm{od}}(G) had od ( G ) is even. Choose a (possibly empty) clique Q Q Q of Z Z Z of size exactly ⌊ Δ ( G ) / 4 ⌋ \lfloor\Delta(G)/4 \rfloor ⌊ Δ ( G ) /4 ⌋ , and let q : = ∣ Q ∣ q := |Q| q := ∣ Q ∣ . Let Z ′ Z' Z ′ be an induced subgraph of Z Z Z containing Q Q Q such that ∣ V ( Z ′ ) ∣ = 4 q |V(Z')| = 4q ∣ V ( Z ′ ) ∣ = 4 q ; this is possible since 4 q ≤ Δ ( G ) 4q \le\Delta(G) 4 q ≤ Δ ( G ) . Let Z ′ ′ : = G [ V ( Z ′ ) ∪ { v } ] Z'' := G[V(Z') \cup\{v\}] Z ′′ := G [ V ( Z ′ ) ∪ { v }] . Then ∣ V ( Z ′ ′ ) ∣ = 4 q + 1 |V(Z'')| = 4q + 1 ∣ V ( Z ′′ ) ∣ = 4 q + 1 , α ( Z ′ ′ ) ≤ 2 \alpha(Z'') \le2 α ( Z ′′ ) ≤ 2 , and ω ( Z ′ ′ ) ≥ q + 1 \omega(Z'') \ge q + 1 ω ( Z ′′ ) ≥ q + 1 , and consequently,
2 ω ( Z ′ ′ ) ≥ 2 q + 2 = ⌈ ∣ V ( Z ′ ′ ) ∣ / 2 ⌉ + 1. 2\omega(Z'') \ge2q + 2 = \lceil|V(Z'')|/2 \rceil+ 1. 2 ω ( Z ′′ ) ≥ 2 q + 2 = ⌈ ∣ V ( Z ′′ ) ∣/2 ⌉ + 1.
By Lemma 12 applied to Z ′ ′ Z'' Z ′′ , had o d ( G ) ≥ had o d ( Z ′ ′ ) ≥ 2 q + 1 \operatorname{had}_{\mathrm{od}}(G) \ge\operatorname{had}_{\mathrm{od}}(Z'') \ge2q + 1 had od ( G ) ≥ had od ( Z ′′ ) ≥ 2 q + 1 . Since had o d ( G ) \operatorname{had}_{\mathrm{od}}(G) had od ( G ) is even, had o d ( G ) ≥ 2 q + 2 \operatorname{had}_{\mathrm{od}}(G) \ge2q + 2 had od ( G ) ≥ 2 q + 2 . Therefore, Δ ( G ) ≤ 4 q + 3 ≤ 2 had o d ( G ) − 1 \Delta(G) \le4q + 3 \le2\operatorname{had}_{\mathrm{od}}(G) - 1 Δ ( G ) ≤ 4 q + 3 ≤ 2 had od ( G ) − 1 .
Now suppose that had o d ( G ) \operatorname{had}_{\mathrm{od}}(G) had od ( G ) is odd. Choose a clique Q Q Q of Z Z Z of size exactly ⌈ Δ ( G ) / 4 ⌉ \lceil\Delta(G)/4 \rceil ⌈ Δ ( G ) /4 ⌉ , and let q : = ∣ Q ∣ q := |Q| q := ∣ Q ∣ . Let Z ′ Z' Z ′ be an induced subgraph of Z Z Z containing Q Q Q such that ∣ V ( Z ′ ) ∣ = 4 q − 3 |V(Z')| = 4q - 3 ∣ V ( Z ′ ) ∣ = 4 q − 3 ; this is possible since 4 q − 3 ≤ Δ ( G ) 4q - 3 \le\Delta(G) 4 q − 3 ≤ Δ ( G ) . Then α ( Z ′ ) ≤ 2 \alpha(Z') \le2 α ( Z ′ ) ≤ 2 and ω ( Z ′ ) ≥ q \omega(Z') \ge q ω ( Z ′ ) ≥ q , and consequently,
2 ω ( Z ′ ) ≥ 2 q = ⌈ ∣ V ( Z ′ ) ∣ / 2 ⌉ + 1. 2\omega(Z') \ge2q = \lceil|V(Z')|/2 \rceil+ 1. 2 ω ( Z ′ ) ≥ 2 q = ⌈ ∣ V ( Z ′ ) ∣/2 ⌉ + 1.
By Lemma 12 applied to Z ′ Z' Z ′ , had o d ( Z ′ ) ≥ 2 q − 1 \operatorname{had}_{\mathrm{od}}(Z') \ge2q - 1 had od ( Z ′ ) ≥ 2 q − 1 . By swapping red and blue if necessary, we may choose a two-colouring of this model so that blue occurs in every branch set, and colour v v v blue. Since every vertex of Z ′ Z' Z ′ is adjacent to v v v , appending { v } \{v\} { v } as the last branch set gives had o d ( G ) ≥ had o d ( Z ′ ) + 1 ≥ 2 q \operatorname{had}_{\mathrm{od}}(G) \ge\operatorname{had}_{\mathrm{od}}(Z') + 1 \ge2q had od ( G ) ≥ had od ( Z ′ ) + 1 ≥ 2 q . Since had o d ( G ) \operatorname{had}_{\mathrm{od}}(G) had od ( G ) is odd, had o d ( G ) ≥ 2 q + 1 \operatorname{had}_{\mathrm{od}}(G) \ge2q + 1 had od ( G ) ≥ 2 q + 1 . Therefore, Δ ( G ) ≤ 4 q ≤ 2 had o d ( G ) − 2 \Delta(G) \le4q \le2\operatorname{had}_{\mathrm{od}}(G) - 2 Δ ( G ) ≤ 4 q ≤ 2 had od ( G ) − 2 .
We deduce that
Δ ( G ) ≤ { 2 had o d ( G ) − 1 , if had o d ( G ) is even , 2 had o d ( G ) − 2 , if had o d ( G ) is odd . (2) \Delta(G) \le
\begin{cases}
2\operatorname{had}_{\mathrm{od}}(G) - 1, & \text{if }\operatorname{had}_{\mathrm{od}}(G)\text{ is even},\\
2\operatorname{had}_{\mathrm{od}}(G) - 2, & \text{if }\operatorname{had}_{\mathrm{od}}(G)\text{ is odd}.
\end{cases} \tag*{(2)} Δ ( G ) ≤ { 2 had od ( G ) − 1 , 2 had od ( G ) − 2 , if had od ( G ) is even , if had od ( G ) is odd . (2)
Finally, Theorem 14 and Equation (2) and ω ( G ) ≤ had o d ( G ) \omega(G) \le\operatorname{had}_{\mathrm{od}}(G) ω ( G ) ≤ had od ( G ) give
2 χ ( G ) ≤ Δ ( G ) + ω ( G ) + 2 ≤ { 3 had o d ( G ) + 1 , if had o d ( G ) is even , 3 had o d ( G ) , if had o d ( G ) is odd . 2\chi(G) \le\Delta(G) + \omega(G) + 2 \le
\begin{cases}
3\operatorname{had}_{\mathrm{od}}(G) + 1, & \text{if }\operatorname{had}_{\mathrm{od}}(G)\text{ is even},\\
3\operatorname{had}_{\mathrm{od}}(G), & \text{if }\operatorname{had}_{\mathrm{od}}(G)\text{ is odd}.
\end{cases} 2 χ ( G ) ≤ Δ ( G ) + ω ( G ) + 2 ≤ { 3 had od ( G ) + 1 , 3 had od ( G ) , if had od ( G ) is even , if had od ( G ) is odd .
Since 2 χ ( G ) 2\chi(G) 2 χ ( G ) is even, in either case 2 χ ( G ) ≤ 3 had o d ( G ) 2\chi(G) \le3\operatorname{had}_{\mathrm{od}}(G) 2 χ ( G ) ≤ 3 had od ( G ) , contradicting the choice of G G G .
Note that the proof of Theorem 5 shows a stronger result: every non-empty claw-free graph G G G has an odd dominating K t K_t K t -model with t ≥ 2 χ ( G ) / 3 t \ge2\chi(G)/3 t ≥ 2 χ ( G ) /3 in which every branch set has at most three vertices. This is because the models constructed in Lemmas 12 and 16 have branch sets that are either induced three-vertex paths or single vertices.
One might wonder if Theorem 5 can be strengthened further by replacing had o d \operatorname{had}_{\mathrm{od}} had od with had s o d \operatorname{had}_{\mathrm{sod}} had sod . More precisely, does every claw-free graph G G G satisfy had s o d ( G ) ≥ 2 χ ( G ) / 3 \operatorname{had}_{\mathrm{sod}}(G) \ge2\chi(G)/3 had sod ( G ) ≥ 2 χ ( G ) /3 ? This is false.10
A constant-factor improvement for dominating models
In this section, we prove Theorem 4, which is a constant-factor improvement of the Duchet–Meyniel bound for dominating models.
Let S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) . We say that S S S is connected if G [ S ] G[S] G [ S ] is connected. The set S S S is dominating if each vertex in V ( G ) ∖ S V(G) \setminus S V ( G ) ∖ S has a neighbour in S S S . Write α ( S ) : = α ( G [ S ] ) \alpha(S) := \alpha(G[S]) α ( S ) := α ( G [ S ]) , and let c ( S ) c(S) c ( S ) denote the number of connected components of G [ S ] G[S] G [ S ] . Define the potential of S S S to be ϕ ( S ) : = 2 α ( S ) − c ( S ) − ∣ S ∣ \phi(S) := 2\alpha(S) - c(S) - |S| ϕ ( S ) := 2 α ( S ) − c ( S ) − ∣ S ∣ . The potential of a claw is one. A useful property of ϕ \phi ϕ is that it is additive on disjoint vertex subsets with no edges between them. This follows from the fact that the independence number, the number of components, and the number of vertices are all additive on disjoint vertex subsets with no edges between them. This notion is due to [20 ] .
A graph G G G is α \alpha α -connected if there is no partition of V ( G ) V(G) V ( G ) into sets A A A and B B B with A , B ≠ ∅ A, B \ne\varnothing A , B = ∅ such that α ( A ) + α ( B ) = α ( G ) \alpha(A) + \alpha(B) = \alpha(G) α ( A ) + α ( B ) = α ( G ) .11
Theorem 17 (Balogh and Kostochka [3 Lemma 2.1] ). Let G G G be an n n n -vertex α \alpha α -connected graph with n ≥ 1 n \ge1 n ≥ 1 . For every X ⊆ V ( G ) X \subseteq V(G) X ⊆ V ( G ) , G G G contains a connected dominating set X ~ \widetilde{X} X with ∣ X ~ ∣ ≤ 2 α ( G ) − 2 ϕ ( X ) / 3 − 1 |\widetilde{X}| \le2\alpha(G) - 2\phi(X)/3 - 1 ∣ X ∣ ≤ 2 α ( G ) − 2 ϕ ( X ) /3 − 1 .
We now prove Theorem 4. The argument does not extend to odd models, because its final step uses a connected dominating set as a new first branch set. We highlight this in the proof.
Theorem 4. Let c : = ( 49 − 2113 ) / 72 c := (49 - \sqrt{2113})/72 c := ( 49 − 2113 ) /72 . Every n n n -vertex graph G G G with n ≥ 1 n \ge1 n ≥ 1 satisfies
had d ( G ) ≥ n ( 2 − c ) α ( G ) = 72 95 + 2113 n α ( G ) > 0.51075 n α ( G ) . \operatorname{had}_{d}(G) \ge\frac{n}{(2-c)\alpha(G)} = \frac{72}{95+\sqrt{2113}}\frac{n}{\alpha(G)} > 0.51075\frac{n}{\alpha(G)}. had d ( G ) ≥ ( 2 − c ) α ( G ) n = 95 + 2113 72 α ( G ) n > 0.51075 α ( G ) n .
The proof follows the potential method of Balogh and Kostochka [3 ] and Fox [20 ] . We first choose a maximal collection of r r r pairwise vertex-disjoint induced claws with no edges between distinct claws. Let A A A be their union and B : = N G [ A ] B := N_G[A] B := N G [ A ] its closed neighbourhood. After removing B B B , the remaining graph D : = G − B D := G - B D := G − B is claw-free, so Theorem 5 implies that had d ( D ) \operatorname{had}_{d}(D) had d ( D ) is sufficiently large if ∣ V ( D ) ∣ |V(D)| ∣ V ( D ) ∣ is large, and thus we are done in that case. This forces ∣ V ( D ) ∣ |V(D)| ∣ V ( D ) ∣ to be small and hence ∣ B ∣ |B| ∣ B ∣ to be large. If α ( B ) \alpha(B) α ( B ) is small, then we apply induction on B B B to deduce that had d ( G [ B ] ) \operatorname{had}_{d}(G[B]) had d ( G [ B ]) is large. Thus α ( B ) \alpha(B) α ( B ) is large and B B B has a large independent set I I I . We then argue that A ∪ I A \cup I A ∪ I is a set of large potential. Applying Theorem 17 to A ∪ I A \cup I A ∪ I , we obtain a small connected dominating set of G G G , and finish by induction, using it as the first branch set of the dominating model. The main difference from Balogh and Kostochka [3 ] is that their proof requires a more complicated analysis to find a set of large potential, involving several cases according to the size of I I I and the structure of D D D . We avoid this analysis, at the cost of a slightly worse constant.
Proof. Note that 0 < c < 1 / 9 0 < c < 1/9 0 < c < 1/9 and 36 c 2 − 49 c + 2 = 0 36c^2 - 49c + 2 = 0 36 c 2 − 49 c + 2 = 0 . Let G G G be a minimal counterexample to Theorem 4, and let n : = ∣ V ( G ) ∣ n := |V(G)| n := ∣ V ( G ) ∣ . Thus n > ( 2 − c ) α ( G ) had d ( G ) n > (2-c)\alpha(G)\operatorname{had}_{d}(G) n > ( 2 − c ) α ( G ) had d ( G ) .
If V ( G ) V(G) V ( G ) had a partition into sets A A A and B B B with A , B ≠ ∅ A, B \ne\varnothing A , B = ∅ and α ( A ) + α ( B ) = α ( G ) \alpha(A) + \alpha(B) = \alpha(G) α ( A ) + α ( B ) = α ( G ) , then by minimality,
∣ A ∣ ≤ ( 2 − c ) α ( A ) had d ( G [ A ] ) ≤ ( 2 − c ) α ( A ) had d ( G ) . (3) |A| \le(2-c)\alpha(A)\operatorname{had}_{d}(G[A]) \le(2-c)\alpha(A)\operatorname{had}_{d}(G). \tag*{(3)} ∣ A ∣ ≤ ( 2 − c ) α ( A ) had d ( G [ A ]) ≤ ( 2 − c ) α ( A ) had d ( G ) . (3)
Together with the analogous inequality for B B B , Equation (3) gives n ≤ ( 2 − c ) α ( G ) had d ( G ) n \le(2-c)\alpha(G)\operatorname{had}_{d}(G) n ≤ ( 2 − c ) α ( G ) had d ( G ) , a contradiction. Hence G G G is α \alpha α -connected. In particular, G G G is connected.
If G G G is claw-free, then by Theorem 5, had d ( G ) ≥ 2 χ ( G ) / 3 ≥ 2 n / ( 3 α ( G ) ) > n / ( ( 2 − c ) α ( G ) ) \operatorname{had}_{d}(G) \ge2\chi(G)/3 \ge2n/(3\alpha(G)) > n/((2-c)\alpha(G)) had d ( G ) ≥ 2 χ ( G ) /3 ≥ 2 n / ( 3 α ( G )) > n / (( 2 − c ) α ( G )) , where the final inequality follows from c < 1 / 2 c < 1/2 c < 1/2 , a contradiction. Thus G G G has an induced claw. Choose a maximal family of r r r pairwise disjoint induced claws with no edges between distinct claws. Let A A A be the union of their vertex sets, let B : = N G [ A ] B := N_G[A] B := N G [ A ] be the closed neighbourhood, and let D : = G − B D := G - B D := G − B . Then
∣ A ∣ = 4 r , α ( A ) = 3 r , c ( A ) = r , ϕ ( A ) = r . |A| = 4r,\qquad\alpha(A) = 3r,\qquad c(A) = r,\qquad\phi(A) = r. ∣ A ∣ = 4 r , α ( A ) = 3 r , c ( A ) = r , ϕ ( A ) = r .
Claim. G G G contains a set with potential at least 3 c α ( G ) / 2 3c\alpha(G)/2 3 c α ( G ) /2 .
Proof. If r ≥ 3 c α ( G ) / 2 r \ge3c\alpha(G)/2 r ≥ 3 c α ( G ) /2 , then A A A is such a set. Thus assume that r < 3 c α ( G ) / 2 r < 3c\alpha(G)/2 r < 3 c α ( G ) /2 . Let I I I be a maximum independent set of G [ B ] G[B] G [ B ] , and consider A ∪ I A \cup I A ∪ I . This set has independence number α ( B ) \alpha(B) α ( B ) , at most r r r connected components since each vertex of I ∖ A I \setminus A I ∖ A is adjacent to a vertex of A A A , and at most 4 r + α ( B ) 4r + \alpha(B) 4 r + α ( B ) vertices. Hence
ϕ ( A ∪ I ) ≥ α ( B ) − 5 r . \phi(A \cup I) \ge\alpha(B) - 5r. ϕ ( A ∪ I ) ≥ α ( B ) − 5 r . If D D D is empty, then α ( B ) = α ( G ) \alpha(B) = \alpha(G) α ( B ) = α ( G ) , and since c < 1 / 9 c < 1/9 c < 1/9 and r < 3 c α ( G ) / 2 r < 3c\alpha(G)/2 r < 3 c α ( G ) /2 ,
α ( B ) = α ( G ) > 9 c α ( G ) > 5 r + 3 c α ( G ) 2 . \alpha(B) = \alpha(G) > 9c\alpha(G) > 5r + \frac{3c\alpha(G)}{2}. α ( B ) = α ( G ) > 9 c α ( G ) > 5 r + 2 3 c α ( G ) . Thus A ∪ I A \cup I A ∪ I has the required potential. Hence assume that D D D is non-empty, so B ≠ V ( G ) B \ne V(G) B = V ( G ) .
The maximality of r r r implies that D D D is claw-free. Since there are no edges between A A A and D D D , we also have α ( D ) ≤ α ( G ) − 3 r \alpha(D) \le\alpha(G) - 3r α ( D ) ≤ α ( G ) − 3 r . By Theorem 5,
∣ V ( D ) ∣ ≤ 3 2 α ( D ) had d ( D ) ≤ 3 2 ( α ( G ) − 3 r ) had d ( G ) . (4) |V(D)| \le\frac{3}{2}\alpha(D)\operatorname{had}_d(D) \le\frac{3}{2}(\alpha(G) - 3r)\operatorname{had}_d(G). \tag*{(4)} ∣ V ( D ) ∣ ≤ 2 3 α ( D ) had d ( D ) ≤ 2 3 ( α ( G ) − 3 r ) had d ( G ) . (4) Since G G G is a counterexample, had d ( G ) < n / ( ( 2 − c ) α ( G ) ) \operatorname{had}_d(G) < n/((2-c)\alpha(G)) had d ( G ) < n / (( 2 − c ) α ( G )) . Combining this with Equation (4) gives
∣ V ( D ) ∣ ≤ 3 ( α ( G ) − 3 r ) n 2 ( 2 − c ) α ( G ) . (5) |V(D)| \le\frac{3(\alpha(G) - 3r)n}{2(2-c)\alpha(G)}. \tag*{(5)} ∣ V ( D ) ∣ ≤ 2 ( 2 − c ) α ( G ) 3 ( α ( G ) − 3 r ) n . (5) Since V ( G ) = B ∪ V ( D ) V(G) = B \cup V(D) V ( G ) = B ∪ V ( D ) , Equation (5) gives
∣ B ∣ ≥ n − 3 ( α ( G ) − 3 r ) n 2 ( 2 − c ) α ( G ) = ( ( 1 − 2 c ) α ( G ) + 9 r ) n 2 ( 2 − c ) α ( G ) . (6) |B| \ge n - \frac{3(\alpha(G) - 3r)n}{2(2-c)\alpha(G)}
= \frac{((1-2c)\alpha(G) + 9r)n}{2(2-c)\alpha(G)}. \tag*{(6)} ∣ B ∣ ≥ n − 2 ( 2 − c ) α ( G ) 3 ( α ( G ) − 3 r ) n = 2 ( 2 − c ) α ( G ) (( 1 − 2 c ) α ( G ) + 9 r ) n . (6) Since ∣ B ∣ < ∣ V ( G ) ∣ |B| < |V(G)| ∣ B ∣ < ∣ V ( G ) ∣ , G [ B ] G[B] G [ B ] satisfies Theorem 4, so
∣ B ∣ ≤ ( 2 − c ) α ( B ) had d ( G ) < α ( B ) n α ( G ) . (7) |B| \le(2-c)\alpha(B)\operatorname{had}_d(G) < \frac{\alpha(B)n}{\alpha(G)}. \tag*{(7)} ∣ B ∣ ≤ ( 2 − c ) α ( B ) had d ( G ) < α ( G ) α ( B ) n . (7) Combining Equations (6) and (7) gives
α ( B ) > ∣ B ∣ α ( G ) n ≥ ( 1 − 2 c ) α ( G ) + 9 r 2 ( 2 − c ) . (8) \alpha(B) > \frac{|B|\alpha(G)}{n} \ge\frac{(1-2c)\alpha(G) + 9r}{2(2-c)}. \tag*{(8)} α ( B ) > n ∣ B ∣ α ( G ) ≥ 2 ( 2 − c ) ( 1 − 2 c ) α ( G ) + 9 r . (8) Since 36 c 2 − 49 c + 2 = 0 36c^2 - 49c + 2 = 0 36 c 2 − 49 c + 2 = 0 , we have 1 − 8 c + 3 c 2 = 3 c ( 11 − 10 c ) / 2 1 - 8c + 3c^2 = 3c(11 - 10c)/2 1 − 8 c + 3 c 2 = 3 c ( 11 − 10 c ) /2 . Therefore
( 1 − 2 c ) α ( G ) + 9 r 2 ( 2 − c ) − ( 5 r + 3 c α ( G ) 2 ) = ( 1 − 8 c + 3 c 2 ) α ( G ) − ( 11 − 10 c ) r 2 ( 2 − c ) = ( 11 − 10 c ) ( 3 c α ( G ) 2 − r ) 2 ( 2 − c ) > 0. (9) \frac{(1-2c)\alpha(G) + 9r}{2(2-c)}
-\left(5r + \frac{3c\alpha(G)}{2}\right)
= \frac{(1-8c+3c^2)\alpha(G) - (11-10c)r}{2(2-c)}
= \frac{(11-10c)\left(\frac{3c\alpha(G)}{2}-r\right)}{2(2-c)}
> 0. \tag*{(9)} 2 ( 2 − c ) ( 1 − 2 c ) α ( G ) + 9 r − ( 5 r + 2 3 c α ( G ) ) = 2 ( 2 − c ) ( 1 − 8 c + 3 c 2 ) α ( G ) − ( 11 − 10 c ) r = 2 ( 2 − c ) ( 11 − 10 c ) ( 2 3 c α ( G ) − r ) > 0. (9) The final inequality follows from r < 3 c α ( G ) / 2 r < 3c\alpha(G)/2 r < 3 c α ( G ) /2 and 11 − 10 c > 0 11 - 10c > 0 11 − 10 c > 0 . By Equations (8) and (9) , we have α ( B ) > 5 r + 3 c α ( G ) / 2 \alpha(B) > 5r + 3c\alpha(G)/2 α ( B ) > 5 r + 3 c α ( G ) /2 . Thus ϕ ( A ∪ I ) > 3 c α ( G ) / 2 \phi(A \cup I) > 3c\alpha(G)/2 ϕ ( A ∪ I ) > 3 c α ( G ) /2 , proving the claim.
By Theorem 17, applied to such a set, we deduce that G G G has a connected dominating set S S S with size at most
∣ S ∣ ≤ 2 α ( G ) − 2 3 ( 3 c α ( G ) 2 ) − 1 = ( 2 − c ) α ( G ) − 1. (10) |S| \le2\alpha(G)-\frac{2}{3}\left(\frac{3c\alpha(G)}{2}\right)-1=(2-c)\alpha(G)-1. \tag*{(10)} ∣ S ∣ ≤ 2 α ( G ) − 3 2 ( 2 3 c α ( G ) ) − 1 = ( 2 − c ) α ( G ) − 1. (10)
Since n > ( 2 − c ) α ( G ) n>(2-c)\alpha(G) n > ( 2 − c ) α ( G ) h a d d ( G ) ≥ ( 2 − c ) α ( G ) \mathrm{had}_{d}(G)\ge(2-c)\alpha(G) had d ( G ) ≥ ( 2 − c ) α ( G ) , G − S G-S G − S has at least one vertex. Let T T T be a spanning tree of G [ S ] G[S] G [ S ] . Prepending12 T T T to a dominating model in G − S G-S G − S shows that h a d d ( G − S ) ≤ h a d d ( G ) − 1 \mathrm{had}_{d}(G-S)\le\mathrm{had}_{d}(G)-1 had d ( G − S ) ≤ had d ( G ) − 1 . By minimality,
∣ V ( G − S ) ∣ ≤ ( 2 − c ) α ( G ) ( h a d d ( G ) − 1 ) . (11) |V(G-S)|\le(2-c)\alpha(G)(\mathrm{had}_{d}(G)-1). \tag*{(11)} ∣ V ( G − S ) ∣ ≤ ( 2 − c ) α ( G ) ( had d ( G ) − 1 ) . (11)
By Equations (10) and (11) ,
n ≤ ( 2 − c ) α ( G ) − 1 + ( 2 − c ) α ( G ) ( h a d d ( G ) − 1 ) = ( 2 − c ) α ( G ) h a d d ( G ) − 1 , n\le(2-c)\alpha(G)-1+(2-c)\alpha(G)(\mathrm{had}_{d}(G)-1)=(2-c)\alpha(G)\mathrm{had}_{d}(G)-1, n ≤ ( 2 − c ) α ( G ) − 1 + ( 2 − c ) α ( G ) ( had d ( G ) − 1 ) = ( 2 − c ) α ( G ) had d ( G ) − 1 ,
a contradiction.
Odd dominating models
The proof of Theorem 6 produces odd dominating models with the following additional property. A dominating K t K_t K t -model ( T 1 , … , T t ) (T_1,\ldots,T_t) ( T 1 , … , T t ) together with a colouring c c c of ⋃ i V ( T i ) \bigcup_i V(T_i) ⋃ i V ( T i ) with colours {red, blue} is red-dominating if every edge of every T i T_i T i is bichromatic, every T i T_i T i contains a vertex of colour red, and for 1 ≤ i < j ≤ t 1\le i<j\le t 1 ≤ i < j ≤ t every vertex of T j T_j T j has a neighbour of colour red in T i T_i T i . Every red-dominating K t K_t K t -model is an odd dominating K t K_t K t -model, since for i < j i<j i < j a vertex of colour red in T j T_j T j has a neighbour of colour red in T i T_i T i . Let h a d r d ( G ) \mathrm{had}_{\mathrm{rd}}(G) had rd ( G ) be the maximum integer t t t such that G G G has a red-dominating K t K_t K t -model. Then h a d r d ( G ) ≤ h a d o d ( G ) \mathrm{had}_{\mathrm{rd}}(G)\le\mathrm{had}_{\mathrm{od}}(G) had rd ( G ) ≤ had od ( G ) , so Theorem 6 is a consequence of the following result.
Theorem 18. For every graph G G G with n ≥ 1 n\ge1 n ≥ 1 vertices, there is an integer h h h with 1 ≤ h ≤ h a d r d ( G ) 1\le h\le\mathrm{had}_{\mathrm{rd}}(G) 1 ≤ h ≤ had rd ( G ) such that G G G has an h h h -colourable induced subgraph on at least ( n + h ) / 2 (n+h)/2 ( n + h ) /2 vertices. In particular,
h a d r d ( G ) ≥ n 2 α ( G ) − 1 . \mathrm{had}_{\mathrm{rd}}(G)\ge\frac{n}{2\alpha(G)-1}. had rd ( G ) ≥ 2 α ( G ) − 1 n .
The following lemma is implicit in the proofs of Duchet and Meyniel [19 ] , Kawarabayashi and Song [36 ] .
Lemma 19. Every non-empty connected graph G G G has a set D ⊆ V ( G ) D\subseteq V(G) D ⊆ V ( G ) , an independent set I ⊆ D I\subseteq D I ⊆ D with ∣ D ∣ ≤ 2 ∣ I ∣ − 1 |D|\le2|I|-1 ∣ D ∣ ≤ 2∣ I ∣ − 1 , and a spanning tree F F F of G [ D ] G[D] G [ D ] such that
every edge of F F F has exactly one end in I I I , and
every vertex of V ( G ) ∖ D V(G)\setminus D V ( G ) ∖ D has a neighbour in I I I .
Proof. There is at least one triple ( D , I , F ) (D,I,F) ( D , I , F ) satisfying all the stated conditions except possibly (2). For example, take D = I = { v } D=I=\{v\} D = I = { v } for any vertex v v v , and let F F F be the 1-vertex tree. Choose such a triple with ∣ I ∣ |I| ∣ I ∣ maximum, and suppose that (2) fails. Let N N N be the set of vertices in V ( G ) ∖ D V(G)\setminus D V ( G ) ∖ D with a neighbour in I I I , and let R : = V ( G ) ∖ ( D ∪ N ) R:=V(G)\setminus(D\cup N) R := V ( G ) ∖ ( D ∪ N ) . Then R ≠ ∅ R\ne\varnothing R = ∅ . Since G G G is connected, there is an edge y z yz y z with y ∈ R y\in R y ∈ R and z ∉ R z\notin R z ∈ / R . Since y ∉ N y\notin N y ∈ / N , the vertex y y y has no neighbour in I I I , so z ∉ I z\notin I z ∈ / I . Thus z ∈ N z\in N z ∈ N or z ∈ D ∖ I z\in D\setminus I z ∈ D ∖ I .
If z ∈ N z \in N z ∈ N , then let x ∈ I x \in I x ∈ I be a neighbour of z z z , and let D ′ : = D ∪ { y , z } D' := D \cup\{y,z\} D ′ := D ∪ { y , z } , I ′ : = I ∪ { y } I' := I \cup\{y\} I ′ := I ∪ { y } and F ′ : = F + x z + z y F' := F + xz + zy F ′ := F + x z + z y . Then I ′ I' I ′ is independent, each edge of F ′ F' F ′ has exactly one end in I ′ I' I ′ , and ∣ D ′ ∣ = ∣ D ∣ + 2 ≤ 2 ∣ I ′ ∣ − 1 |D'| = |D| + 2 \leq2|I'| - 1 ∣ D ′ ∣ = ∣ D ∣ + 2 ≤ 2∣ I ′ ∣ − 1 .
If z ∈ D ∖ I z \in D \setminus I z ∈ D ∖ I , then let D ′ : = D ∪ { y } D' := D \cup\{y\} D ′ := D ∪ { y } , I ′ : = I ∪ { y } I' := I \cup\{y\} I ′ := I ∪ { y } and F ′ : = F + z y F' := F + zy F ′ := F + z y . Then I ′ I' I ′ is independent, each edge of F ′ F' F ′ has exactly one end in I ′ I' I ′ , and ∣ D ′ ∣ = ∣ D ∣ + 1 < 2 ∣ I ′ ∣ − 1 |D'| = |D| + 1 < 2|I'| - 1 ∣ D ′ ∣ = ∣ D ∣ + 1 < 2∣ I ′ ∣ − 1 .
In both cases ∣ I ′ ∣ > ∣ I ∣ |I'| > |I| ∣ I ′ ∣ > ∣ I ∣ , which contradicts the choice of ( D , I , F ) (D,I,F) ( D , I , F ) .
In Lemma 19 , colour each vertex in I I I red and each vertex in D ∖ I D \setminus I D ∖ I blue. Then every edge of F F F is bichromatic, and every vertex of V ( G ) ∖ D V(G) \setminus D V ( G ) ∖ D has a neighbour of colour red in D D D . The analogous lemma of Illingworth and Wood [29 ] only guarantees that every vertex of V ( G ) ∖ D V(G) \setminus D V ( G ) ∖ D has a neighbour in D D D . This is not enough for oddness, since all the neighbours in D D D of a vertex outside D D D might have colour blue.
For a rooted forest T T T and vertices x , y ∈ V ( T ) x,y \in V(T) x , y ∈ V ( T ) , we say that x x x is a proper ancestor of y y y if x ≠ y x \ne y x = y and x x x lies on the path in T T T from y y y to the root of its component. Vertices x , y x,y x , y are comparable if x = y x = y x = y or one is a proper ancestor of the other. Applying Lemma 19 recursively gives the following structure theorem.
Theorem 20. For every graph G G G there is a rooted forest T T T and a partition { P x : x ∈ V ( T ) } \{P_x : x \in V(T)\} { P x : x ∈ V ( T )} of V ( G ) V(G) V ( G ) into non-empty parts, together with, for each x ∈ V ( T ) x \in V(T) x ∈ V ( T ) , an independent set I x ⊆ P x I_x \subseteq P_x I x ⊆ P x with ∣ P x ∣ ≤ 2 ∣ I x ∣ − 1 |P_x| \leq2|I_x| - 1 ∣ P x ∣ ≤ 2∣ I x ∣ − 1 and a spanning tree F x F_x F x of G [ P x ] G[P_x] G [ P x ] whose edges each have exactly one end in I x I_x I x , such that:
(1) if x , y ∈ V ( T ) x,y \in V(T) x , y ∈ V ( T ) are incomparable, then there is no edge of G G G between P x P_x P x and P y P_y P y ;
(2) if x x x is a proper ancestor of y y y , then every vertex of P y P_y P y has a neighbour in I x I_x I x .
Proof. We proceed by induction on ∣ V ( G ) ∣ |V(G)| ∣ V ( G ) ∣ . If G G G has no vertices, let T T T be empty. If G G G is disconnected, then apply induction to each component of G G G and take the union of the resulting forests. Then (1) holds since distinct components are not adjacent, and (2) holds within each component. Now assume that G G G is connected. Apply Lemma 19 to obtain ( D , I , F ) (D,I,F) ( D , I , F ) . By induction, G − D G - D G − D has a rooted forest T ′ T' T ′ and a partition { P x : x ∈ V ( T ′ ) } \{P_x : x \in V(T')\} { P x : x ∈ V ( T ′ )} with the stated properties. Let T T T be obtained from T ′ T' T ′ by adding a new vertex r r r adjacent to the root of each component of T ′ T' T ′ , and let r r r be the root of T T T . Let P r : = D P_r := D P r := D , I r : = I I_r := I I r := I and F r : = F F_r := F F r := F . Property (1) holds since r r r is comparable with every vertex of T T T , and incomparable vertices of T T T are incomparable in T ′ T' T ′ . Property (2) holds for x = r x = r x = r by Lemma 19 (2), and for x ≠ r x \ne r x = r by induction.
Paths from a root in this structure give red-dominating models.
Corollary 21. In the setting of Theorem 20 , let c ( v ) : = red c(v) := \text{red} c ( v ) := red if v ∈ ⋃ I x v \in\bigcup I_x v ∈ ⋃ I x and c ( v ) : = blue c(v) := \text{blue} c ( v ) := blue otherwise. If x 1 x_1 x 1 is a root of T T T and x i + 1 x_{i+1} x i + 1 is a child of x i x_i x i for 1 ≤ i < h 1 \leq i < h 1 ≤ i < h , then ( ( F x 1 , … , F x h ) , c ) ((F_{x_1},\ldots,F_{x_h}),c) (( F x 1 , … , F x h ) , c ) is a red-dominating K h K_h K h -model in G G G .
Proof. Each F x i F_{x_i} F x i is a tree whose edges are bichromatic, and F x i F_{x_i} F x i contains the vertices of I x i ≠ ∅ I_{x_i} \ne\varnothing I x i = ∅ , which have colour red. For i < j i < j i < j , the vertex x i x_i x i is a proper ancestor of x j x_j x j , so every vertex of F x j F_{x_j} F x j has a neighbour in I x i I_{x_i} I x i , which has colour red.
Proof of Theorem 18. Apply Theorem 20 to G G G , and let h h h be the maximum number of vertices on a path in T T T that starts at a root. Since G G G has at least one vertex, h ≥ 1 h \geq1 h ≥ 1 , and $h \leq \operatorname{had}_{\mathrm{rd}}(G) by Corollary 21. Let X : = ⋃ x ∈ V ( T ) I x X := \bigcup_{x\in V(T)} I_x X := ⋃ x ∈ V ( T ) I x . Then
∣ X ∣ = ∑ x ∈ V ( T ) ∣ I x ∣ ≥ ∑ x ∈ V ( T ) ∣ P x ∣ + 1 2 = n + ∣ V ( T ) ∣ 2 ≥ n + h 2 . |X| = \sum_{x\in V(T)} |I_x| \ge\sum_{x\in V(T)} \frac{|P_x|+1}{2} = \frac{n+|V(T)|}{2} \ge\frac{n+h}{2}. ∣ X ∣ = x ∈ V ( T ) ∑ ∣ I x ∣ ≥ x ∈ V ( T ) ∑ 2 ∣ P x ∣ + 1 = 2 n + ∣ V ( T ) ∣ ≥ 2 n + h .
Colour each vertex of I x I_x I x by the depth of x x x in T T T , where roots have depth 1. This uses at most h h h colours. Two distinct vertices of X X X with the same colour are either both in the same independent set I x I_x I x , or in parts P x P_x P x and P y P_y P y where x ≠ y x\ne y x = y have the same depth. In the latter case, x x x and y y y are incomparable, so the two vertices are non-adjacent by Theorem 20 (1). Thus G [ X ] G[X] G [ X ] is h h h -colourable. Some colour class of G [ X ] G[X] G [ X ] is an independent set of size at least
n + h 2 h = n 2 h + 1 2 ≥ n 2 had r d ( G ) + 1 2 = n + had r d ( G ) 2 had r d ( G ) . \frac{n+h}{2h} = \frac{n}{2h}+\frac{1}{2} \ge\frac{n}{2\operatorname{had}_{\mathrm{rd}}(G)}+\frac{1}{2} = \frac{n+\operatorname{had}_{\mathrm{rd}}(G)}{2\operatorname{had}_{\mathrm{rd}}(G)}. 2 h n + h = 2 h n + 2 1 ≥ 2 had rd ( G ) n + 2 1 = 2 had rd ( G ) n + had rd ( G ) .
Thus α ( G ) ≥ ( n + had r d ( G ) ) / ( 2 had r d ( G ) ) \alpha(G) \ge(n+\operatorname{had}_{\mathrm{rd}}(G))/(2\operatorname{had}_{\mathrm{rd}}(G)) α ( G ) ≥ ( n + had rd ( G )) / ( 2 had rd ( G )) , which rearranges to had r d ( G ) ≥ n / ( 2 α ( G ) − 1 ) \operatorname{had}_{\mathrm{rd}}(G) \ge n/(2\alpha(G)-1) had rd ( G ) ≥ n / ( 2 α ( G ) − 1 ) .
The next result bounds χ ( G ) \chi(G) χ ( G ) in terms of had r d ( G ) \operatorname{had}_{\mathrm{rd}}(G) had rd ( G ) . The proof adapts Wagner’s argument [63 ] for graphs with no K t K_t K t -model.
Proposition 22. Every graph G G G with at least one vertex satisfies χ ( G ) ≤ 2 had r d ( G ) − 1 \chi(G) \le2^{\operatorname{had}_{\mathrm{rd}}(G)-1} χ ( G ) ≤ 2 had rd ( G ) − 1 . In particular, χ ( G ) ≤ 2 had o d ( G ) − 1 \chi(G) \le2^{\operatorname{had}_{\mathrm{od}}(G)-1} χ ( G ) ≤ 2 had od ( G ) − 1 .
Proof. We proceed by induction on k ≥ 1 k \ge1 k ≥ 1 to show that every non-empty graph G G G with had r d ( G ) ≤ k \operatorname{had}_{\mathrm{rd}}(G) \le k had rd ( G ) ≤ k satisfies χ ( G ) ≤ 2 k − 1 \chi(G) \le2^{k-1} χ ( G ) ≤ 2 k − 1 . If k = 1 k=1 k = 1 , then ∣ E ( G ) ∣ = 0 |E(G)|=0 ∣ E ( G ) ∣ = 0 , so χ ( G ) = 1 \chi(G)=1 χ ( G ) = 1 .
Now let k ≥ 2 k \ge2 k ≥ 2 . We may assume that G G G is connected. Fix a vertex r r r , let L 0 : = { r } L_0 := \{r\} L 0 := { r } , and for i ≥ 1 i \ge1 i ≥ 1 , let L i L_i L i be the set of vertices at distance exactly i i i from r r r . Every edge of G G G has both ends in one L i L_i L i or ends in L i L_i L i and L i + 1 L_{i+1} L i + 1 for some i i i . Consequently the sets L i L_i L i with i i i even are pairwise non-adjacent, as are the sets L i L_i L i with i i i odd, and thus χ ( G ) ≤ 2 max i χ ( G [ L i ] ) \chi(G) \le2\max_i\chi(G[L_i]) χ ( G ) ≤ 2 max i χ ( G [ L i ]) . We now show that χ ( G [ L i ] ) ≤ 2 k − 2 \chi(G[L_i]) \le2^{k-2} χ ( G [ L i ]) ≤ 2 k − 2 for every layer L i L_i L i , which implies the result.
This holds for L 0 L_0 L 0 since k ≥ 2 k \ge2 k ≥ 2 . For a layer L i L_i L i with i ≥ 1 i \ge1 i ≥ 1 , take a red-dominating K s K_s K s -model in G [ L i ] G[L_i] G [ L i ] , with s : = had r d ( G [ L i ] ) s := \operatorname{had}_{\mathrm{rd}}(G[L_i]) s := had rd ( G [ L i ]) . Let T T T be a breadth-first search tree from r r r restricted to L 0 ∪ ⋯ ∪ L i − 1 L_0\cup\cdots\cup L_{i-1} L 0 ∪ ⋯ ∪ L i − 1 , which is a subtree of G G G . Colour each vertex of T T T at distance d d d from r r r with red if d ≡ i − 1 ( m o d 2 ) d\equiv i-1\pmod{2} d ≡ i − 1 ( mod 2 ) and blue otherwise. Every edge of T T T is bichromatic, and every vertex of L i − 1 L_{i-1} L i − 1 is red. Since every vertex of L i L_i L i has a neighbour in L i − 1 L_{i-1} L i − 1 , prepending T T T to the red-dominating K s K_s K s -model gives a red-dominating K s + 1 K_{s+1} K s + 1 -model in G G G . Thus s + 1 ≤ had r d ( G ) ≤ k s+1\le\operatorname{had}_{\mathrm{rd}}(G)\le k s + 1 ≤ had rd ( G ) ≤ k . This implies that s = had r d ( G [ L i ] ) ≤ k − 1 s=\operatorname{had}_{\mathrm{rd}}(G[L_i])\le k-1 s = had rd ( G [ L i ]) ≤ k − 1 . By induction, χ ( G [ L i ] ) ≤ 2 k − 2 \chi(G[L_i])\le2^{k-2} χ ( G [ L i ]) ≤ 2 k − 2 , completing the proof.
Strongly odd dominating models
In a strongly odd dominating model, every vertex of a later branch set must have a neighbour of its own colour in each earlier branch set. The following strengthening of Lemma 19 ensures the stronger property that every vertex outside the constructed set has neighbours of both colours in it.
Lemma 23. Every non-empty connected graph G G G has a set D ⊆ V ( G ) D\subseteq V(G) D ⊆ V ( G ) , a colouring c : D → { red , blue } c:D\to\{\text{red},\text{blue}\} c : D → { red , blue } , a spanning tree F F F of G [ D ] G[D] G [ D ] whose edges are bichromatic, and an independent set Y ⊆ D Y\subseteq D Y ⊆ D with ∣ Y ∣ ≥ ( ∣ D ∣ + 1 ) / 3 |Y|\ge(|D|+1)/3 ∣ Y ∣ ≥ ( ∣ D ∣ + 1 ) /3 , such that every vertex of V ( G ) ∖ D V(G)\setminus D V ( G ) ∖ D has a neighbour of colour red and a neighbour of colour blue in D D D .
Proof. Let ( D 0 , I , F 0 ) (D_0, I, F_0) ( D 0 , I , F 0 ) be given by Lemma 19 . Colour I I I with colour red and D 0 ∖ I D_0 \setminus I D 0 ∖ I with colour blue. Let W W W be the set of vertices in V ( G ) ∖ D 0 V(G) \setminus D_0 V ( G ) ∖ D 0 with no neighbour in D 0 ∖ I D_0 \setminus I D 0 ∖ I , and let J J J be a maximal independent set of G [ W ] G[W] G [ W ] , where J = ∅ J = \varnothing J = ∅ if W = ∅ W = \varnothing W = ∅ . By Lemma 19 (2), every w ∈ J w \in J w ∈ J has a neighbour x w ∈ I x_w \in I x w ∈ I . Let D : = D 0 ∪ J D := D_0 \cup J D := D 0 ∪ J , colour J J J with colour blue, and let F : = F 0 + { x w w : w ∈ J } F := F_0 + \{x_w w : w \in J\} F := F 0 + { x w w : w ∈ J } . Then F F F is a spanning tree of G [ D ] G[D] G [ D ] whose edges are bichromatic.
Let v ∈ V ( G ) ∖ D v \in V(G) \setminus D v ∈ V ( G ) ∖ D . By Lemma 19 (2), v v v has a neighbour in I I I , which has colour red. If v ∉ W v \notin W v ∈ / W , then v v v has a neighbour in D 0 ∖ I D_0 \setminus I D 0 ∖ I , which has colour blue. If v ∈ W ∖ J v \in W \setminus J v ∈ W ∖ J , then v v v has a neighbour in J J J by the maximality of J J J , and this neighbour has colour blue.
Finally, ∣ D ∣ = ∣ D 0 ∣ + ∣ J ∣ ≤ 2 ∣ I ∣ + ∣ J ∣ − 1 ≤ 3 max { ∣ I ∣ , ∣ J ∣ } − 1 |D| = |D_0| + |J| \le2|I| + |J| - 1 \le3\max\{|I|, |J|\} - 1 ∣ D ∣ = ∣ D 0 ∣ + ∣ J ∣ ≤ 2∣ I ∣ + ∣ J ∣ − 1 ≤ 3 max { ∣ I ∣ , ∣ J ∣ } − 1 . Let Y Y Y be the larger of I I I and J J J . Then Y Y Y is independent and ∣ Y ∣ ≥ ( ∣ D ∣ + 1 ) / 3 |Y| \ge(|D| + 1)/3 ∣ Y ∣ ≥ ( ∣ D ∣ + 1 ) /3 .
Using Lemma 23 in place of Lemma 19 gives the following analogue of Theorem 20 .
Theorem 24. For every graph G G G there is a rooted forest T T T , a partition { P x : x ∈ V ( T ) } \{P_x : x \in V(T)\} { P x : x ∈ V ( T )} of V ( G ) V(G) V ( G ) into non-empty parts, and a colouring c : V ( G ) → { red , blue } c : V(G) \to\{\text{red}, \text{blue}\} c : V ( G ) → { red , blue } , together with, for each x ∈ V ( T ) x \in V(T) x ∈ V ( T ) , a spanning tree F x F_x F x of G [ P x ] G[P_x] G [ P x ] whose edges are bichromatic and an independent set Y x ⊆ P x Y_x \subseteq P_x Y x ⊆ P x with ∣ Y x ∣ ≥ ( ∣ P x ∣ + 1 ) / 3 |Y_x| \ge(|P_x| + 1)/3 ∣ Y x ∣ ≥ ( ∣ P x ∣ + 1 ) /3 , such that:
(1) if x , y ∈ V ( T ) x, y \in V(T) x , y ∈ V ( T ) are incomparable, then there is no edge of G G G between P x P_x P x and P y P_y P y ;
(2) if x x x is a proper ancestor of y y y , then every vertex of P y P_y P y has a neighbour of colour red and a neighbour of colour blue in P x P_x P x .
Proof. The proof is the same as that of Theorem 20 , with Lemma 23 in place of Lemma 19 . For connected G G G , the root part is the set D D D given by Lemma 23 , with its colouring, tree F F F and independent set Y Y Y , and the colouring of V ( G ) ∖ D V(G) \setminus D V ( G ) ∖ D is given by induction.
We now prove Theorem 7 , following the proof of Theorem 18 with Theorem 24 in place of Theorem 20 .
Proof of Theorem 7 . Apply Theorem 24 to G G G , and let h h h be the maximum number of vertices on a path in T T T that starts at a root. Since G G G has at least one vertex, h ≥ 1 h \ge1 h ≥ 1 . If x 1 , … , x h x_1, \ldots, x_h x 1 , … , x h is such a path with x 1 x_1 x 1 a root, then ( ( F x 1 , … , F x h ) , c ) ((F_{x_1}, \ldots, F_{x_h}), c) (( F x 1 , … , F x h ) , c ) is a strongly odd dominating K h K_h K h -model, since for i < j i < j i < j each vertex v ∈ P x j v \in P_{x_j} v ∈ P x j has a neighbour of colour c ( v ) c(v) c ( v ) in P x i P_{x_i} P x i by Theorem 24 (2). Thus h ≤ had s o d ( G ) h \le\operatorname{had}_{\mathrm{sod}}(G) h ≤ had sod ( G ) . Let X : = ⋃ x ∈ V ( T ) Y x X := \bigcup_{x \in V(T)} Y_x X := ⋃ x ∈ V ( T ) Y x . Then
∣ X ∣ = ∑ x ∈ V ( T ) ∣ Y x ∣ ≥ ∑ x ∈ V ( T ) ∣ P x ∣ + 1 3 = n + ∣ V ( T ) ∣ 3 ≥ n + h 3 . |X| = \sum_{x \in V(T)} |Y_x| \ge\sum_{x \in V(T)} \frac{|P_x| + 1}{3} = \frac{n + |V(T)|}{3} \ge\frac{n + h}{3}. ∣ X ∣ = x ∈ V ( T ) ∑ ∣ Y x ∣ ≥ x ∈ V ( T ) ∑ 3 ∣ P x ∣ + 1 = 3 n + ∣ V ( T ) ∣ ≥ 3 n + h .
As in the proof of Theorem 18 , colouring each vertex of Y x Y_x Y x by the depth of x x x in T T T shows that G [ X ] G[X] G [ X ] is h h h -colourable. Some colour class is an independent set of size at least
n + h 3 h = n 3 h + 1 3 ≥ n 3 had s o d ( G ) + 1 3 = n + had s o d ( G ) 3 had s o d ( G ) . \frac{n + h}{3h} = \frac{n}{3h} + \frac{1}{3} \ge\frac{n}{3\operatorname{had}_{\mathrm{sod}}(G)} + \frac{1}{3} = \frac{n + \operatorname{had}_{\mathrm{sod}}(G)}{3\operatorname{had}_{\mathrm{sod}}(G)}. 3 h n + h = 3 h n + 3 1 ≥ 3 had sod ( G ) n + 3 1 = 3 had sod ( G ) n + had sod ( G ) .
Thus α ( G ) ≥ ( n + had s o d ( G ) ) / ( 3 had s o d ( G ) ) \alpha(G) \ge(n+\operatorname{had}_{\mathrm{sod}}(G))/(3\operatorname{had}_{\mathrm{sod}}(G)) α ( G ) ≥ ( n + had sod ( G )) / ( 3 had sod ( G )) , which rearranges to had s o d ( G ) ≥ n / ( 3 α ( G ) − 1 ) \operatorname{had}_{\mathrm{sod}}(G) \ge n/(3\alpha(G)-1) had sod ( G ) ≥ n / ( 3 α ( G ) − 1 ) .
We now bound χ ( G ) \chi(G) χ ( G ) in terms of had s o d ( G ) \operatorname{had}_{\mathrm{sod}}(G) had sod ( G ) . The proof of Proposition 22 does not work here, since in a breadth-first search all the neighbours of a vertex of L i L_i L i in L 0 ∪ ⋯ ∪ L i − 1 L_0 \cup\cdots\cup L_{i-1} L 0 ∪ ⋯ ∪ L i − 1 lie in L i − 1 L_{i-1} L i − 1 , and so receive the same colour in that proof. The following lemma deals with this issue.
Lemma 25. Let W ⊆ V ( G ) W \subseteq V(G) W ⊆ V ( G ) be a non-empty set such that G [ W ] G[W] G [ W ] is connected, let F F F be a spanning tree of G [ W ] G[W] G [ W ] , let c : W → { red , blue } c: W \to\{\text{red}, \text{blue}\} c : W → { red , blue } be a colouring such that every edge of F F F is bichromatic, and let K ⊆ V ( G ) ∖ W K \subseteq V(G) \setminus W K ⊆ V ( G ) ∖ W be a set such that every vertex of K K K has a neighbour in W W W . Then there is a set Z ⊆ K Z \subseteq K Z ⊆ K , an extension of c c c to W ∪ Z W \cup Z W ∪ Z , and a spanning tree F ′ F' F ′ of G [ W ∪ Z ] G[W \cup Z] G [ W ∪ Z ] containing F F F , such that:
(1) every edge of F ′ F' F ′ is bichromatic;
(2) every edge of G [ Z ] G[Z] G [ Z ] is bichromatic, so χ ( G [ Z ] ) ≤ 2 \chi(G[Z]) \le2 χ ( G [ Z ]) ≤ 2 ;
(3) every vertex of K ∖ Z K \setminus Z K ∖ Z has a neighbour of colour red and a neighbour of colour blue in W ∪ Z W \cup Z W ∪ Z .
Proof. Start with Y : = W Y := W Y := W , Z : = ∅ Z := \varnothing Z := ∅ and F ′ : = F F' := F F ′ := F . While some vertex v ∈ K ∖ Z v \in K \setminus Z v ∈ K ∖ Z has neighbours in Y Y Y of only one colour γ \gamma γ (it has at least one neighbour in Y Y Y , since it has one in W W W ), add v v v to Y Y Y and to Z Z Z , colour v v v with the colour in { red , blue } ∖ { γ } \{\text{red}, \text{blue}\} \setminus\{\gamma\} { red , blue } ∖ { γ } , and add to F ′ F' F ′ an edge from v v v to a neighbour of v v v of colour γ \gamma γ . This process terminates, and then (1) and (3) hold. For (2), let z z ′ zz' z z ′ be an edge of G [ Z ] G[Z] G [ Z ] , where z z z was added before z ′ z' z ′ . When z ′ z' z ′ was added, z z z was in Y Y Y and adjacent to z ′ z' z ′ , so the only colour that z ′ z' z ′ saw in Y Y Y was the colour of z z z , and z ′ z' z ′ received the other colour.
With Lemma 25 , the layering argument gives the following analogue of Proposition 22.
Proposition 26. Every graph G G G with at least one vertex satisfies χ ( G ) ≤ 3 ⋅ 2 had s o d ( G ) − 5 \chi(G) \le3 \cdot2^{\operatorname{had}_{\mathrm{sod}}(G)} - 5 χ ( G ) ≤ 3 ⋅ 2 had sod ( G ) − 5 .
Proof. We proceed by induction on k ≥ 1 k \ge1 k ≥ 1 to show that every non-empty graph G G G with had s o d ( G ) ≤ k \operatorname{had}_{\mathrm{sod}}(G) \le k had sod ( G ) ≤ k satisfies χ ( G ) ≤ 3 ⋅ 2 k − 5 \chi(G) \le3 \cdot2^k - 5 χ ( G ) ≤ 3 ⋅ 2 k − 5 . If k = 1 k = 1 k = 1 , then ∣ E ( G ) ∣ = 0 |E(G)| = 0 ∣ E ( G ) ∣ = 0 , so χ ( G ) = 1 \chi(G) = 1 χ ( G ) = 1 .
Now let k ≥ 2 k \ge2 k ≥ 2 . We may assume that G G G is connected. Fix a vertex r r r , let L 0 : = { r } L_0 := \{r\} L 0 := { r } , and for i ≥ 1 i \ge1 i ≥ 1 , let L i L_i L i be the set of vertices at distance exactly i i i from r r r . Every edge of G G G has both ends in one L i L_i L i or ends in L i L_i L i and L i + 1 L_{i+1} L i + 1 for some i i i . Consequently the sets L i L_i L i with i i i even are pairwise non-adjacent, as are the sets L i L_i L i with i i i odd, and thus χ ( G ) ≤ 2 max i χ ( G [ L i ] ) \chi(G) \le2 \max_i \chi(G[L_i]) χ ( G ) ≤ 2 max i χ ( G [ L i ]) . We now show that χ ( G [ L i ] ) ≤ 3 ⋅ 2 k − 1 − 3 \chi(G[L_i]) \le3 \cdot2^{k-1} - 3 χ ( G [ L i ]) ≤ 3 ⋅ 2 k − 1 − 3 for every layer L i L_i L i , which implies the result. This holds for L 0 L_0 L 0 since k ≥ 2 k \ge2 k ≥ 2 .
For a layer L i L_i L i with i ≥ 1 i \ge1 i ≥ 1 , let W : = L 0 ∪ ⋯ ∪ L i − 1 W := L_0 \cup\cdots\cup L_{i-1} W := L 0 ∪ ⋯ ∪ L i − 1 , and let F F F be a breadth-first search spanning tree from r r r restricted to W W W . Let c c c be the colouring of W W W in which each vertex at distance d d d from r r r is red if d ≡ i − 1 ( m o d 2 ) d \equiv i - 1 \pmod2 d ≡ i − 1 ( mod 2 ) and blue otherwise. Each edge of F F F is bichromatic, and each vertex of L i L_i L i has a neighbour in L i − 1 ⊆ W L_{i-1} \subseteq W L i − 1 ⊆ W . Apply Lemma 25 to W W W , F F F , c c c and L i L_i L i to obtain Z Z Z , the extension of c c c (also denoted c c c ) and a spanning tree F ′ F' F ′ . Let H : = G [ L i ∖ Z ] H := G[L_i \setminus Z] H := G [ L i ∖ Z ] . By Lemma 25 (2), χ ( G [ L i ] ) ≤ χ ( H ) + 2 \chi(G[L_i]) \le\chi(H) + 2 χ ( G [ L i ]) ≤ χ ( H ) + 2 . If H H H is empty, then χ ( G [ L i ] ) ≤ 2 \chi(G[L_i]) \le2 χ ( G [ L i ]) ≤ 2 , as required. Otherwise, take a strongly odd dominating K s K_s K s -model ( ( T 1 , … , T s ) , c ′ ) ((T_1, \ldots, T_s), c') (( T 1 , … , T s ) , c ′ ) in H H H , with s : = had s o d ( H ) s := \operatorname{had}_{\mathrm{sod}}(H) s := had sod ( H ) . By Lemma 25 (3), for each j ∈ { 1 , … , s } j \in\{1, \ldots, s\} j ∈ { 1 , … , s } , every vertex of T j T_j T j has neighbours of both colours in F ′ F' F ′ , and in particular a neighbour of its own colour under c ′ c' c ′ . Hence ( ( F ′ , T 1 , … , T s ) , c ∪ c ′ ) ((F', T_1, \ldots, T_s), c \cup c') (( F ′ , T 1 , … , T s ) , c ∪ c ′ ) is a strongly odd dominating K s + 1 K_{s+1} K s + 1 -model in G G G . Thus s + 1 ≤ had s o d ( G ) ≤ k s + 1 \le\operatorname{had}_{\mathrm{sod}}(G) \le k s + 1 ≤ had sod ( G ) ≤ k , so had s o d ( H ) ≤ k − 1 \operatorname{had}_{\mathrm{sod}}(H) \le k - 1 had sod ( H ) ≤ k − 1 . By induction, χ ( H ) ≤ 3 ⋅ 2 k − 1 − 5 \chi(H) \le3 \cdot2^{k-1} - 5 χ ( H ) ≤ 3 ⋅ 2 k − 1 − 5 . Consequently, χ ( G [ L i ] ) ≤ 3 ⋅ 2 k − 1 − 3 \chi(G[L_i]) \le3 \cdot2^{k-1} - 3 χ ( G [ L i ]) ≤ 3 ⋅ 2 k − 1 − 3 , completing the proof.
Open Problems
We finish with some open problems.
The best known upper bound is χ ( G ) ∈ O ( had d ( G ) ( log had d ( G ) ) 2 ) \chi(G) \in O(\operatorname{had}_{d}(G)(\log\operatorname{had}_{d}(G))^{2}) χ ( G ) ∈ O ( had d ( G ) ( log had d ( G ) ) 2 ) for every graph G G G with had d ( G ) ≥ 2 \operatorname{had}_{d}(G) \ge2 had d ( G ) ≥ 2 , by the result of Girão et al. [25 ] mentioned above. Is there a constant C C C such that every graph G G G satisfies χ ( G ) ≤ C had d ( G ) \chi(G) \le C\operatorname{had}_{d}(G) χ ( G ) ≤ C had d ( G ) ? Illingworth and Wood [29 ] showed that there are graphs with no dominating K t K_t K t -model and with average degree ( 1 − o ( 1 ) ) t log t (1-o(1))t\log t ( 1 − o ( 1 )) t log t , so a bound on the degeneracy does not give a linear bound on the chromatic number.
Every non-empty graph G G G satisfies χ ( G ) ≤ 2 had o d ( G ) − 1 \chi(G) \le2^{\operatorname{had}_{\mathrm{od}}(G)-1} χ ( G ) ≤ 2 had od ( G ) − 1 (Proposition 22, which adapts Wagner’s layering argument [63 ] ) and χ ( G ) ≤ 3 ⋅ 2 had s o d ( G ) − 5 \chi(G) \le3 \cdot2^{\operatorname{had}_{\mathrm{sod}}(G)} - 5 χ ( G ) ≤ 3 ⋅ 2 had sod ( G ) − 5 (Proposition 26). Is χ ( G ) \chi(G) χ ( G ) bounded above by a polynomial function of had o d ( G ) \operatorname{had}_{\mathrm{od}}(G) had od ( G ) ? The same question applies to had s o d ( G ) \operatorname{had}_{\mathrm{sod}}(G) had sod ( G ) . Bipartite graphs G G G satisfy had o ( G ) ≤ 2 \operatorname{had}_{\mathrm{o}}(G) \le2 had o ( G ) ≤ 2 and can have arbitrarily large minimum degree, so the degeneracy of G G G is not bounded by any function of had o d ( G ) \operatorname{had}_{\mathrm{od}}(G) had od ( G ) or had s o d ( G ) \operatorname{had}_{\mathrm{sod}}(G) had sod ( G ) . Thus such a result cannot be proved by bounding the degeneracy.
What are the constants ρ \rho ρ and ρ d \rho_d ρ d ?
Use of AI. The authors discovered all the proofs in this paper. Claude Opus 5.5 was used to help write the paper, and GPT-6.1 was used for proof-reading.
Proofs of Lemmas 12 and 16
The proof of Lemma 12 extends a deep result of Chudnovsky and Seymour [14 1.3] to odd dominating models.
A seagull is an induced three-vertex path. A five-wheel consists of a 5-cycle and one additional vertex adjacent to every vertex of the cycle. For disjoint sets X X X , Y ⊆ V ( G ) Y \subseteq V(G) Y ⊆ V ( G ) , we say that X X X is complete to Y Y Y if every vertex of X X X is adjacent to every vertex of Y Y Y , and anticomplete to Y Y Y if there are no edges between X X X and Y Y Y . For a non-empty clique C C C of a graph G G G , let A C A_C A C , B C B_C B C , and D C D_C D C denote the sets of vertices in V ( G ) ∖ C V(G) \setminus C V ( G ) ∖ C that are complete to C C C , anticomplete to C C C , and have both a neighbour and a non-neighbour in C C C , respectively. We call ( A C , B C , C , D C ) (A_C, B_C, C, D_C) ( A C , B C , C , D C ) the associated partition of a clique C C C . Define the capacity of C C C by
cap G ( C ) : = ∣ D C ∣ + ∣ A C ∣ + ∣ B C ∣ 2 . \operatorname{cap}_G(C) := |D_C| + \frac{|A_C| + |B_C|}{2}. cap G ( C ) := ∣ D C ∣ + 2 ∣ A C ∣ + ∣ B C ∣ .
To prove Lemma 12 , the following result of Chudnovsky and Seymour [14 ] is essential.
Theorem 27 (Chudnovsky and Seymour [14 1.6] ). Let G G G be a non-empty graph with α ( G ) ≤ 2 \alpha(G) \leq2 α ( G ) ≤ 2 , and let k ≥ 0 k \geq0 k ≥ 0 be an integer, such that if k = 2 k = 2 k = 2 then G G G is not a five-wheel. Then G G G has k k k pairwise vertex-disjoint seagulls if and only if
We now prove Lemma 12 using Theorem 27 .
Lemma 12. Every n n n -vertex graph G G G with n ≥ 1 n \ge1 n ≥ 1 , α ( G ) ≤ 2 \alpha(G) \le2 α ( G ) ≤ 2 and 2 ω ( G ) ≥ ⌈ n / 2 ⌉ + 1 2\omega(G) \ge\lceil n/2\rceil+ 1 2 ω ( G ) ≥ ⌈ n /2 ⌉ + 1 has had o d ( G ) ≥ ⌈ n / 2 ⌉ \operatorname{had}_{\mathrm{od}}(G) \ge\lceil n/2\rceil had od ( G ) ≥ ⌈ n /2 ⌉ .
Proof. Let C C C be a clique of maximum size in G G G , and we may suppose that ∣ C ∣ ≤ ⌈ n / 2 ⌉ − 1 |C| \le\lceil n/2\rceil- 1 ∣ C ∣ ≤ ⌈ n /2 ⌉ − 1 . Let H : = G − C H := G-C H := G − C . Let k : = ⌈ n / 2 ⌉ − ∣ C ∣ ≥ 1 k := \lceil n/2\rceil- |C| \ge1 k := ⌈ n /2 ⌉ − ∣ C ∣ ≥ 1 .
Claim. H H H satisfies the hypotheses of Theorem 27 and thus has k k k pairwise vertex-disjoint seagulls.
First, we check that ∣ V ( H ) ∣ ≥ 3 k |V(H)| \ge3k ∣ V ( H ) ∣ ≥ 3 k . By hypothesis, 2 ∣ C ∣ ≥ ⌈ n / 2 ⌉ + 1 2|C| \ge\lceil n/2\rceil+ 1 2∣ C ∣ ≥ ⌈ n /2 ⌉ + 1 , and 2 ⌈ n / 2 ⌉ ≤ n + 1 2\lceil n/2\rceil\le n + 1 2 ⌈ n /2 ⌉ ≤ n + 1 . Hence
∣ V ( H ) ∣ = n − ∣ C ∣ = 3 ( ⌈ n / 2 ⌉ − ∣ C ∣ ) + n + 2 ∣ C ∣ − 3 ⌈ n / 2 ⌉ = 3 k + n + 2 ∣ C ∣ − 3 ⌈ n / 2 ⌉ ≥ 3 k + n + ( ⌈ n / 2 ⌉ + 1 ) − 3 ⌈ n / 2 ⌉ = 3 k + n + 1 − 2 ⌈ n / 2 ⌉ ≥ 3 k . \begin{aligned}
|V(H)| &= n-|C| \\
&= 3(\lceil n/2\rceil-|C|)+n+2|C|-3\lceil n/2\rceil\\
&= 3k+n+2|C|-3\lceil n/2\rceil\\
&\ge3k+n+(\lceil n/2\rceil+1)-3\lceil n/2\rceil\\
&= 3k+n+1-2\lceil n/2\rceil\ge3k.
\end{aligned} ∣ V ( H ) ∣ = n − ∣ C ∣ = 3 (⌈ n /2 ⌉ − ∣ C ∣ ) + n + 2∣ C ∣ − 3 ⌈ n /2 ⌉ = 3 k + n + 2∣ C ∣ − 3 ⌈ n /2 ⌉ ≥ 3 k + n + (⌈ n /2 ⌉ + 1 ) − 3 ⌈ n /2 ⌉ = 3 k + n + 1 − 2 ⌈ n /2 ⌉ ≥ 3 k .
Next, we show that H H H is k k k -connected. Suppose for contradiction that there is a set X ⊆ V ( H ) X \subseteq V(H) X ⊆ V ( H ) with ∣ X ∣ ≤ k − 1 |X| \le k-1 ∣ X ∣ ≤ k − 1 such that H − X H-X H − X is disconnected. As α ( G ) ≤ 2 \alpha(G) \le2 α ( G ) ≤ 2 , the graph H − X H-X H − X consists of exactly two components, each of which is a clique. Let their vertex sets be A A A and B B B .
Now, each vertex v ∈ C v \in C v ∈ C is complete to either A A A or B B B (otherwise taking a vertex a ∈ A a \in A a ∈ A and b ∈ B b \in B b ∈ B not adjacent to v v v gives an independent set of size 3 3 3 ). Thus we can partition C C C into sets C A C_A C A and C B C_B C B such that C A C_A C A is complete to A A A and C B C_B C B is complete to B B B . Both A ∪ C A A \cup C_A A ∪ C A and B ∪ C B B \cup C_B B ∪ C B are cliques, so the maximality of ∣ C ∣ |C| ∣ C ∣ implies that
n − ∣ X ∣ = ∣ A ∪ C A ∣ + ∣ B ∪ C B ∣ ≤ 2 ∣ C ∣ . n-|X|=|A\cup C_A|+|B\cup C_B|\le2|C|. n − ∣ X ∣ = ∣ A ∪ C A ∣ + ∣ B ∪ C B ∣ ≤ 2∣ C ∣.
On the other hand, since n ≥ 2 ⌈ n / 2 ⌉ − 1 n \ge2\lceil n/2\rceil-1 n ≥ 2 ⌈ n /2 ⌉ − 1 ,
n − ∣ X ∣ ≥ n − k + 1 = n − ⌈ n / 2 ⌉ + ∣ C ∣ + 1 ≥ ⌈ n / 2 ⌉ + ∣ C ∣ > 2 ∣ C ∣ , n-|X|\ge n-k+1=n-\lceil n/2\rceil+|C|+1\ge\lceil n/2\rceil+|C|>2|C|, n − ∣ X ∣ ≥ n − k + 1 = n − ⌈ n /2 ⌉ + ∣ C ∣ + 1 ≥ ⌈ n /2 ⌉ + ∣ C ∣ > 2∣ C ∣ ,
a contradiction.
Next, we show that every non-empty clique Q Q Q of H H H satisfies cap H ( Q ) ≥ k \operatorname{cap}_H(Q) \ge k cap H ( Q ) ≥ k . Suppose that a non-empty clique Q Q Q of H H H satisfies cap H ( Q ) < k \operatorname{cap}_H(Q) < k cap H ( Q ) < k . Let ( Q A , Q B , Q , Q D ) (Q_A,Q_B,Q,Q_D) ( Q A , Q B , Q , Q D ) be its associated partition in H H H . Then since ∣ Q A ∣ |Q_A| ∣ Q A ∣ , ∣ Q B ∣ |Q_B| ∣ Q B ∣ and ∣ Q D ∣ |Q_D| ∣ Q D ∣ are integers,
cap H ( Q ) = ∣ Q D ∣ + ∣ Q A ∣ + ∣ Q B ∣ 2 ≤ k − 1 2 . \operatorname{cap}_H(Q)=|Q_D|+\frac{|Q_A|+|Q_B|}{2}\le k-\frac{1}{2}. cap H ( Q ) = ∣ Q D ∣ + 2 ∣ Q A ∣ + ∣ Q B ∣ ≤ k − 2 1 .
Therefore,
∣ Q A ∣ + ∣ Q B ∣ + 2 ∣ Q D ∣ ≤ 2 k − 1. |Q_A|+|Q_B|+2|Q_D|\le2k-1. ∣ Q A ∣ + ∣ Q B ∣ + 2∣ Q D ∣ ≤ 2 k − 1.
Since 2 ⌈ n / 2 ⌉ − 1 ≤ n 2\lceil n/2\rceil-1\le n 2 ⌈ n /2 ⌉ − 1 ≤ n , we have
2 ⌈ n / 2 ⌉ − 1 + ∣ Q D ∣ ≤ n + ∣ Q D ∣ = ∣ Q A ∣ + ∣ Q B ∣ + ∣ Q ∣ + 2 ∣ Q D ∣ + ∣ C ∣ ≤ 2 k − 1 + ∣ Q ∣ + ∣ C ∣ ≤ 2 k − 1 + 2 ∣ C ∣ = 2 ⌈ n / 2 ⌉ − 1 , \begin{aligned}
2\lceil n/2\rceil-1+|Q_D| &\le n+|Q_D| \\
&=|Q_A|+|Q_B|+|Q|+2|Q_D|+|C| \\
&\le2k-1+|Q|+|C| \\
&\le2k-1+2|C|=2\lceil n/2\rceil-1,
\end{aligned} 2 ⌈ n /2 ⌉ − 1 + ∣ Q D ∣ ≤ n + ∣ Q D ∣ = ∣ Q A ∣ + ∣ Q B ∣ + ∣ Q ∣ + 2∣ Q D ∣ + ∣ C ∣ ≤ 2 k − 1 + ∣ Q ∣ + ∣ C ∣ ≤ 2 k − 1 + 2∣ C ∣ = 2 ⌈ n /2 ⌉ − 1 ,
where the last inequality follows from k = ⌈ n / 2 ⌉ − ∣ C ∣ k = \lceil n/2\rceil- |C| k = ⌈ n /2 ⌉ − ∣ C ∣ . Hence every inequality is an equality. In particular, Q D = ∅ Q_D = \varnothing Q D = ∅ and ∣ Q ∣ = ∣ C ∣ |Q| = |C| ∣ Q ∣ = ∣ C ∣ . Thus Q Q Q is a maximum clique of G G G and Q A = ∅ Q_A = \varnothing Q A = ∅ . Thus V ( H ‾ ) = Q ∪ Q B V(\overline{H}) = Q \cup Q_B V ( H ) = Q ∪ Q B . Since H H H is k k k -connected and k ≥ 1 k \ge1 k ≥ 1 , H H H is connected. In particular, Q B = ∅ Q_B = \varnothing Q B = ∅ . Consequently, V ( H ‾ ) = Q V(\overline{H}) = Q V ( H ) = Q and V ( G ) = C ∪ Q V(G) = C \cup Q V ( G ) = C ∪ Q . But ∣ Q ∣ = ∣ C ∣ < n / 2 |Q| = |C| < n/2 ∣ Q ∣ = ∣ C ∣ < n /2 , a contradiction. Thus every non-empty clique Q Q Q of H H H satisfies cap H ( Q ) ≥ k \operatorname{cap}_{H}(Q) \ge k cap H ( Q ) ≥ k .
Next, we show that H ‾ \overline{H} H has a matching of cardinality k k k . Let M M M be a maximal matching in H ‾ \overline{H} H , and let U U U be the set of vertices of H ‾ \overline{H} H not covered by M M M . By the maximality of M M M , the set U U U is independent in H ‾ \overline{H} H , and hence is a clique in H H H . Thus, ∣ U ∣ ≤ ∣ C ∣ |U| \le|C| ∣ U ∣ ≤ ∣ C ∣ . Therefore,
2 ∣ M ∣ = ∣ V ( H ) ∣ − ∣ U ∣ ≥ n − ∣ C ∣ − ∣ C ∣ = n − 2 ∣ C ∣ ≥ 2 ⌈ n / 2 ⌉ − 1 − 2 ∣ C ∣ = 2 k − 1. \begin{aligned}
2|M| &= |V(H)| - |U| \\
&\ge n - |C| - |C| \\
&= n - 2|C| \\
&\ge2\lceil n/2\rceil- 1 - 2|C| = 2k - 1.
\end{aligned} 2∣ M ∣ = ∣ V ( H ) ∣ − ∣ U ∣ ≥ n − ∣ C ∣ − ∣ C ∣ = n − 2∣ C ∣ ≥ 2 ⌈ n /2 ⌉ − 1 − 2∣ C ∣ = 2 k − 1.
Since 2 ∣ M ∣ 2|M| 2∣ M ∣ is even, we have 2 ∣ M ∣ ≥ 2 k 2|M| \ge2k 2∣ M ∣ ≥ 2 k and hence ∣ M ∣ ≥ k |M| \ge k ∣ M ∣ ≥ k , as desired.
Finally, to apply Theorem 27 , we need to show that H H H is not isomorphic to the 5-wheel when k = 2 k = 2 k = 2 . Suppose that H H H is isomorphic to the 5-wheel. Then ∣ V ( H ) ∣ = 6 |V(H)| = 6 ∣ V ( H ) ∣ = 6 and H H H contains a clique of size 3. Since C C C is a maximum clique of G G G , we have ∣ C ∣ ≥ 3 |C| \ge3 ∣ C ∣ ≥ 3 . Thus n ≥ 9 n \ge9 n ≥ 9 . Since k = 2 k = 2 k = 2 , n = ∣ C ∣ + 6 = ⌈ n / 2 ⌉ − k + 6 = ⌈ n / 2 ⌉ + 4 n = |C| + 6 = \lceil n/2\rceil- k + 6 = \lceil n/2\rceil+ 4 n = ∣ C ∣ + 6 = ⌈ n /2 ⌉ − k + 6 = ⌈ n /2 ⌉ + 4 . We deduce that ⌊ n / 2 ⌋ = 4 \lfloor n/2\rfloor= 4 ⌊ n /2 ⌋ = 4 , and so n ∈ { 8 , 9 } n \in\{8,9\} n ∈ { 8 , 9 } . Consequently, n = 9 n = 9 n = 9 and ∣ C ∣ = 3 |C| = 3 ∣ C ∣ = 3 .
Let D D D be the induced 5-cycle in H H H . Since C C C is a maximum clique of G G G , ω ( G ) ≤ 3 \omega(G) \le3 ω ( G ) ≤ 3 . Therefore, for every edge u v uv uv of D D D , at most one vertex of C C C is adjacent to both u u u and v v v . Since ∣ E ( D ) ∣ = 5 |E(D)| = 5 ∣ E ( D ) ∣ = 5 and ∣ C ∣ = 3 |C| = 3 ∣ C ∣ = 3 , there is a vertex c ∈ C c \in C c ∈ C such that c c c is adjacent to both u u u and v v v for at most one edge u v ∈ E ( D ) uv \in E(D) uv ∈ E ( D ) . Thus c c c has at most three neighbours in D D D , and the three neighbours are not consecutive on D D D . Let x x x and y y y be non-adjacent vertices in D D D such that x x x and y y y are non-adjacent to c c c . But { x , y , c } \{x,y,c\} { x , y , c } is an independent set of size 3, a contradiction. Therefore, H H H is not a 5-wheel. By Theorem 27 , H H H contains k k k pairwise vertex-disjoint seagulls, completing the proof of the claim.
Let S 1 , … , S k S_1,\ldots,S_k S 1 , … , S k be the k k k vertex-disjoint seagulls of H H H supplied by the claim, and for each i ∈ { 1 , … , k } i \in\{1,\ldots,k\} i ∈ { 1 , … , k } , let S i = x i y i z i S_i = x_i y_i z_i S i = x i y i z i , where x i z i ∉ E ( H ) x_i z_i \notin E(H) x i z i ∈ / E ( H ) . Enumerate the vertices of C = { c 1 , … , c ∣ C ∣ } C = \{c_1,\ldots,c_{|C|}\} C = { c 1 , … , c ∣ C ∣ } , and consider the K k + ∣ C ∣ = K ⌈ n / 2 ⌉ K_{k+|C|} = K_{\lceil n/2\rceil} K k + ∣ C ∣ = K ⌈ n /2 ⌉ -model of G G G given by the branch sets
T : = ( S 1 , … , S k , { c 1 } , … , { c ∣ C ∣ } ) . \mathcal{T} := (S_1,\ldots,S_k,\{c_1\},\ldots,\{c_{|C|}\}). T := ( S 1 , … , S k , { c 1 } , … , { c ∣ C ∣ }) .
We claim that T \mathcal{T} T is an odd and dominating model. Since α ( G ) ≤ 2 \alpha(G) \le2 α ( G ) ≤ 2 and x i z i ∉ E ( G ) x_i z_i \notin E(G) x i z i ∈ / E ( G ) , every vertex v ∈ V ( G ) ∖ V ( S i ) v \in V(G) \setminus V(S_i) v ∈ V ( G ) ∖ V ( S i ) is adjacent to at least one of x i x_i x i and z i z_i z i ; otherwise, { v , x i , z i } \{v,x_i,z_i\} { v , x i , z i } is an independent set of size 3. Thus T \mathcal{T} T is a dominating model.
To see that T \mathcal{T} T is an odd model, for each seagull S i S_i S i , we colour x i x_i x i and z i z_i z i blue and y i y_i y i red. We colour each vertex of C C C blue. The endpoints of every edge within each branch set receive different colours. Every blue vertex outside S i S_i S i has a blue neighbour in { x i , z i } \{x_i,z_i\} { x i , z i } . Since C C C is a blue clique, every two branch sets are joined by a monochromatic edge. Hence T \mathcal{T} T is an odd model. This completes the proof. □
As mentioned, the proof of Lemma 16 is a straightforward modification of the proof in Plummer et al. [51 Theorem 3.3(a)] .
Lemma 16 (Plummer et al. [51 Theorem 3.3(a)] , modified). Every n n n -vertex graph G G G with n ≥ 1 n \ge1 n ≥ 1 and α ( G ) ≤ 2 \alpha(G) \le2 α ( G ) ≤ 2 satisfies hadod ( G ) ≥ ⌊ ( ω ( G ) + n ) / 3 ⌋ \operatorname{hadod}(G) \ge\lfloor(\omega(G)+n)/3\rfloor hadod ( G ) ≥ ⌊( ω ( G ) + n ) /3 ⌋ .
Proof. Let C C C be a maximum clique of G G G , and let S 1 , … , S s S_1,\ldots,S_s S 1 , … , S s be a maximal collection of s ≥ 0 s \ge0 s ≥ 0 pairwise vertex-disjoint seagulls in G − C G-C G − C . Let G ′ : = G − ⋃ i = 1 s V ( S i ) G' := G-\bigcup_{i=1}^{s}V(S_i) G ′ := G − ⋃ i = 1 s V ( S i ) and H : = G ′ − C H := G'-C H := G ′ − C . By the maximality of the collection, H H H contains no seagull. Thus every component of H H H is a clique, and since α ( G ) ≤ 2 \alpha(G) \le2 α ( G ) ≤ 2 , H H H has at most two components; let A A A and B B B be their vertex sets, where A A A or B B B may be empty.
Every vertex of C C C is complete to A A A or B B B , since otherwise there is an independent set of size 3. Hence we may partition C = C A ∪ C B C=C_A\cup C_B C = C A ∪ C B such that C A C_A C A is complete to A A A and C B C_B C B is complete to B B B . Since A ∪ C A A\cup C_A A ∪ C A and B ∪ C B B\cup C_B B ∪ C B are cliques, ∣ V ( G ′ ) ∣ = ∣ A ∪ C A ∣ + ∣ B ∪ C B ∣ ≤ 2 ∣ C ∣ |V(G')|=|A\cup C_A|+|B\cup C_B|\le2|C| ∣ V ( G ′ ) ∣ = ∣ A ∪ C A ∣ + ∣ B ∪ C B ∣ ≤ 2∣ C ∣ .
Since each seagull has three vertices, we have n − 3 s = ∣ V ( G ′ ) ∣ ≤ 2 ∣ C ∣ n-3s=|V(G')|\le2|C| n − 3 s = ∣ V ( G ′ ) ∣ ≤ 2∣ C ∣ . Therefore, n + ∣ C ∣ ≤ 3 s + 3 ∣ C ∣ = 3 ( s + ∣ C ∣ ) n+|C|\le3s+3|C|=3(s+|C|) n + ∣ C ∣ ≤ 3 s + 3∣ C ∣ = 3 ( s + ∣ C ∣ ) and consequently s + ∣ C ∣ ≥ ⌈ ( n + ∣ C ∣ ) / 3 ⌉ = ⌈ ( n + ω ( G ) ) / 3 ⌉ s+|C|\ge\lceil(n+|C|)/3\rceil=\lceil(n+\omega(G))/3\rceil s + ∣ C ∣ ≥ ⌈( n + ∣ C ∣ ) /3 ⌉ = ⌈( n + ω ( G )) /3 ⌉ .
For each i ∈ { 1 , … , s } i\in\{1,\ldots,s\} i ∈ { 1 , … , s } , write S i = x i y i z i S_i=x_iy_iz_i S i = x i y i z i , where x i z i ∉ E ( G ) x_iz_i\notin E(G) x i z i ∈ / E ( G ) , and enumerate C = { c 1 , … , c ∣ C ∣ } C=\{c_1,\ldots,c_{|C|}\} C = { c 1 , … , c ∣ C ∣ } . Consider the model
T : = ( S 1 , … , S s , { c 1 } , … , { c ∣ C ∣ } ) . \mathcal{T}:=(S_1,\ldots,S_s,\{c_1\},\ldots,\{c_{|C|}\}). T := ( S 1 , … , S s , { c 1 } , … , { c ∣ C ∣ }) .
We claim that T \mathcal{T} T is an odd and dominating model. Since α ( G ) ≤ 2 \alpha(G)\le2 α ( G ) ≤ 2 and x i z i ∉ E ( G ) x_iz_i\notin E(G) x i z i ∈ / E ( G ) , every vertex v ∈ V ( G ) ∖ V ( S i ) v\in V(G)\setminus V(S_i) v ∈ V ( G ) ∖ V ( S i ) is adjacent to at least one of x i x_i x i and z i z_i z i ; otherwise, { v , x i , z i } \{v,x_i,z_i\} { v , x i , z i } is an independent set of size 3. Thus T \mathcal{T} T is a dominating model.
To see that T \mathcal{T} T is an odd model, for each seagull S i S_i S i , we colour x i x_i x i and z i z_i z i blue and y i y_i y i red. We colour each vertex of C C C blue. The endpoints of every edge within each branch set receive different colours. Every blue vertex outside S i S_i S i has a blue neighbour in { x i , z i } \{x_i,z_i\} { x i , z i } . Since C C C is a blue clique, every two branch sets are joined by a monochromatic edge. Hence T \mathcal{T} T is an odd model. Consequently, had o d ( G ) ≥ s + ∣ C ∣ ≥ ⌈ ( n + ω ( G ) ) / 3 ⌉ \operatorname{had}_{\mathrm{od}}(G)\ge s+|C|\ge\lceil(n+\omega(G))/3\rceil had od ( G ) ≥ s + ∣ C ∣ ≥ ⌈( n + ω ( G )) /3 ⌉ , as required. □ \square □