betaFeedback

WorksMathematics

Strong complete immersions in graphs with independence number two

Abstract

We prove that every graph GG with independence number at most two contains a strong immersion of Kχ(G)K_{χ(G)}. This strengthens Dahlke's theorem for weak immersions and establishes the Lescure–Meyniel conjecture for this class of graphs.

Introduction

All graphs considered in this paper are finite and simple. An immersion of a graph FF in a graph GG consists of an injection φ:V(F)→V(G)\varphi: V(F) \to V(G) and pairwise edge-disjoint paths PuvP_{uv} joining φ(u)\varphi(u) and φ(v)\varphi(v) for uv∈E(F)uv \in E(F). The vertices in φ(V(F))\varphi(V(F)) are its branch vertices. The immersion is strong if

V(Puv)∩φ(V(F))={φ(u),φ(v)}(uv∈E(F)).V(P_{uv}) \cap\varphi(V(F)) = \{\varphi(u), \varphi(v)\} \qquad(uv \in E(F)).

We write G⪰sFG \succeq_s F if GG contains a strong immersion of FF.

Lescure and Meyniel proposed the following conjecture.

Conjecture 1.1 (Lescure and Meyniel [14]). Every graph GG contains a strong immersion of Kχ(G)K_{\chi(G)}.

Abu-Khzam and Langston [1] proposed the corresponding conjecture for weak immersions. We prove Conjecture 1.1 for graphs with independence number at most two.

Theorem 1.2. If α(G)≤2\alpha(G) \le2, then G⪰sKχ(G)G \succeq_s K_{\chi(G)}.

For an nn-vertex graph with α(G)≤2\alpha(G) \le2, we have χ(G)≥⌈n/2⌉\chi(G) \ge\lceil n/2\rceil. Thus Theorem 1.2 also gives G⪰sK⌈n/2⌉G \succeq_s K_{\lceil n/2\rceil}. Vergara [17] proved G⪰sK⌈n/3⌉G \succeq_s K_{\lceil n/3\rceil}, and Gauthier, Le and Wollan [13] improved this to G⪰sK2⌊n/5⌋G \succeq_s K_{2\lfloor n/5\rfloor}. Botler et al. [5] proved G⪰sKχ(G)G \succeq_s K_{\chi(G)} when n≥11n \ge11 and Δ(G)<19n/29−1\Delta(G) < 19n/29 - 1, or when GG is covered by three cliques and Δ(G)<2n/3−1\Delta(G) < 2n/3 - 1. Deng, Chang and Liu [10] proved the gem-free case. Quiroz [15] proved that every FF-free graph GG with α(G)≤2\alpha(G) \le2 contains an immersion of Kχ(G)K_{\chi(G)}, provided ∣V(F)∣≤4|V(F)| \le4 and α(F)≤2\alpha(F) \le2.

Botler et al. [6] proved that every nn-vertex graph with independence number two contains every complete bipartite graph on ⌈n/2⌉\lceil n/2\rceil vertices as an immersion. Chen and Deng [8] gave a simpler proof. For α(G)≥3\alpha(G) \ge3, Bustamante et al. [7] obtained lower bounds on the order of a clique immersion in terms of ∣V(G)∣|V(G)| and α(G)\alpha(G).

Dahlke [9] proved that every graph with α(G)=2\alpha(G) = 2 contains a weak immersion of Kχ(G)K_{\chi(G)}. Theorem 1.2 strengthens this result to strong immersions. We use the bridge construction and the L/M/RL/M/R decomposition of [9]. By choosing the matching and the available paths suitably, we eliminate the RRRR pieces, whose paths may contain other branch vertices.

Bermúdez, Netto and Quiroz [2] proved that every nn-vertex graph with α(G)=2\alpha(G) = 2 contains K⌈n/2⌉K_{\lceil n/2\rceil} as an odd minor or as a totally odd strong immersion; the immersion alternative holds under additional hypotheses. Echeverría and McDonald [11] proved χ(G)≤⌈3(t−1)/2⌉\chi(G) \le\lceil3(t - 1)/2\rceil for graphs in this class with no strong odd KtK_t immersion. We impose no parity restriction on the immersion paths.

Our decomposition lemma uses Tan’s stable partitions and Fleiner’s predecessor-counting argument [16, 12]. § 4 proves an extension theorem, from which Theorem 1.2 follows by induction in § 5.

Notation and preliminaries

Write [t]={1,…,t}[t] = \{1,\ldots,t\}, xy∈Gxy \in G for xy∈E(G)xy \in E(G), dG(x,S)=∣NG(x)∩S∣d_G(x,S) = |N_G(x) \cap S|, and ν(G)\nu(G) for the matching number. For disjoint sets XX, YY, let EG(X,Y)E_G(X,Y) be the edges between them. The join of disjoint graphs G1G_1, G2G_2 is denoted by G1∨G2G_1 \vee G_2. A graph JJ is factor-critical if J−xJ - x has a perfect matching for every x∈V(J)x \in V(J). We allow the empty K0K_0 immersion.

Theorem 1.3 (Gallai–Edmonds; see [18 Theorem 5]). Let DD be the vertices missed by some maximum matching of JJ, and put

A=NJ(D)∖D,C=V(J)∖(D∪A).A = N_J(D) \setminus D,\qquad C = V(J) \setminus(D \cup A).

Then J[C]J[C] has a perfect matching, every component of J[D]J[D] is factor-critical, and EJ(C,D)=∅E_J(C,D) = \varnothing. Every maximum matching consists of a perfect matching on CC, near-perfect matchings in the components of J[D]J[D], and edges matching AA into distinct such components. In particular,

def⁡(J):=∣V(J)∣−2ν(J)=c(J[D])−∣A∣.\operatorname{def}(J) := |V(J)| - 2\nu(J) = c(J[D]) - |A|.

The following local-order form follows from the increasing and decreasing colour orders in the proof of Borodin, Kostochka and Woodall [4 Theorem 3, p. 189].

Theorem 1.4 (Borodin, Kostochka and Woodall). A simple bipartite graph BB admits strict orders on its incident edges such that

px(xy)+py(xy)≤max⁡{dB(x),dB(y)}−1(xy∈E(B)).p_x(xy) + p_y(xy) \le\max\{d_B(x),d_B(y)\} - 1 \qquad(xy \in E(B)).

