WorksMathematics
Strong complete immersions in graphs with independence number two
Abstract
We prove that every graph with independence number at most two contains a strong immersion of . 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 in a graph consists of an injection and pairwise edge-disjoint paths joining and for . The vertices in are its branch vertices. The immersion is strong if
We write if contains a strong immersion of .
Lescure and Meyniel proposed the following conjecture.
Conjecture 1.1 (Lescure and Meyniel [14]). Every graph contains a strong immersion of .
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 , then .
For an -vertex graph with , we have . Thus Theorem 1.2 also gives . Vergara [17] proved , and Gauthier, Le and Wollan [13] improved this to . Botler et al. [5] proved when and , or when is covered by three cliques and . Deng, Chang and Liu [10] proved the gem-free case. Quiroz [15] proved that every -free graph with contains an immersion of , provided and .
Botler et al. [6] proved that every -vertex graph with independence number two contains every complete bipartite graph on vertices as an immersion. Chen and Deng [8] gave a simpler proof. For , Bustamante et al. [7] obtained lower bounds on the order of a clique immersion in terms of and .
Dahlke [9] proved that every graph with contains a weak immersion of . Theorem 1.2 strengthens this result to strong immersions. We use the bridge construction and the decomposition of [9]. By choosing the matching and the available paths suitably, we eliminate the pieces, whose paths may contain other branch vertices.
Bermúdez, Netto and Quiroz [2] proved that every -vertex graph with contains as an odd minor or as a totally odd strong immersion; the immersion alternative holds under additional hypotheses. Echeverría and McDonald [11] proved for graphs in this class with no strong odd 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 , for , , and for the matching number. For disjoint sets , , let be the edges between them. The join of disjoint graphs , is denoted by . A graph is factor-critical if has a perfect matching for every . We allow the empty immersion.
Theorem 1.3 (Gallai–Edmonds; see [18 Theorem 5]). Let be the vertices missed by some maximum matching of , and put
Then has a perfect matching, every component of is factor-critical, and . Every maximum matching consists of a perfect matching on , near-perfect matchings in the components of , and edges matching into distinct such components. In particular,
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 admits strict orders on its incident edges such that
where is the number of edges preceding at .
Since is simple, the seeing count in [4] equals the predecessor sum above.
Theorem 1.5 (Tan [16]). In a graph with strict preferences on the neighbours of each vertex and self-partnership ranked last, there is a permutation such that whenever ,
and no edge satisfies both and .
See also [3 Theorem 2]. Replacing an even cycle of by alternating pairs gives each vertex a partner at least as preferred as its predecessor. Thus we may assume that every cycle of has length one, two, or odd length at least three.
Local orders and decompositions
Let be a simple graph and a finite colour set. For each , put
The following pieces, each assigned a colour , are adapted from [9 Lemma 2.7]:
(i) an -edge with owner and , using the pair ;
(ii) an - or -edge , using ;
(iii) an odd cycle with all vertices labelled , using at each vertex;
(iv) a path labelled , using .
Here a vertex has label , or according to the set containing . A compatible decomposition partitions into these pieces and uses each pair at most once.
Lemma 2.1. If has strict local edge orders satisfying
then has a compatible decomposition.
Proof. Process the colours successively. For a colour , let consist of the remaining edges with . Apply Theorem 1.5 to , preferring earlier incident edges.
Assign each 2-cycle an -edge if it has an endpoint, and an - or -edge otherwise. Retain every all- odd cycle. Let be any other odd cycle, in successor order.
If has label , select the -edge owned by and the pairs
If the cycle has no vertex, its vertices are independent. Hence, after relabelling, have labels . Select this path and the pairs . Assign the pairs as above and delete all selected edges. The selected pieces use distinct pairs .
Every unselected edge of has a selected edge preceding it at one endpoint. If one endpoint of 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 . Otherwise, if is outside the permutation cycles, the same theorem gives an endpoint at which both cycle edges precede . In either case, at least one of these cycle edges is selected. Finally, if is an omitted cycle edge, then is selected and precedes at (subscripts modulo $2t+1). If remains after all colours, each therefore gives a distinct deleted predecessor at or . Thus
contrary to (1).
Assume henceforth in this section that . Call tight if and slack otherwise. An orientation is nearly balanced if for every . 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 and a sink otherwise.
Lemma 2.2. Let be a matching whose endpoints have odd -degree. Orient nearly balanced and put . There are local orders with incoming edges first, the matching edge next, and outgoing edges last, such that every arc satisfies
The right-hand side is at most , except when is odd, is an unmatched sink, and is matched or an unmatched sink. In this case it equals . For , the predecessor sum is at most .
Proof. Split each vertex into an outgoing copy and an incoming copy, and apply Theorem 1.4 to the resulting simple bipartite graph. For , the incoming edges and the matching edge at add predecessors, giving (2).
If , the bound is . Otherwise it exceeds both endpoint bounds only if
Set and . Their values are
The two strict inequalities force and , giving the stated exception. For ,
In the exceptional case, a slack endpoint gives , so (1) still holds.
Corollary 2.3. Suppose has a matching covering all odd tight vertices except at most one, and every even-degree endpoint of the matching is slack. Then has local orders satisfying (1).
Proof. Add a pendant edge at each even matching endpoint. At such a vertex, , so its unchanged set still has size at least its new degree. Give each new vertex a set 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 ; the predecessor counts decrease and the original sets are unchanged.
Lemma 2.4. Let be the odd tight vertices of . If is complete multipartite, then has local orders satisfying (1).
Proof. The case follows from Corollary 2.3. Suppose a part satisfies . Match into , orient the graph minus these edges nearly balanced, and restore them directed toward . Their endpoints have even residual degree, so every vertex of becomes a source. All tight odd sinks lie in the independent set . Apply Lemma 2.2 with .
Otherwise has a matching missing at most one vertex. For even , repeatedly pair vertices in two largest parts; for odd , first delete a vertex from a largest part. Corollary 2.3 applies.
An extension theorem
Theorem 3.1. Let be a triangle-free graph of order , , and . Suppose has a perfect matching, with pairs for , . Put
If , then .
Throughout this section, use the notation of Theorem 3.1. Since is triangle-free, is independent and . The matching on has edges. Fix a strong immersion in with branch set , and put . Thus .
Resources and optimal selections
For , define
Since , we have . The available index resources and individual resources at are, respectively,
Write and for these resources, and set , .
Lemma 3.2. For each ,
Proof. For , triangle-freeness gives , and precisely when this intersection is empty. Since and ,
Also, , yielding the formula for . Now
The last inequality follows because meets each matching edge of at most once. Substitution proves (3).
Choose a set S_i \subseteq A_i \mathbin{\mathaccent\cdot\cup} U_i with for each . Here indices and vertices of are treated as distinct labels. Define on by
Then . We vary the perfect matching of and the sets , keeping and the labels fixed.
Put
Assign each edge of incident with to an endpoint . Since , distinct colours in give -edges using no pair with . It remains to decompose .
For , let \mathcal{F}_i = (A_i \cap B) \mathbin{\mathaccent\cdot\cup} U_i. Call the selection normalised if
Replacing an element of by an unused element of cannot increase . Choose a matching and a normalised selection minimising
If , then and every element of is a mutual index in . Hence
Indeed, a violation of the second implication permits replacing a mutual index by , decreasing . Consequently, for distinct ,
Exchanging matched vertices
Lemma 3.3. Let satisfy , and . Then can be replaced by , with a normalised selection for which does not increase. Moreover, for and ,
Proof. Put and . The assumptions give
Since , every meets both matching edges in . Triangle-freeness implies
Thus, after the exchange, . Resources into depend only on the endpoint and the unchanged pairs in , so . Furthermore,
and . In particular, and are unchanged.
For , transfer as follows. If , triangle-freeness gives ; keep each selected index at its endpoint. Otherwise keep it with its endpoint. The selected resources remain distinct and available, and . For , also and .
By Lemma 3.2, choose and . Since and ,
For the last assertion, suppose but for some . Pair with , exchanging the two pairs if necessary. The resource remains available, but is unavailable. Choose , and complete by Lemma 3.2. Then
contrary to the minimality of .
Lemma 3.4. If for some , then there are a strong immersion in , a perfect matching of , and a normalised selection for which has a compatible decomposition.
Proof. Set . This is an independent transversal of the matching of , so . Use this clique as the immersion, set and , redefine the resource sets, and minimise (4) again. For every partner of , triangle-freeness gives ; hence .
For , choose . Since , we have . As , it follows that . Thus
is independent in . If and , Lemma 3.3 applies. For , we have but , a contradiction. Therefore
Hence is complete multipartite. The odd tight vertices of form a subset of , so the subgraph they induce is also complete multipartite. Lemmas 2.4 and 2.1 therefore give a compatible decomposition of . Adding the -edges assigned to gives a compatible decomposition of .
By (3), implies and , so Lemma 3.4 applies whenever some .
Auxiliary matchings
Colour the pairs in by
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 is red and are white, then but , 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 be a nonbipartite red component. For , put
Each is a vertex cover of , since an uncovered red edge would form a red–white–white triangle with . If is blue with , then , and every edge of joins to . This makes bipartite, a contradiction.
Thus there are no blue edges outside . If the red graph outside had a component containing an edge and another component containing a vertex , then would again be red, white, white. The assertion follows.
Set
and apply Theorem 1.3 to , with parts . A nontrivial connected factor-critical graph is nonbipartite: a bipartition with sizes would require both and . Lemma 3.5, applied on , gives at most two nontrivial components of . If there are two, then
Proposition 3.6. If or has at most one nontrivial component, then has local orders satisfying (1), and has a compatible decomposition.
Proof. If , a maximum matching of and Corollary 2.3 give (1). Otherwise has at most one nontrivial component.
Case 1. Every component of is a singleton.
Let be the perfect matching on and the matching from to in a maximum matching of . Orient nearly balanced, and restore from to . The endpoints of have even degree in , so the resulting orientation of is nearly balanced and every vertex of is a source.
Every unmatched tight odd sink lies in , and
Its tight odd neighbours therefore lie in and are sources. Lemma 2.2 has no exceptional edge with two tight endpoints.
Case 2. has exactly one nontrivial component .
Choose and a maximum matching of missing . By Theorem 1.3, no matching edge from enters . Let be its edges from to the singleton components of , and let consist of its perfect matchings on and .
Orient nearly balanced, making a source by reversing its component if necessary. Restore from to . Every vertex of becomes a source, since its residual degree was even. Every unmatched tight odd sink lies in a singleton component of and has tight odd neighbours only in . 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 ; adding the -edges assigned to gives one of .
Proposition 3.7. Suppose the optimal choice satisfies for every . If has two nontrivial components and , then a normalised selection can be chosen, with the same matching and branch set , for which has a compatible decomposition.
Proof. Let be the two nontrivial components. Then
Choose . Since and , we have and . Choose . By optimality, . Also , since otherwise would force .
Replace by . The selection remains normalised, and
Since leaves , the minimality of forces to enter . Hence
The vertex has even -degree and is slack. Fix . For a factor-critical graph and , let denote a perfect matching of .
Case 1. is even.
The odd tight vertices of are . The matching
lies in and covers all of them except .
Case 2. is odd.
The odd tight vertices of are . The matching
lies in : , and none of its edges is . It covers all odd tight vertices except , and its only even endpoint is the slack vertex .
In each case, Corollary 2.3 and Lemma 2.1 give a compatible decomposition of . Adding the -edges assigned to gives a compatible decomposition of the final graph .
Realising the decomposition
Proposition 3.8. Let be the branch set of a strong immersion in . For any perfect matching of and resource sets as above, if has a compatible decomposition, then has a strong immersion with branch set .
Proof. As in [9 Section 3], take
as the branch set, retaining the strong immersion on . Since , join directly to . For , use the edge if it lies in , and otherwise the path
The latter exists by triangle-freeness of and independence of in . Also use every edge of . The remaining pairs are
For , the available resources give paths
or for . Here because .
For a piece of colour , make the following assignments:
(i) For an -edge owned by , delete . Since , the edge has already been used.
(ii) For an -edge , assign and , using and .
(iii) For an -edge with label at , assign , using .
(iv) For an all- odd cycle , assign using for each , with subscripts modulo .
(v) For an path , assign and , using and .
These short paths exist because their internal vertices have label or . Let be the number of deleted resources at , and the number used by short paths starting at a vertex of and ending at . Compatibility gives
Assign the remaining pairs to distinct unused elements of , using the corresponding long paths. Discard unused resources.
We check edge-disjointness by edge type.
(i) Each edge determines a unique resource , used at most once. Its occurrence in (5) requires , whereas a resource path requires .
(ii) An edge can occur in two resource paths only if . Each piece deletes or shortens at least one of , . Its occurrence in (5) is excluded by the same adjacency condition as in (i).
(iii) A short path using uses the pair , so there is at most one such path. If , the same piece assigns the pair a short path, excluding its long path. If , the edge has already been used; if , then . Distinct long paths use distinct pairs .
(iv) Each edge or determines a unique individual resource , used at most once. These edges belong to no other new path.
(v) The old paths use only , which no new path uses. The direct edges from , within , and between and occur in no other path.
Thus the paths are pairwise edge-disjoint. Every new internal vertex lies in , and
Therefore .
Proof of Theorem 3.1. If , the direct edges from to , the edges of , and the paths (5) give a strong immersion. Assume and choose a matching and a normalised selection minimising (4).
If some , Lemma 3.4 gives a choice of , matching and selection for which has a compatible decomposition. Otherwise for every . By Lemma 3.5 and Theorem 1.3, has at most two nontrivial components. Proposition 3.6 applies if it has at most one, or if . In the remaining case, , so and ; Proposition 3.7 applies. Thus in every case a compatible decomposition of exists. Proposition 3.8 completes the proof.
Proof of the main theorem
Proof of Theorem 1.2. Let . Since , the two-vertex colour classes form a matching in , and
We proceed by induction on . The assertion is immediate for . Passing to a vertex-critical induced subgraph with the same chromatic number, assume is vertex-critical. For every ,
Hence in Theorem 1.3, so every component of is factor-critical.
If has components with , then
By induction, . Joining their branch sets by the direct edges between different factors gives .
Assume is connected. Write . Then and . Choose with and a perfect matching of . Define as in Theorem 3.1. Since has a perfect matching,
Induction gives , and Theorem 3.1 gives .
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]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]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]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]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]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]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]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]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]J. C. Dahlke, The Abu-Khzam–Langston conjecture for graphs with α(G) = 2, preprint (2026), arXiv:2605.28159v1.
- [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]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]T. Fleiner, List colourings with restricted lists, EGRES Quick-Proof 2017-01 (2017). https://egres.elte.hu/qp/egresqp-17-01.pdf.
- [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]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]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]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]S. Vergara, Complete graph immersions in dense graphs, Discrete Math. 340 (2017), 1019–1027. doi:10.1016/j.disc.2017.01.001.
- [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