WorksMathematics
Supersaturation and reconfiguration diameter of independent transversals
Abstract
Consider the collection of independent transversals of a vertex-partitioned graph of maximum degree . It is a classic result that when all parts have size at least , the collection is nonempty. Recently, it was found that if the parts have size at least , then every pair of independent transversals is connected, within the collection, by a sequence of one-vertex reconfigurations. We prove, among other results, that there are exponentially many independent transversals when the parts have size at least , and that the reconfiguration diameter is at most linear in the number of parts when the parts have size at least .
Introduction
Given an integer , let be a graph of maximum degree at most . Consider an arbitrary vertex-partition for . An independent transversal of is an independent set of containing exactly one vertex from each part. This is guaranteed to exist, by a result of Haxell [18], if all parts of have size at least . The size-constraint is precisely optimal, in that there are examples of where the parts are only of size for which there is no independent transversal [24] (see also [16]).
Consider the collection of all independent transversals of . How does this collection change as we increase the size-constraint beyond ?
Can we guarantee it has a certain cardinality, as a function of natural parameters in ?
What about changes in the collection’s qualitative structure, such as its topology or geometry?
The result of [18] guarantees only that the cardinality in Question 1 is at least 1 for any size-constraint at least , and so Question 1 constitutes a natural ‘supersaturation’ refinement. To make Question 2 precise, we study the (independent transversal) reconfiguration graph of , which is the graph whose vertices are the independent transversals of and whose edges join two transversals that differ in exactly one part. Under what circumstances is the reconfiguration graph connected, and how small is its diameter? These kinds of questions are relevant for applications to sampling and counting algorithms via Markov chains (see, e.g., [20]).
Buys, Kang, and Ozeki [6] used combinatorial methods to prove that the reconfiguration graph of is connected when every part has size at least . Wdowinski reproved this result within a framework of topological methods [27], analogous to those that were used to prove Haxell’s existence theorem (e.g., [1, 3, 23]). If every part has size exactly , connectivity can fail only if some parts induce disjoint copies of in . Wdowinski [28], resolving a question in [6], exactly characterized which partitions may occur in the exceptional instances. These results give a sharp qualitative picture for connectivity around Haxell’s threshold, while leaving quantitative diameter and supersaturation questions open.
Diameters of reconfiguration graphs
One of our main results provides a linear upper bound on the diameter under the stronger assumption that the parts have size . The diameter bound is sharp due to examples coming from correspondence-colouring reconfiguration [7 Proposition 2(ii)].
Theorem 1. Let be a graph of maximum degree , and let be a partition of such that for every . Then the reconfiguration graph of independent transversals of has diameter at most .
Related diameter questions have been studied before for list colourings, which can be viewed as independent transversals of an auxiliary vertex-partitioned graph, and hence constitute a special case (see [19]). In that setting, a list colouring is already guaranteed to exist when parts have size , and the associated reconfiguration graph is connected when the parts have size at least . At that same threshold of parts of size , Jerrum [20] gave an argument that yields a upper bound on the diameter of the reconfiguration graph, Cereceda [10] improved it to , and finally Cambie, Cames van Batenburg, and Cranston [7] showed that the diameter is at most . See [9, 11] for a generalization to hypergraphs and refinements of this sharp bound.
For general independent transversals, this raises the question of whether the bound in Theorem 1 might still hold close to the connectivity threshold. We show that this is the case asymptotically if the average degree of the vertices in each block is (see Corollary 8), but this still leaves open the general case. Is the diameter still at most , or at least linear in , under the weaker condition that all parts have size at least ? And when the parts have size , does every connected component have diameter ? So far, the best result we know [14] is that when parts have size at least , the diameter is polynomial in for every fixed , but the dependence on in the exponent is huge. In this current work, we show that linear diameter fails below the connectivity threshold, and that connected components can have at least quadratic diameter.
Theorem 2. For every there are infinitely many for which there exists a graph of maximum degree at most , together with a partition of $V(G) into parts each of size $2\Delta - 1$, such that the reconfiguration graph of independent transversals of has a connected component of diameter at least .
Our construction simulates the 3-colouring reconfiguration graph of a path (from [5]) inside the independent transversal reconfiguration graph.
Number of independent transversals
In the direction of counting independent transversals, our next main result is that there exist exponentially many independent transversals when the parts have size , where the exponential dependence is in the number of parts .
Theorem 3. Let be a graph of maximum degree , and let be a partition of such that . Then the number of independent transversals of is at least
Our proof is an interesting application of Lindsey’s edge-isoperimetric inequality [22] on the Hamming graph. Our theorem appears to be the first result demonstrating exponentially many independent transversals at the threshold that works for all values of and .
Exponential lower bounds on the number of independent transversals have previously been obtained through the Lovász Local Lemma and variations of it, but they require larger part sizes. For example, Wanless and Wood [26] proved the existence of at least independent transversals when for all . This was actually shown with the maximum degree replaced by the maximum block average degree of , which is defined as the maximum over all parts of the average degree of the vertices in . In this average degree setting, the part size threshold was shown to be best possible even for the existence of a single independent transversal [13, 17]. And while it is suggestive based on Theorem 1 that the reconfiguration graph of ought to be connected when , that hunch fails spectacularly: It is not hard to construct examples with two parts of arbitrarily large size and such that the independent transversal reconfiguration graph is disconnected.
Another exponential-type lower bound is due to Tang and Zhao [25]. Their main result implies that if for all , then the number of independent transversals is at least , where depends only on . However, they require that be sufficiently large compared to . We are more interested in the situation when is fixed and is growing. Buys, Kang, and Ozeki [6] posed the following conjecture giving a sharp lower bound on the number of independent transversals at Haxell’s theshold . This would be tight by a simple construction (see Example 17).
Conjecture 4. Let be a graph with maximum degree , and let be a partition of with for all . Then the number of independent transversals of is at least .
For comparison, the total number of (not necessarily independent) transversals of is . Our last main result is proving the first non-trivial case of Conjecture 4, namely when $n = 3 ({xref}Theorem 19). Interestingly, while there are various tight constructions for {xref}Conjecture 4 when $n \in \{1,2\}$, we show that the mentioned tight construction ({xref}Example 17`) is unique when , and we conjecture that this is the case for all .
Organization
This paper is organized as follows. In Section 2, we prove Theorem 1 on linear diameter. In § 3, we prove Theorem 2 on quadratic diameter components. In § 4, we prove Theorem 3 as well as a more elementary result coming from double-counting. In § 5, we prove Conjecture 4 when .
Linear diameter when parts have size
In this section, we prove Theorem 1 demonstrating that the reconfiguration graph of has linear diameter when the parts of have size at least . Before that, let us recall Haxell’s Theorem [18, 19].
Theorem 5 (Haxell [18, 19]). Let be a graph of maximum degree at most with a vertex partition . If for every , then has an independent transversal. In fact, every vertex is contained in some independent transversal.
Theorem 1 will be a direct corollary of Theorem 5 and the following theorem, which more generally provides a linear upper bound on the diameter under the condition that the existence of an independent transversal is sufficiently robust under vertex removal.
Theorem 6. Let be a graph with maximum degree at most and let be a partition of into parts. Suppose that whenever one removes at most vertices from each part of , the resulting induced subgraph and vertex partition has an independent transversal. Then the reconfiguration graph of independent transversals of has diameter at most .
Proof. Let and be two independent transversals of . We will show that . Essentially, the proof proceeds by finding some suitable independent transversal such that both and can be reconfigured to in at most steps. We construct an ordering of the parts , together with large subsets , with the ordering chosen so that every vertex of avoids all vertices and appearing later than in the order . We construct greedily.
Suppose that is the set of indices of parts that are not yet ordered. For , define
Thus is the set of vertices in blocked by the still-unordered vertices of and . Since
some satisfies
Put this part next in the order , and define . Then
It follows from the hypothesis of Theorem 6 that the graph induced by has an independent transversal . Moreover, by construction, every vertex of is nonadjacent to every and whose part appears after in the order .
We now show that can be reconfigured to in at most steps. We reconfigure the parts in the order . Suppose we are reconfiguring the part . At this moment, the parts earlier than in have already been changed to their vertices of , while the parts later than in are still at their vertices of . We now reconfigure to . This is allowed because:
is nonadjacent to all earlier vertices of , since is independent; and
is nonadjacent to all later vertices of , since .
By the same argument, the transversal can be reconfigured to in at most steps according to the same order . This already gives that . However, we can do slightly better. Let be the index whose part comes last in the order . As above we reconfigure and to according to order , except we do not yet execute the last reconfiguration, from to and from to . Instead we can then finish by directly reconfiguring to , saving one reconfiguration step. □
As another application of Theorem 6, we prove Corollary 8 below, showing that we have linear diameter whenever the parts have size , under the additional assumption that the maximum block average degree of is . Recall that the maximum block average degree of is defined as . In place of Haxell’s Theorem 5, we use the following theorem that comes from variations of the Lovász Local Lemma [21, 26] (see also [4]).
Theorem 7 (Kang, Kelly [21]; Wanless, Wood [26]). Let be a graph and let be a vertex partition. If has maximum block average degree and for every , then has an independent transversal.
Corollary 8. Let be a graph of maximum degree and maximum block average degree , together with a vertex partition such that for every . Then the reconfiguration graph of independent transversals of has diameter at most .
Proof. We verify the hypothesis of Theorem 6. Let be obtained from by deleting at most vertices from each part, and put for every . Then . Let be the maximum block average degree of , say that the average degree is maximised at . Since , we have
Hence for every . By Theorem 7, it follows that has an independent transversal. Therefore, Theorem 6 applies to give the diameter result. □
Remark 9. Due to the construction in [7 Proposition 2(ii)], for every and there exist examples of graphs with maximum degree and a partition where for all and the reconfiguration graph of has diameter at least . Thus the upper bound in Theorem 1 is sharp for all values of .
Remark 10. If the parts have size , then there exists at least one “unfrozen” part. More precisely: Suppose and for all . Given independent transversals and , say that is -unfrozen if some satisfies and . Suppose for a contradiction that no such exists for any . Then with and , we have for all . Since and , it follows that , contradiction. So there must exist some -unfrozen part . This could be a somewhat desirable property for a potential proof by induction, because it means that can be reconfigured to without being blocked by either or .
Quadratic diameter components when parts have size
In this section, we prove Theorem 2. When the parts of a partition have size less than , there might not be an independent transversal, and if there does exist one, the reconfiguration graph may not be connected. However, here we zoom in on the situation that the reconfiguration graph is nonempty, and we ask how large the maximum diameter among all connected components can be. We show that it can be at least . We use the following result as input.
Theorem 11 (Bonamy, Johnson, Lignos, Patel, Paulusma [5]). For every , the 3-colouring reconfiguration graph of the -vertex path has diameter at least .
The idea of the construction of in the proof of Theorem 2 is to “simulate” the 3-colour reconfiguration graph of an -vertex path on vertices, by forcing it to occur as an induced subgraph of the reconfiguration graph of . This is inspired by [8 Lemma 17], where a very different simulation of was used for list-colouring reconfiguration. The construction is illustrated in Figure 1.

Figure 1. Illustration of the construction in Theorem 2. The big blue boxes depict the main parts ; they contain dummy sets of size 2, as well as a triple of three vertices that represent the three possible colours of the -th vertex of the path . The green boxes depict the auxiliary parts , split into , , and sets. The thick edges indicate a complete bipartite graph. The thin edges depict the path edges, which can be viewed as the edges between equal colours of adjacent vertices of .
Proof of Theorem 2. Put and let be a positive integer. Partition will have parts.
We first build main parts . Each main part consists of a core set and dummy sets , , each of size 2. Thus .
For each dummy set , we introduce an auxiliary part . This part is split into three sets
where , , and . Hence every auxiliary part also has size . The partition is
We now define the edges. First, between consecutive main parts, add the path edges for every and . Second, make complete to , for every . Third, make complete to , for every . Finally, cyclically order all pairs , and for every , make complete to , where is the successor of in this cyclic order. (We note in passing that it is not essential to do this via a cyclic order; the only important thing is that each is made complete to some unique with .) There are no other edges.
We first check the maximum degree. A vertex in has at most two path-neighbours and is adjacent to the unique vertex of for each , so its degree is at most . A vertex in is adjacent to the two vertices of and to the vertices of the unique -set made complete to , so its degree is exactly . The unique vertex of has degree 3, and every vertex in a dummy set or has degree exactly . Hence .
Call an independent transversal core if it chooses a vertex from in every main part , and a vertex from in every auxiliary part . The crucial claim is that every core transversal can only be reconfigured to another core transversal. Indeed, in a core transversal, each vertex of is blocked by the selected vertex of . The unique vertex of is blocked by the selected vertex of . Finally, every vertex of is blocked by the selected vertex of . Therefore the core transversals form a closed union of connected components.
Inside the core transversals, the choices in the main parts are exactly proper 3-colourings of a path on vertices: choosing corresponds to giving colour to the -th path vertex, and the edges forbid equal colours on consecutive path vertices. The auxiliary parts impose no further restrictions on these path choices, because there is no edge between the cores of the main parts and the cores of the auxiliary parts.
It follows that the reconfiguration graph of contains a copy of the 3-colour reconfiguration graph of the path as an induced subgraph, and moreover any shortest path between two vertices of is also a shortest path in . In particular, the diameter of the connected component of containing is at least the diameter of . By Theorem 11, has diameter . Plugging in yields the result. □
Exponentially many independent transversals
In this section, we prove Theorem 3, demonstrating the existence of exponentially many independent transversals when parts have size . We prove it in a more general form involving arbitrary part sizes (see Theorem 15).
For a graph and vertex partition , the number of independent transversals of is denoted by .
Double counting argument
Before proving Theorem 3, in this subsection we give an elementary double-counting argument demonstrating exponentially many independent transversals when parts have size . This is an adaptation of a folklore proof for showing the existence of exponentially many (list) colourings of graphs.
Proposition 12. Let be a graph of maximum degree , and let be a partition of with for all . Then
In particular, if for every , then
Proof. For each , choose a subset with . Write . The induced subgraph has maximum degree at most , and its vertex set is partitioned into . By Haxell’s theorem, every such choice of has at least independent transversals. Let be the set of pairs where with and for every , and where is an independent transversal of . We will double count .
First count by starting from a fixed choice of . There are choices for , each of which has at least independent transversals, so .
Now count by starting from some fixed choice of independent transversal of . For to be an independent transversal of , each must contain the unique vertex of . After this vertex has been included, the remaining vertices of may be chosen arbitrarily from the other vertices of . Hence, the number of choices of compatible with is . Thus , where .
Combining the two estimates yields . Therefore,
as required.
The above proposition and proof, though not fully optimized, easily adapt to other settings. For example, if is a chordal graph, then a result of Aharoni, Berger, and Ziv [2] guarantees that every vertex lies in an independent transversal whenever for every . The above proof then yields that, when is chordal and for every , we have .
We also mention that when is relatively small ( or smaller), then we obtain a better lower bound on by applying the above proof on another refined version of Haxell’s Theorem 5, due to Haxell and Szabó [15], stated below.
Theorem 13 (Haxell, Szabó [15]). Let be a graph of maximum degree at most with a vertex partition . Then has an independent transversal whenever
for every , if is even;
for every , if is odd.
However, the resulting lower bound is superseded by the following theorem, mentioned in the Introduction, of Tang and Zhao [25] when is even and is sufficiently large.
Theorem 14 (Tang, Zhao [25]). For any even integer , there exist and such that whenever and and , the following holds. If is a graph of maximum degree , is a partition of , and for every , then
In particular:
For any even and sufficiently large , if for every , then .
For any and sufficiently large , if for every , then for some constant depending only on .
Isoperimetric approach
In this subsection, we prove the following more general version of Theorem 3, as an application of edge-isoperimetric inequalities.
Theorem 15. Let be a graph of maximum degree , and let be a partition of . For every integer satisfying , we have
In particular:
If for every , then .
If for every , then .
The basic idea is to view our reconfiguration graph on independent transversals as a subgraph of the Hamming graph, show that it induces many edges, and thus by isoperimetric inequalities deduce that it has many vertices.
For integers , the -ary -dimensional Hamming graph has vertex set , with two words in connected by an edge if they differ in exactly one coordinate. We use the following formulation of Lindsey’s edge-isoperimetric inequality on the Hamming graph [22] (see also inequality (3) in [12], from which it easily follows).
Lemma 16. For any vertex subset of the Hamming graph , with and , the number of edges induced by is at most
Proof of Theorem 15. We prove the stated lower bound when every part has size exactly , where the claimed lower bound is . To get the statement for general part sizes , we then apply the same double counting argument as in Proposition 12.
Identify each part with the set in arbitrary fashion, and let represent the family of independent transversals of under these identifications. We view as a vertex subset of the Hamming graph . Since , Haxell’s Theorem 5 gives .
Fix an independent transversal , with for every , identified as vertices of . Define the set . Every vertex in has a neighbour in , which implies that . Thus, the degree of in the subgraph of induced by satisfies
Since was an arbitrary vertex in , we get that the number of edges induced by in is at least . Combining this with Lemma 16 gives , and therefore
as required. □
Conjecture 4 for small number of parts
In this section, we prove the first few cases of Conjecture 4, namely when . Recall that denotes the number of independent transversals of , and recall that Conjecture 4 of Buys, Kang, and Ozeki [6] states that, if for all , then
This lower bound would be best possible, as it is attained by the following basic cyclic construction, a special case of Wdowinski’s characterization [28] of when the reconfiguration graph of is disconnected.
Example 17. Let be disjoint copies of , where has bipartition . Let , and let consist of for every (where ). Then every independent transversal of is either a transversal of or a transversal of , and there are such transversals.
Observe that Conjecture 4 trivially holds when , with equality. Next, it is straightforward to show that the conjecture holds when , although in this case the cyclic construction of Example 17 is not the unique minimizer.
Proposition 18. Let be a graph of maximum degree and let vertex partition satisfy . Then , and equality holds if and only if and is a -regular bipartite graph with bipartition .
Proof. The independent transversals of consist of a vertex together with a non-neighbour of in . Every vertex in has at least non-neighbours in , so all together there are at least independent transversals of . Equality holds if and only if and every vertex of has exactly neighbours in . In this case, is a -regular bipartite graph with bipartition .
Our next goal is to prove the conjecture for , and demonstrate that the described cyclic construction of Example 17 is indeed the unique minimizer of .
Theorem 19. Let be a graph of maximum degree and let vertex partition satisfy . Then , and equality holds if and only if is a cyclic construction of the form described in Example 17.
We prove Theorem 19 using the following lemma, which comes from an inclusion-exclusion argument. Recall that a transversal of partition is a set with one element from each part of .
Lemma 20. For a graph and partition of with for all , we have
Proof. For an arbitrary transversal , with for all , let be the indicator variable for inducing an edge. Then is an independent transversal of precisely when
equals 1, and otherwise equals 0. Thus, the number of independent transversals of is
For a fixed transversal , we expand the associated product as
Summing over all , the first term becomes , the number of transversals of . The second term becomes because a given edge lies in transversals . (1) becomes
where the last inequality uses that . This gives the required result.
Proof of Theorem 19. The lower bound comes directly from Lemma 20 by plugging in and (the last sum is always nonnegative). Equality holds if and only if is -regular and for every transversal of , and each is an independent set. In this case, we have that the non-neighbours of inside form a -regular bipartite subgraph of with bipartition (inherited from) . Since , there are at most non-neighbours of inside . Hence by -regularity these non-neighbours must induce a . This then implies that . Moreover, is an independent set, and no vertex in can have neighbours in both and (by for every transversal ). From these, we obtain that and contain vertex-disjoint induced copies of , with those bipartitions. This gives the cyclic construction .
Declaration of use of AI
The majority of this work was done in May, June and July 2026. For Theorems 15 and 19, the main ideas were originally found through multiple queries of ChatGPT-5.5. The authors verified, cleaned up, and generalized the details. ChatGPT-5.5 was also used for initial versions of Figure 1.
Acknowledgments
We would like to thank Pjotr Buys, Carla Groenland, and Jan van den Heuvel for fruitful discussions. This project started during the “Phase Transitions in Combinatorics, Algorithms, Probability” (PhaseCAP) Research Semester Programme at CWI in 2026. W.CvB. was supported by the Belgian National Fund for Scientific Research (FNRS). P.H. was partially supported by NSERC as well as the CWI Visiting Programme. R.J.K. was partially supported by the Dutch Research Council (NWO) grants OCENW.M20.009 and OCENW.M.25.085. R.W. was supported in part by the Austrian Science Fund (FWF) [10.55776/F1002]. For open access purposes, the authors have applied a CC BY public copyright license to any author accepted manuscript version arising from this submission.
References
- [1]R. Aharoni and E. Berger. The intersection of a matroid and a simplicial complex. Transactions of the American Mathematical Society, 358(11):4895–4918, 2006. doi:10.1090/S0002-9947-06-03333-5.DOI
- [2]R. Aharoni, E. Berger, and R. Ziv. A tree version of König’s theorem. Combinatorica, 22(3):335–343, 2002. doi:10.1007/s004930200016.DOI
- [3]R. Aharoni, E. Berger, and R. Ziv. Independent systems of representatives in weighted graphs. Combinatorica, 27(3):253–267, 2007. doi:10.1007/s00493-007-2086-y.DOI
- [4]R. Bissacot, R. Fernández, A. Procacci, and B. Scoppola. An improvement of the Lovász local lemma via cluster expansion. Combinatorics, Probability and Computing, 20(5):709–719, 2011. doi:10.1017/S0963548311000253.DOI
- [5]M. Bonamy, M. Johnson, I. Lignos, V. Patel, and D. Paulusma. On the diameter of reconfiguration graphs for vertex colourings. Electronic Notes in Discrete Mathematics, 38:161–166, 2011. doi:10.1016/j.endm.2011.09.028.DOI
- [6]P. Buys, R. J. Kang, and K. Ozeki. Reconfiguration of independent transversals. Random Structures & Algorithms, 67(1), 2025, arXiv:2407.04367. doi:10.1002/rsa.70025.DOI
- [7]S. Cambie, W. Cames van Batenburg, and D. W. Cranston. Optimally reconfiguring list and correspondence colourings. European Journal of Combinatorics, 115:103798, 2024, arXiv:2204.07928. doi:10.1016/j.ejc.2023.103798.DOI
- [8]S. Cambie, W. Cames van Batenburg, and D. W. Cranston. Sharp bounds on lengths of linear recolouring sequences. The Electronic Journal of Combinatorics, 33(1), 2026. doi:10.37236/13788.DOI
- [9]W. Cames van Batenburg. Large diameter for (Δ + 2)-colouring reconfiguration, 2026, arXiv:2611.17022. doi:10.48550/arXiv.2611.17022.arxiv.org/abs/2611.17022
- [10]L. Cereceda. Mixing Graph Colourings. PhD thesis, London School of Economics and Political Science, 2007.
- [11]L. De Meyer. Optimal list recoloring of subcubic graphs and complete multipartite graphs. Discrete Mathematics, 349(8):115155, 2026. doi:10.1016/j.disc.2026.115155.DOI
- [12]S. Diskin and W. Samotij. Isoperimetry in product graphs. The Electronic Journal of Combinatorics, 32(3):P3.12, 2025. doi:10.37236/13585.DOI
- [13]C. Groenland, T. Kaiser, O. Treffers, and M. Wales. Graphs of low average degree without independent transversals. Journal of Graph Theory, 102(2):374–387, 2023. doi:10.1002/jgt.22876.DOI
- [14]S. Hajebi and P. Haxell. Efficient reconfiguration of independent transversals, 2026, arXiv:2611.18474. doi:10.48550/arXiv.2611.18474.arxiv.org/abs/2611.18474
- [15]P. Haxell and T. Szabó. Odd independent transversals are odd. Combinatorics, Probability and Computing, 15(1-2):193–211, 2006. doi:10.1017/S0963548305007157.DOI
- [16]P. Haxell and R. Wdowinski. Constructing graphs with no independent transversals. Electron. J. Combin., 31(2):P2–39, 2024. doi:10.37236/12429.DOI
- [17]P. Haxell and R. Wdowinski. Degree criteria and stability for independent transversals. J. Graph Theory, 106(2):352–371, 2024. doi:10.1002/jgt.23085.DOI
- [18]P. E. Haxell. A condition for matchability in hypergraphs. Graphs and Combinatorics, 11(3):245–248, 1995. doi:10.1007/BF01793010.DOI
- [19]P. E. Haxell. A note on vertex list colouring. Combinatorics, Probability and Computing, 10(4):345–347, 2001. doi:10.1017/S0963548301004758.DOI
- [20]M. Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structures Algorithms, 7(2):157–165, 1995. doi:10.1002/rsa.3240070205.DOI
- [21]R. J. Kang and T. Kelly. Colorings, transversals, and local sparsity. Random Structures & Algorithms, 61(1):173–192, 2022. doi:10.1002/rsa.21051.DOI
- [22]J. H. Lindsey. Assignment of numbers to vertices. The American Mathematical Monthly, 71(5):508–516, 1964. doi:10.1080/00029890.1964.11992272.DOI
- [23]R. Meshulam. Domination numbers and homology. Journal of Combinatorial Theory, Series A, 102(2):321–330, 2003. doi:10.1016/S0097-3165(03)00045-1.DOI
- [24]T. Szabó and G. Tardos. Extremal problems for transversals in graphs with bounded degree. Combinatorica, 26(3):333–351, 2006. doi:10.1007/s00493-006-0019-9.DOI
- [25]Y. Tang and Y. Zhao. Number of independent transversals in multipartite graphs, 2025, arXiv:2504.03950. doi:10.48550/arXiv.2504.03950.DOI
- [26]I. M. Wanless and D. R. Wood. A general framework for hypergraph coloring. SIAM Journal on Discrete Mathematics, 36(3):1663–1677, 2022. doi:10.1137/21M1421015.DOI
- [27]R. Wdowinski. Hall’s theorem for reconfigurations and higher dimensional topological connectedness, 2025, arXiv:2511.04863. doi:10.48550/arXiv.2511.04863.DOI
- [28]R. Wdowinski. Tight constructions for reconfigurations of independent transversals, 2026, arXiv:2604.21576. doi:10.48550/arXiv.2604.21576.DOI