where px(e)p_x(e) is the number of edges preceding ee at xx.

Since BB is simple, the seeing count in [4] equals the predecessor sum above.

Theorem 1.5 (Tan [16]). In a graph JJ with strict preferences on the neighbours of each vertex and self-partnership ranked last, there is a permutation π\pi such that xπ(x)∈E(J)x\pi(x) \in E(J) whenever π(x)≠x\pi(x) \ne x,

π(x)⪰xπ−1(x),\pi(x) \succeq_x \pi^{-1}(x),

and no edge xyxy satisfies both y≻xπ−1(x)y \succ_x \pi^{-1}(x) and x≻yπ−1(y)x \succ_y \pi^{-1}(y).

See also [3 Theorem 2]. Replacing an even cycle of π\pi by alternating pairs gives each vertex a partner at least as preferred as its predecessor. Thus we may assume that every cycle of π\pi has length one, two, or odd length at least three.

Local orders and decompositions

Let QQ be a simple graph and UU a finite colour set. For each i∈V(Q)i \in V(Q), put

U=Li⊔Mi⊔Ri,Ai=Li∪Mi,ri=∣Ai∣.U = L_i \sqcup M_i \sqcup R_i,\qquad A_i = L_i \cup M_i,\qquad r_i = |A_i|.

The following pieces, each assigned a colour w∈Uw \in U, are adapted from [9 Lemma 2.7]:

  • (i) an FF-edge ijij with owner ii and w∈Miw \in M_i, using the pair (i,w)(i,w);

  • (ii) an LLLL- or LRLR-edge ijij, using (i,w),(j,w)(i,w),(j,w);

  • (iii) an odd cycle with all vertices labelled LL, using (i,w)(i,w) at each vertex;

  • (iv) a path a−b−ca-b-c labelled L,L,RL,L,R, using (a,w),(b,w),(c,w)(a,w),(b,w),(c,w).

Here a vertex has label LL, MM or RR according to the set containing ww. A compatible decomposition partitions E(Q)E(Q) into these pieces and uses each pair (i,w)(i,w) at most once.

Lemma 2.1. If QQ has strict local edge orders satisfying

pi(ij)+pj(ij)<∣Ai∪Aj∣(ij∈E(Q)),(1)p_i(ij) + p_j(ij) < |A_i \cup A_j| \qquad(ij \in E(Q)), \tag*{(1)}

then QQ has a compatible decomposition.

Proof. Process the colours successively. For a colour ww, let QwQ_w consist of the remaining edges ijij with w∈Ai∪Ajw \in A_i \cup A_j. Apply Theorem 1.5 to QwQ_w, preferring earlier incident edges.

Assign each 2-cycle an FF-edge if it has an MM endpoint, and an LLLL- or LRLR-edge otherwise. Retain every all-LL odd cycle. Let x0x1⋯x2tx0x_0x_1\cdots x_{2t}x_0 be any other odd cycle, in successor order.

If x0x_0 has label MM, select the FF-edge x0x1x_0x_1 owned by x0x_0 and the pairs

x1x2, x3x4,…, x2t−1x2t.x_1x_2,\ x_3x_4,\ldots,\ x_{2t-1}x_{2t}.

If the cycle has no MM vertex, its RR vertices are independent. Hence, after relabelling, x0,x1,x2x_0,x_1,x_2 have labels L,L,RL,L,R. Select this path and the pairs x3x4,…,x2t−1x2tx_3x_4,\ldots,x_{2t-1}x_{2t}. Assign the pairs as above and delete all selected edges. The selected pieces use distinct pairs (i,w)(i,w).

Every unselected edge ee of QwQ_w has a selected edge preceding it at one endpoint. If one endpoint of ee is a singleton, then, since self-partnership is ranked last, Theorem 1.5 forces the other endpoint to be non-singleton, with both its predecessor and successor edges preceding ee. Otherwise, if ee is outside the permutation cycles, the same theorem gives an endpoint at which both cycle edges precede ee. In either case, at least one of these cycle edges is selected. Finally, if e=xixi+1e=x_ix_{i+1} is an omitted cycle edge, then xi+1xi+2x_{i+1}x_{i+2} is selected and precedes ee at xi+1x_{i+1} (subscripts modulo $2t+1). If ijij remains after all colours, each w∈Ai∪Ajw \in A_i \cup A_j therefore gives a distinct deleted predecessor at ii or jj. Thus

pi(ij)+pj(ij)≥∣Ai∪Aj∣,p_i(ij) + p_j(ij) \ge\lvert A_i \cup A_j\rvert,

contrary to (1). □\square

Assume henceforth in this section that ri≥dQ(i)r_i \ge d_Q(i). Call ii tight if ri=dQ(i)r_i = d_Q(i) and slack otherwise. An orientation is nearly balanced if ∣out⁡(i)−in⁡(i)∣≤1\lvert\operatorname{out}(i)-\operatorname{in}(i)\rvert\le1 for every ii. Such an orientation is obtained by pairing the odd vertices in each component, adding the corresponding edges, orienting an Euler tour, and deleting the added edges. An odd vertex is a source if out⁡(i)=in⁡(i)+1\operatorname{out}(i)=\operatorname{in}(i)+1 and a sink otherwise.

Lemma 2.2. Let MM be a matching whose endpoints have odd QQ-degree. Orient Q−MQ-M nearly balanced and put εi=1i∈V(M)\varepsilon_i=1_{i\in V(M)}. There are local orders with incoming edges first, the matching edge next, and outgoing edges last, such that every arc i→ji\to j satisfies

pi(ij)+pj(ij)≤in⁡(i)+εi+max⁡{out⁡(i),in⁡(j)}−1.(2)p_i(ij)+p_j(ij)\le\operatorname{in}(i)+\varepsilon_i+\max\{\operatorname{out}(i),\operatorname{in}(j)\}-1. \tag*{(2)}

The right-hand side is at most max⁡{dQ(i),dQ(j)}−1\max\{d_Q(i),d_Q(j)\}-1, except when dQ(i)=dQ(j)d_Q(i)=d_Q(j) is odd, jj is an unmatched sink, and ii is matched or an unmatched sink. In this case it equals dQ(i)d_Q(i). For ij∈Mij\in M, the predecessor sum is at most max⁡{dQ(i),dQ(j)}−1\max\{d_Q(i),d_Q(j)\}-1.

Proof. Split each vertex into an outgoing copy and an incoming copy, and apply Theorem 1.4 to the resulting simple bipartite graph. For i→ji\to j, the incoming edges and the matching edge at ii add in⁡(i)+εi\operatorname{in}(i)+\varepsilon_i predecessors, giving (2).

If out⁡(i)≥in⁡(j)\operatorname{out}(i)\ge\operatorname{in}(j), the bound is dQ(i)−1d_Q(i)-1. Otherwise it exceeds both endpoint bounds only if

in⁡(j)>out⁡(i),in⁡(i)+εi>out⁡(j)+εj.\operatorname{in}(j)>\operatorname{out}(i),\qquad\operatorname{in}(i)+\varepsilon_i>\operatorname{out}(j)+\varepsilon_j.

Set δi=in⁡(i)+εi−out⁡(i)\delta_i=\operatorname{in}(i)+\varepsilon_i-\operatorname{out}(i) and ηi=in⁡(i)−out⁡(i)−εi\eta_i=\operatorname{in}(i)-\operatorname{out}(i)-\varepsilon_i. Their values are

imatchedunmatched sinkevenunmatched sourceδi110−1ηi−110−1\begin{array}{c|cccc} i & \text{matched} & \text{unmatched sink} & \text{even} & \text{unmatched source}\\ \delta_i & 1 & 1 & 0 & -1\\ \eta_i & -1 & 1 & 0 & -1 \end{array}

The two strict inequalities force δi=ηj=1\delta_i=\eta_j=1 and out⁡(i)=out⁡(j)\operatorname{out}(i)=\operatorname{out}(j), giving the stated exception. For ij∈Mij\in M,

pi(ij)+pj(ij)=dQ(i)−12+dQ(j)−12≤max⁡{dQ(i),dQ(j)}−1.p_i(ij)+p_j(ij)=\frac{d_Q(i)-1}{2}+\frac{d_Q(j)-1}{2}\le\max\{d_Q(i),d_Q(j)\}-1.

□\square

In the exceptional case, a slack endpoint gives ∣Ai∪Aj∣≥dQ(i)+1\lvert A_i\cup A_j\rvert\ge d_Q(i)+1, so (1) still holds.

Corollary 2.3. Suppose QQ has a matching covering all odd tight vertices except at most one, and every even-degree endpoint of the matching is slack. Then QQ has local orders satisfying (1).

Proof. Add a pendant edge at each even matching endpoint. At such a vertex, ri≥dQ(i)+1r_i\ge d_Q(i)+1, so its unchanged set AiA_i still has size at least its new degree. Give each new vertex a set AiA_i of size at least two. All matching endpoints are now odd and all new vertices are slack.

Orient the graph minus the matching nearly balanced, making the unique unmatched odd tight vertex a source if it exists. Lemma 2.2 has no exceptional edge with two tight endpoints. Restrict the resulting orders to QQ; the predecessor counts decrease and the original sets AiA_i are unchanged. □\square

Lemma 2.4. Let OO be the odd tight vertices of QQ. If Q[O]Q[O] is complete multipartite, then QQ has local orders satisfying (1).

Proof. The case O=∅O = \varnothing follows from Corollary 2.3. Suppose a part AA satisfies ∣A∣≥∣O∖A∣|A| \ge|O \setminus A|. Match O∖AO \setminus A into AA, orient the graph minus these edges nearly balanced, and restore them directed toward AA. Their endpoints have even residual degree, so every vertex of O∖AO \setminus A becomes a source. All tight odd sinks lie in the independent set AA. Apply Lemma 2.2 with M=∅M = \varnothing.

Otherwise Q[O]Q[O] has a matching missing at most one vertex. For even ∣O∣|O|, repeatedly pair vertices in two largest parts; for odd ∣O∣|O|, first delete a vertex from a largest part. Corollary 2.3 applies.

An extension theorem

Theorem 3.1. Let HH be a triangle-free graph of order 2k−12k - 1, G=H‾G = \overline{H}, and dH(v)=Δ(H)=Dd_H(v) = \Delta(H) = D. Suppose H−vH - v has a perfect matching, with pairs picip_i c_i for pi∈P=NH(v)p_i \in P = N_H(v), i∈[D]i \in[D]. Put

C={ci:i∈[D]},Y=V(H)∖({v}∪P∪C),m=k−1−D.C = \{c_i : i \in[D]\}, \qquad Y = V(H) \setminus(\{v\} \cup P \cup C), \qquad m = k - 1 - D.

If G[Y]⪰sKmG[Y] \succeq_s K_m, then G⪰sKkG \succeq_s K_k.

Throughout this section, use the notation of Theorem 3.1. Since HH is triangle-free, PP is independent and P∩C=∅P \cap C = \varnothing. The matching on YY has mm edges. Fix a strong KmK_m immersion in G[Y]G[Y] with branch set WW, and put Z=Y∖WZ = Y \setminus W. Thus ∣W∣=∣Z∣=m|W| = |Z| = m.

Resources and optimal selections

For i∈[D]i \in[D], define

Li=NH(ci)∩W,Mi=NH(pi)∩W,L_i = N_H(c_i) \cap W, \qquad M_i = N_H(p_i) \cap W,
Ai=Li∪Mi,Ri=W∖Ai,ri=∣Ai∣.A_i = L_i \cup M_i, \qquad R_i = W \setminus A_i, \qquad r_i = |A_i|.

Since pici∈Hp_i c_i \in H, we have Li∩Mi=∅L_i \cap M_i = \varnothing. The available index resources and individual resources at ii are, respectively,

Ai={j∈[D]∖{i}:cicj,cipj∈G},\mathcal{A}_i = \{j \in[D] \setminus\{i\} : c_i c_j, c_i p_j \in G\},
Ui={z∈Z:ciz,piz∈G}.U_i = \{z \in Z : c_i z, p_i z \in G\}.

Write i→ji \to j and i→zi \to z for these resources, and set ai=∣Ai∣a_i = |\mathcal{A}_i|, ui=∣Ui∣u_i = |U_i|.

Lemma 3.2. For each i∈[D]i \in[D],

ai=D−dH(ci)+dH(ci,Y),ui=m−dH(ci,Z)−dH(pi,Z),qi:=ai+ui−ri=D−dH(ci)+m−dH(pi,Y)≥0.(3)\begin{aligned} a_i &= D - d_H(c_i) + d_H(c_i,Y),\\ u_i &= m - d_H(c_i,Z) - d_H(p_i,Z),\\ q_i &:= a_i + u_i - r_i = D - d_H(c_i) + m - d_H(p_i,Y) \ge0. \tag*{(3)} \end{aligned}

Proof. For j≠ij \ne i, triangle-freeness gives ∣NH(ci)∩{pj,cj}∣≤1|N_H(c_i) \cap\{p_j,c_j\}| \le1, and j∈Aij \in\mathcal{A}_i precisely when this intersection is empty. Since pi∈NH(ci)p_i \in N_H(c_i) and v∉NH(ci)v \notin N_H(c_i),

ai=(D−1)−(dH(ci)−dH(ci,Y)−1).a_i = (D - 1) - (d_H(c_i) - d_H(c_i,Y) - 1).

Also, NH(ci)∩NH(pi)=∅N_H(c_i) \cap N_H(p_i) = \varnothing, yielding the formula for uiu_i. Now

ri=dH(ci,W)+dH(pi,W),dH(ci)≤D,dH(pi,Y)≤m.r_i = d_H(c_i,W) + d_H(p_i,W), \qquad d_H(c_i) \le D, \qquad d_H(p_i,Y) \le m.

The last inequality follows because NH(pi)N_H(p_i) meets each matching edge of H[Y]H[Y] at most once. Substitution proves (3).

Choose a set S_i \subseteq A_i \mathbin{\mathaccent\cdot\cup} U_i with ∣Si∣=ri|S_i| = r_i for each ii. Here indices and vertices of ZZ are treated as distinct labels. Define QQ on [D][D] by

ij∈E(Q)⟺j∈Si and i∈Sj.ij \in E(Q) \Longleftrightarrow j \in S_i \text{ and } i \in S_j.

Then dQ(i)≤rid_Q(i) \le r_i. We vary the perfect matching of H[P,C]H[P,C] and the sets SiS_i, keeping P,C,Y,W,ZP,C,Y,W,Z and the labels pip_i fixed.

Put

B={i:Li=∅},I=[D]∖B,R=Q[I].B = \{i : L_i = \varnothing\}, \qquad I = [D] \setminus B, \qquad R = Q[I].

Assign each edge of QQ incident with BB to an endpoint i∈Bi \in B. Since dQ(i)≤ri=∣Mi∣d_Q(i) \le r_i = |M_i|, distinct colours in MiM_i give FF-edges using no pair (j,w)(j,w) with j∈Ij \in I. It remains to decompose RR.

For i∈Ii \in I, let \mathcal{F}_i = (A_i \cap B) \mathbin{\mathaccent\cdot\cup} U_i. Call the selection normalised if

∣Si∩Fi∣=min⁡{ri,∣Fi∣}(i∈I).|S_i \cap\mathcal{F}_i| = \min\{r_i,|\mathcal{F}_i|\} \qquad(i \in I).

Replacing an element of Si∩IS_i \cap I by an unused element of Fi\mathcal{F}_i cannot increase ∣E(R)∣|E(R)|. Choose a matching and a normalised selection minimising

(μ,∣T∣)lexicographically,μ=∣E(R)∣,T={i∈I:dR(i)=ri}.(4)(\mu, |T|) \quad\text{lexicographically}, \qquad\mu= |E(R)|, \qquad T = \{i \in I : d_R(i) = r_i\}. \tag*{(4)}

If i∈Ti \in T, then ri>0r_i > 0 and every element of SiS_i is a mutual index in II. Hence

Fi=∅,j∈Ai⟹i∈Sj.\mathcal{F}_i = \varnothing, \qquad j \in A_i \Longrightarrow i \in S_j.

Indeed, a violation of the second implication permits replacing a mutual index by jj, decreasing μ\mu. Consequently, for distinct i,j∈Ti,j \in T,

j∈Ai⟺i∈Aj⟺ij∈E(R).j \in A_i \Longleftrightarrow i \in A_j \Longleftrightarrow ij \in E(R).

Exchanging matched vertices

Lemma 3.3. Let a,b∈Ta,b \in T satisfy cacb∈Gc_a c_b \in G, b∉Aab \notin A_a and a∉Aba \notin A_b. Then paca,pbcbp_a c_a,p_b c_b can be replaced by pacb,pbcap_a c_b,p_b c_a, with a normalised selection for which μ\mu does not increase. Moreover, for c∈{ca,cb}c \in\{c_a,c_b\} and j∉{a,b}j \notin\{a,b\},

ccj,cpj∈G⟹cjpa,cjpb∈G.cc_j,cp_j \in G \Longrightarrow c_jp_a,c_jp_b \in G.

Proof. Put P0={pa,pb}P_0 = \{p_a,p_b\} and C0={ca,cb}C_0 = \{c_a,c_b\}. The assumptions give

H[P0∪C0]=K2,2 with parts P0,C0.H[P_0 \cup C_0] = K_{2,2} \text{ with parts } P_0,C_0.

Since Ua=Ub=∅U_a = U_b = \varnothing, every z∈Zz \in Z meets both matching edges in HH. Triangle-freeness implies

NH(z)∩(P0∪C0)∈{P0,C0}.N_H(z) \cap(P_0 \cup C_0) \in\{P_0,C_0\}.

Thus, after the exchange, Ua′=Ub′=∅U'_a = U'_b = \varnothing. Resources into BB depend only on the CC endpoint and the unchanged pairs in BB, so Fa′=Fb′=∅\mathcal{F}'_a = \mathcal{F}'_b = \varnothing. Furthermore,

La′=Lb,Lb′=La,Ma′=Ma,Mb′=Mb,ra′+rb′=ra+rb>0,L'_a = L_b,\qquad L'_b = L_a,\qquad M'_a = M_a,\qquad M'_b = M_b,\qquad r'_a + r'_b = r_a + r_b > 0,

and ra′,rb′>0r'_a,r'_b > 0. In particular, II and BB are unchanged.

For j∉{a,b}j \notin\{a,b\}, transfer Sj∩{a,b}S_j \cap\{a,b\} as follows. If NH(cj)∩P0≠∅N_H(c_j) \cap P_0 \ne\varnothing, triangle-freeness gives NH(cj)∩C0=∅N_H(c_j) \cap C_0 = \varnothing; keep each selected index at its PP endpoint. Otherwise keep it with its CC endpoint. The selected resources remain distinct and available, and ∣Sj′∣=∣Sj∣|S'_j| = |S_j|. For j∈I∖{a,b}j \in I \setminus\{a,b\}, also Fj′=Fj\mathcal{F}'_j = \mathcal{F}_j and Sj′∩Fj=Sj∩FjS'_j \cap\mathcal{F}_j = S_j \cap\mathcal{F}_j.

By Lemma 3.2, choose ∣Sa′∣=ra′|S'_a| = r'_a and ∣Sb′∣=rb′|S'_b| = r'_b. Since ab∉E(R′)ab \notin E(R') and R′−{a,b}=R−{a,b}R' - \{a,b\} = R - \{a,b\},

∣E(R′)∣−∣E(R)∣=dR′(a)+dR′(b)−dR(a)−dR(b)≤ra′+rb′−ra−rb=0.\begin{aligned} |E(R')| - |E(R)| = d_{R'}(a) + d_{R'}(b) - d_R(a) - d_R(b) \\ &\le r'_a + r'_b - r_a - r_b = 0. \end{aligned}

For the last assertion, suppose ccj,cpj∈Gcc_j, cp_j \in G but cjpt∈Hc_jp_t \in H for some t∈{a,b}t \in\{a,b\}. Pair cc with ptp_t, exchanging the two pairs if necessary. The resource t→jt \to j remains available, but j→tj \to t is unavailable. Choose j∈St′j \in S'_t, and complete Sa′,Sb′S'_a,S'_b by Lemma 3.2. Then

dR′(a)+dR′(b)≤ra′+rb′−1=ra+rb−1,d_{R'}(a) + d_{R'}(b) \le r'_a + r'_b - 1 = r_a + r_b - 1,

contrary to the minimality of μ\mu.

Lemma 3.4. If dH(ph,Y)=md_H(p_h,Y) = m for some hh, then there are a strong KmK_m immersion in G[Y]G[Y], a perfect matching of H[P,C]H[P,C], and a normalised selection for which QQ has a compatible decomposition.

Proof. Set W∗=NH(ph)∩YW^* = N_H(p_h) \cap Y. This is an independent transversal of the matching of H[Y]H[Y], so G[W∗]=KmG[W^*] = K_m. Use this clique as the immersion, set W=W∗W = W^* and Z=Y∖WZ = Y \setminus W, redefine the resource sets, and minimise (4) again. For every partner chc_h of php_h, triangle-freeness gives Lh=∅L_h = \varnothing; hence h∈Bh \in B.

For i∈Ti \in T, choose w∈Liw \in L_i. Since ciw,phw∈Hc_iw,p_hw \in H, we have ciph∈Gc_ip_h \in G. As h∉Aih \notin A_i, it follows that cich∈Hc_ic_h \in H. Thus

{ci:i∈T}⊆NH(ch)\{c_i : i \in T\} \subseteq N_H(c_h)

is independent in HH. If a,b∈Ta,b \in T and ab∉E(R)ab \notin E(R), Lemma 3.3 applies. For j∈NR[T](a)∖NR[T](b)j \in N_{R[T]}(a) \setminus N_{R[T]}(b), we have cacj,capj∈Gc_ac_j,c_ap_j \in G but cjpb∈Hc_jp_b \in H, a contradiction. Therefore

ab∉E(R[T])⟹NR[T](a)=NR[T](b).ab \notin E(R[T]) \mathrel{\Longrightarrow} N_{R[T]}(a) = N_{R[T]}(b).

Hence R[T]R[T] is complete multipartite. The odd tight vertices of RR form a subset of TT, so the subgraph they induce is also complete multipartite. Lemmas 2.4 and 2.1 therefore give a compatible decomposition of RR. Adding the FF-edges assigned to BB gives a compatible decomposition of QQ.

By (3), qi=0q_i = 0 implies dH(ci)=Dd_H(c_i) = D and dH(pi,Y)=md_H(p_i,Y) = m, so Lemma 3.4 applies whenever some qi=0q_i = 0.

Auxiliary matchings

Colour the pairs in TT by

ij:{red,ij∈E(R),blue,cicj∈H,white,otherwise.ij : \begin{cases} \text{red}, & ij \in E(R),\\ \text{blue}, & c_ic_j \in H,\\ \text{white}, & \text{otherwise}. \end{cases}

The blue graph is triangle-free, and every white pair satisfies Lemma 3.3. There is no triangle with one red and two white edges: if ajaj is red and ab,bjab,bj are white, then cacj,capj∈Gc_ac_j,c_ap_j \in G but cjpb∈Hc_jp_b \in H, contradicting that lemma.

Lemma 3.5. On any induced vertex set, the red graph has at most two nonbipartite components. If it has two, these are its only components.

Proof. Let KK be a nonbipartite red component. For x∉V(K)x \notin V(K), put

Bx={u∈V(K):xu is blue}.B_x = \{u \in V(K): xu\text{ is blue}\}.

Each BxB_x is a vertex cover of KK, since an uncovered red edge would form a red–white–white triangle with xx. If xyxy is blue with x,y∉V(K)x,y \notin V(K), then Bx∩By=∅B_x \cap B_y = \varnothing, and every edge of KK joins BxB_x to ByB_y. This makes KK bipartite, a contradiction.

Thus there are no blue edges outside KK. If the red graph outside KK had a component containing an edge uvuv and another component containing a vertex xx, then uv,ux,vxuv, ux, vx would again be red, white, white. The assertion follows.

Set

O={i∈T:dR(i) is odd},J=R[O],O = \{i \in T : d_R(i)\text{ is odd}\}, \qquad J = R[O],

and apply Theorem 1.3 to JJ, with parts D0,A0,C0D_0, A_0, C_0. A nontrivial connected factor-critical graph is nonbipartite: a bipartition with sizes a,ba,b would require both a−1=ba-1=b and a=b−1a=b-1. Lemma 3.5, applied on O∖A0O \setminus A_0, gives at most two nontrivial components of J[D0]J[D_0]. If there are two, then

C0=∅,c(J[D0])=2,def⁡(J)=2−∣A0∣.C_0 = \varnothing, \qquad c(J[D_0]) = 2, \qquad\operatorname{def}(J) = 2 - |A_0|.

Proposition 3.6. If def⁡(J)≤1\operatorname{def}(J) \le1 or J[D0]J[D_0] has at most one nontrivial component, then RR has local orders satisfying (1), and QQ has a compatible decomposition.

Proof. If def⁡(J)≤1\operatorname{def}(J) \le1, a maximum matching of JJ and Corollary 2.3 give (1). Otherwise J[D0]J[D_0] has at most one nontrivial component.

Case 1. Every component of J[D0]J[D_0] is a singleton.

Let MM be the perfect matching on C0C_0 and FF the matching from A0A_0 to D0D_0 in a maximum matching of JJ. Orient R−M−FR-M-F nearly balanced, and restore FF from A0A_0 to D0D_0. The endpoints of FF have even degree in R−M−FR-M-F, so the resulting orientation of R−MR-M is nearly balanced and every vertex of A0A_0 is a source.

Every unmatched tight odd sink lies in D0D_0, and

E(J[D0])=EJ(D0,C0)=∅.E(J[D_0]) = E_J(D_0,C_0) = \varnothing.

Its tight odd neighbours therefore lie in A0A_0 and are sources. Lemma 2.2 has no exceptional edge with two tight endpoints.

Case 2. J[D0]J[D_0] has exactly one nontrivial component KK.

Choose b∈V(K)b \in V(K) and a maximum matching of JJ missing bb. By Theorem 1.3, no matching edge from A0A_0 enters KK. Let FF be its edges from A0A_0 to the singleton components of D0D_0, and let MM consist of its perfect matchings on C0C_0 and K−bK-b.

Orient R−M−FR-M-F nearly balanced, making bb a source by reversing its component if necessary. Restore FF from A0A_0 to D0D_0. Every vertex of A0A_0 becomes a source, since its residual degree was even. Every unmatched tight odd sink lies in a singleton component of D0D_0 and has tight odd neighbours only in A0A_0. Again Lemma 2.2 has no exceptional edge with two tight endpoints.

In both cases, any exceptional edge has a slack endpoint, so (1) holds. Lemma 2.1 gives a compatible decomposition of RR; adding the FF-edges assigned to BB gives one of QQ.

Proposition 3.7. Suppose the optimal choice satisfies qi>0q_i > 0 for every i∈[D]i \in[D]. If J[D0]J[D_0] has two nontrivial components and def⁡(J)=2\operatorname{def}(J) = 2, then a normalised selection can be chosen, with the same matching and branch set WW, for which QQ has a compatible decomposition.

Proof. Let K1,K2K_1,K_2 be the two nontrivial components. Then

A0=C0=∅,O=V(K1)⊔V(K2).A_0=C_0=\varnothing,\qquad O=V(K_1)\sqcup V(K_2).

Choose bj∈E(K1)b_j \in E(K_1). Since b∈Tb \in T and qb>0q_b > 0, we have Fb=∅F_b=\varnothing and ab−rb=qb>0a_b-r_b=q_b>0. Choose x∈Ab∖Sbx \in A_b \setminus S_b. By optimality, b∈Sxb \in S_x. Also x∉Tx \notin T, since otherwise bx∈E(R)bx \in E(R) would force x∈Sbx \in S_b.

Replace SbS_b by (Sb∖{j})∪{x}(S_b \setminus\{j\}) \cup\{x\}. The selection remains normalised, and

R′=R−bj+bx,∣E(R′)∣=∣E(R)∣,R'=R-b_j+bx,\qquad|E(R')|=|E(R)|,
dR′(j)=rj−1,dR′(x)=dR(x)+1.d_{R'}(j)=r_j-1,\qquad d_{R'}(x)=d_R(x)+1.

Since jj leaves TT, the minimality of ∣T∣|T| forces xx to enter TT. Hence

dR(x)=rx−1,T′=(T∖{j})∪{x}.d_R(x)=r_x-1,\qquad T'=(T\setminus\{j\})\cup\{x\}.

The vertex jj has even R′R'-degree and is slack. Fix b2∈V(K2)b_2 \in V(K_2). For a factor-critical graph KK and u∈V(K)u \in V(K), let M(K−u)M(K-u) denote a perfect matching of K−uK-u.

Case 1. dR′(x)d_{R'}(x) is even.

The odd tight vertices of R′R' are O∖{j}O\setminus\{j\}. The matching

M′=M(K1−j)∪M(K2−b2)M'=M(K_1-j)\cup M(K_2-b_2)

lies in R′R' and covers all of them except b2b_2.

Case 2. dR′(x)d_{R'}(x) is odd.

The odd tight vertices of R′R' are (O∖{j})∪{x}(O\setminus\{j\})\cup\{x\}. The matching

M′=M(K1−b)∪M(K2−b2)∪{bx}M'=M(K_1-b)\cup M(K_2-b_2)\cup\{bx\}

lies in R′R': x∉Ox\notin O, and none of its edges is bjb_j. It covers all odd tight vertices except b2b_2, and its only even endpoint is the slack vertex jj.

In each case, Corollary 2.3 and Lemma 2.1 give a compatible decomposition of R′R'. Adding the FF-edges assigned to BB gives a compatible decomposition of the final graph QQ.

Realising the decomposition

Proposition 3.8. Let WW be the branch set of a strong KmK_m immersion in G[Y]G[Y]. For any perfect matching of H[P,C]H[P,C] and resource sets SiS_i as above, if QQ has a compatible decomposition, then GG has a strong KkK_k immersion with branch set {v}∪C∪W\{v\}\cup C\cup W.

Proof. As in [9 Section 3], take

B={v}∪C∪WB=\{v\}\cup C\cup W

as the branch set, retaining the strong KmK_m immersion on WW. Since NH(v)=PN_H(v)=P, join vv directly to C∪WC\cup W. For i<ji<j, use the edge cicjc_i c_j if it lies in GG, and otherwise the path

ci−pj−pi−cj.(5)c_i-p_j-p_i-c_j. \tag*{(5)}

The latter exists by triangle-freeness of HH and independence of PP in HH. Also use every edge of EG(C,W)E_G(C,W). The remaining pairs are

{(ci,w):i∈[D], w∈Li}.\{(c_i,w): i \in[D],\ w \in L_i\}.

For w∈Liw \in L_i, the available resources give paths

w−pi−pj−ci(j∈Si∩[D]),(6)w-p_i-p_j-c_i \qquad(j \in S_i \cap[D]), \tag*{(6)}

or w−pi−z−ciw-p_i-z-c_i for z∈Si∩Zz \in S_i \cap Z. Here wpi∈Gwp_i \in G because Li∩Mi=∅L_i \cap M_i = \varnothing.

For a piece of colour ww, make the following assignments:

  • (i) For an FF-edge ijij owned by ii, delete i→ji \to j. Since w∈Miw \in M_i, the edge ciwc_iw has already been used.

  • (ii) For an LLLL-edge ijij, assign w−pj−ciw-p_j-c_i and w−pi−cjw-p_i-c_j, using i→ji \to j and j→ij \to i.

  • (iii) For an LRLR-edge ijij with label LL at ii, assign w−pj−ciw-p_j-c_i, using i→ji \to j.

  • (iv) For an all-LL odd cycle i0i1⋯i2ti0i_0i_1\cdots i_{2t}i_0, assign w−pis+1−cisw-p_{i_{s+1}}-c_{i_s} using is→is+1i_s \to i_{s+1} for each ss, with subscripts modulo 2t+12t+1.

  • (v) For an LLRLLR path a−b−ca-b-c, assign w−pb−caw-p_b-c_a and w−pc−cbw-p_c-c_b, using a→ba \to b and b→cb \to c.

These short paths exist because their internal vertices have label LL or RR. Let fif_i be the number of deleted resources at ii, and sis_i the number used by short paths starting at a vertex of LiL_i and ending at cic_i. Compatibility gives

fi≤∣Mi∣,si≤∣Li∣,ri−fi−si≥∣Li∣−si.f_i \le|M_i|,\qquad s_i \le|L_i|,\qquad r_i-f_i-s_i \ge|L_i|-s_i.

Assign the remaining ∣Li∣−si|L_i|-s_i pairs to distinct unused elements of SiS_i, using the corresponding long paths. Discard unused resources.

We check edge-disjointness by edge type.

  • (i) Each edge cipjc_ip_j determines a unique resource i→ji \to j, used at most once. Its occurrence in (5) requires cicj∈Hc_ic_j \in H, whereas a resource path requires cicj∈Gc_ic_j \in G.

  • (ii) An edge pipjp_ip_j can occur in two resource paths only if ij∈E(Q)ij \in E(Q). Each piece deletes or shortens at least one of i→ji \to j, j→ij \to i. Its occurrence in (5) is excluded by the same adjacency condition as in (i).

  • (iii) A short path using wpiwp_i uses the pair (i,w)(i,w), so there is at most one such path. If w∈Liw \in L_i, the same piece assigns the pair (ci,w)(c_i,w) a short path, excluding its long path. If w∈Riw \in R_i, the edge ciwc_iw has already been used; if w∈Miw \in M_i, then wpi∉Gwp_i \notin G. Distinct long paths use distinct pairs (i,w)(i,w).

  • (iv) Each edge pizp_iz or cizc_iz determines a unique individual resource i→zi \to z, used at most once. These edges belong to no other new path.

  • (v) The old paths use only E(G[Y])E(G[Y]), which no new path uses. The direct edges from vv, within CC, and between CC and WW occur in no other path.

Thus the paths are pairwise edge-disjoint. Every new internal vertex lies in P∪ZP \cup Z, and

(P∪Z)∩B=∅,∣B∣=1+D+m=k.(P \cup Z) \cap B = \varnothing,\qquad|B|=1+D+m=k.

Therefore G⪰sKkG \succeq_s K_k.

Proof of Theorem 3.1. If m=0m=0, the direct edges from vv to CC, the edges of G[C]G[C], and the paths (5) give a strong KkK_k immersion. Assume m>0m>0 and choose a matching and a normalised selection minimising (4).

If some qi=0q_i=0, Lemma 3.4 gives a choice of WW, matching and selection for which QQ has a compatible decomposition. Otherwise qi>0q_i>0 for every ii. By Lemma 3.5 and Theorem 1.3, J[D0]J[D_0] has at most two nontrivial components. Proposition 3.6 applies if it has at most one, or if def⁡(J)≤1\operatorname{def}(J)\leq1. In the remaining case, def⁡(J)=2−∣A0∣>1\operatorname{def}(J)=2-|A_0|>1, so A0=∅A_0=\varnothing and def⁡(J)=2\operatorname{def}(J)=2; Proposition 3.7 applies. Thus in every case a compatible decomposition of QQ exists. Proposition 3.8 completes the proof.

Proof of the main theorem

Proof of Theorem 1.2. Let H=G‾H=\overline{G}. Since α(G)≤2\alpha(G)\leq2, the two-vertex colour classes form a matching in HH, and

χ(G)=∣V(G)∣−ν(H).(7)\chi(G)=|V(G)|-\nu(H). \tag*{(7)}

We proceed by induction on ∣V(G)∣|V(G)|. The assertion is immediate for ∣V(G)∣≤1|V(G)|\leq1. Passing to a vertex-critical induced subgraph with the same chromatic number, assume GG is vertex-critical. For every v∈V(G)v\in V(G),

χ(G−v)=χ(G)−1⟹ν(H−v)=ν(H).\chi(G-v)=\chi(G)-1 \quad\Longrightarrow\quad\nu(H-v)=\nu(H).

Hence D=V(H)D=V(H) in Theorem 1.3, so every component of HH is factor-critical.

If HH has components H1,…,HtH_1,\ldots,H_t with t≥2t\geq2, then

G=H1‾∨⋯∨Ht‾,χ(G)=∑i=1tχ(Hi‾).G=\overline{H_1}\vee\cdots\vee\overline{H_t},\qquad \chi(G)=\sum_{i=1}^{t}\chi(\overline{H_i}).

By induction, Hi‾⪰sKχ(Hi‾)\overline{H_i}\succeq_s K_{\chi(\overline{H_i})}. Joining their branch sets by the direct edges between different factors gives G⪰sKχ(G)G\succeq_s K_{\chi(G)}.

Assume HH is connected. Write ∣V(H)∣=2k−1|V(H)|=2k-1. Then ν(H)=k−1\nu(H)=k-1 and χ(G)=k\chi(G)=k. Choose vv with dH(v)=Δ(H)d_H(v)=\Delta(H) and a perfect matching of H−vH-v. Define P,C,Y,mP,C,Y,m as in Theorem 3.1. Since H[Y]H[Y] has a perfect matching,

χ(G[Y])=∣Y∣−ν(H[Y])=2m−m=m.\chi(G[Y])=|Y|-\nu(H[Y])=2m-m=m.

Induction gives G[Y]⪰sKmG[Y]\succeq_s K_m, and Theorem 3.1 gives G⪰sKkG\succeq_s K_k.

Acknowledgements

This work was supported by the National Natural Science Foundation of China under Grant No. 12161073, the Guangdong Basic and Applied Basic Research Foundation under Grant No. 2026A1515012764, the GDUPT Talent Recruitment Project (No. 2024rcyj1007), and the Scientific Research Funds at China University of Geosciences (Wuhan) (Project No. 2026039).

Declaration of AI use

The authors used GPT-6.1 to assist with exploring proof strategies, checking proofs, and improving the exposition. All mathematical arguments, results, and conclusions were reviewed and verified by the authors, who take full responsibility for the content of this paper.

References

  1. [1]F. N. Abu-Khzam and M. A. Langston, Graph coloring and the immersion order, in Computing and Combinatorics, Lecture Notes in Comput. Sci. 2697, Springer, 2003, 394–403. doi:10.1007/3-540-45071-8_40.
  2. [2]A. Bermúdez, B. L. Netto and D. A. Quiroz, Odd minors or odd immersions in graphs with independence number two, preprint (2026), arXiv:2608.15302v1.arxiv.org/abs/2608.15302
  3. [3]K. Bérczi, G. Csáji and T. Király, Manipulating the outcome of stable matching and roommates problems, preprint (2022), arXiv:2204.13485v1.arxiv.org/abs/2204.13485
  4. [4]O. V. Borodin, A. V. Kostochka and D. R. Woodall, List edge and list total colourings of multigraphs, J. Combin. Theory Ser. B 71 (1997), 184–204. Author full text.DOI
  5. [5]F. Botler, C. G. Fernandes, C. N. Lintzmayer, R. A. Lopes, S. Mishra, B. L. Netto and M. S ambinelli, Immersions of large cliques in graphs with independence number 2 and bounded maximum degree, preprint (2025), arXiv:2506.09768v1.arxiv.org/abs/2506.09768
  6. [6]F. Botler, A. Jiménez, C. N. Lintzmayer, A. Pastine, D. A. Quiroz and M. Sambinelli, Biclique immersions in graphs with independence number 2, European J. Combin. 122 (2024), 104042. doi:10.1016/j.ejc.2024.104042.DOI
  7. [7]S. Bustamante, D. A. Quiroz, M. Stein and J. Zamora, Clique immersions and independence number, European J. Combin. 106 (2022), 103550. doi:10.1016/j.ejc.2022.103550.DOI
  8. [8]R. Chen and Z. Deng, Complete bipartite immersion in graphs with independence number two: A simple proof, Discrete Math. 348(12) (2025), 114737. doi:10.1016/j.disc.2025.114737.DOI
  9. [9]J. C. Dahlke, The Abu-Khzam–Langston conjecture for graphs with α(G) = 2, preprint (2026), arXiv:2605.28159v1.
  10. [10]Z. Deng, C. Chang and Y. Liu, Lescure-Meyniel conjecture holds for Gem-free graphs with independence number two, Indian J. Pure Appl. Math. (2026), published online 16 February 2026. doi:10.1007/s13226-026-00942-6.DOI
  11. [11]H. Echeverría and J. McDonald, Coloring graphs with independence number two and no odd clique immersions, preprint (2026), arXiv:2605.04022v1.arxiv.org/abs/2605.04022
  12. [12]T. Fleiner, List colourings with restricted lists, EGRES Quick-Proof 2017-01 (2017). https://egres.elte.hu/qp/egresqp-17-01.pdf.
  13. [13]G. Gauthier, T.-N. Le and P. Wollan, Forcing clique immersions through chromatic number, European J. Combin. 81 (2019), 98–118. doi:10.1016/j.ejc.2019.04.003.DOI
  14. [14]F. Lescure and H. Meyniel, On a problem upon configurations contained in graphs with given chromatic number, in Graph Theory in Memory of G. A. Dirac, Ann. Discrete Math. 41 (1989), 325–331. doi:10.1016/S0167-5060(08)70470-9.DOI
  15. [15]D. A. Quiroz, Clique immersions in graphs of independence number two with certain forbidden subgraphs, Discrete Math. 344(6) (2021), 112365. doi:10.1016/j.disc.2021.112365.DOI
  16. [16]J. J. M. Tan, A necessary and sufficient condition for the existence of a complete stable matching, J. Algorithms 12 (1991), 154–178. doi:10.1016/0196-6774(91)90028-W.DOI
  17. [17]S. Vergara, Complete graph immersions in dense graphs, Discrete Math. 340 (2017), 1019–1027. doi:10.1016/j.disc.2017.01.001.
  18. [18]D. B. West, A short proof of the Berge–Tutte formula and the Gallai–Edmonds structure theorem, European J. Combin. 32 (2011), 674–676. doi:10.1016/j.ejc.2011.01.009.DOI

Paper details

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

views · 0

downloads · 0

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

  • Mathematics

GPT-6.1

View statement
Looking for related papers…
Contents