Ross J. Kang
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Ross J. Kang has a total of 90 co-authors. Here are the top co-authors by number of shared publications:
- Stijn Cambie
Department of Computer Science KU Leuven Campus Kulak‐Kortrijk Kortrijk Belgium
17 shared publications - François Pirot
Department of Mathematics Radboud University Nijmegen Netherlands
13 shared publications - Wouter Cames van Batenburg
Département d'Informatique Université libre de Bruxelles Brussels Belgium
13 shared publications Rémi de Joannis de Verclos
Department of Mathematics Radboud University Nijmegen Nijmegen The Netherlands
7 shared publications- Rémi de Joannis de Verclos
Department of Mathematics Radboud University Nijmegen Netherlands
7 shared publications - António Girão
School of Mathematics University of Birmingham Edgbaston B15 2TT Birmingham United Kingdom
6 shared publications
Latest Publications
- Open Access
- 3 October 2025
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 32 (4) , P4.3
On Vizing’s Problem for Triangle-Free Graphs
We prove that $\chi(G) \le \lceil (\Delta+1)/2\rceil+1$ for any triangle-free graph $G$ of maximum degree $\Delta$ provided $\Delta \ge 524$. This gives tangible progress towards an old problem of Vizing, in a form cast by Reed. We use a method of Hurley and Pirot, which in turn relies on a new counting argument of the second author.- 3 October 2025
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 32 (4) , P4.3
Open AccessOn Vizing’s Problem for Triangle-Free Graphs
We prove that $\chi(G) \le \lceil (\Delta+1)/2\rceil+1$ for any triangle-free graph $G$ of maximum degree $\Delta$ provided $\Delta \ge 524$. This gives tangible progress towards an old problem of Vizing, in a form cast by Reed. We use a method of Hurley and Pirot, which in turn relies on a new counting argument of the second author. - Open Access
- 4 June 2025
- Published by Springer Nature in Acta Mathematica Hungarica
- Vol. 176 (1) , 183-214
Largest component in Boolean sublattices
For a subfamily $$\mathcal{F}\subseteq 2^{[n]}$$ of the Boolean lattice, consider the graph $$G_\mathcal{F}$$ on $$\mathcal{F}$$ based on the pairwise inclusion relations among its members. Given a positive integer t, how large can $$\mathcal{F}$$ be before $$G_\mathcal{F}$$ must contain some component of order greater than t? For t = 1, this question was answered exactly almost a century ago by Sperner: the size of a middle layer of the Boolean lattice. For t = 2 n , this question is trivial. We are interested in what happens between these two extremes. For t = 2 g with g = g(n) being any integer function that satisfies $$g(n)=o(n/\log n)$$ as $$n\to\infty$$ , we give an asymptotically sharp answer to the above question: not much larger than the size of a middle layer. This constitutes a nontrivial generalisation of Sperner's theorem. We do so by a reduction to a Turán-type problem for rainbow cycles in properly edge-coloured graphs. Among other results, we also give a sharp answer to the question, how large can $$\mathcal{F}$$ be before $$G_\mathcal{F}$$ must be connected?- 4 June 2025
- Published by Springer Nature in Acta Mathematica Hungarica
- Vol. 176 (1) , 183-214
Open AccessLargest component in Boolean sublattices
For a subfamily $$\mathcal{F}\subseteq 2^{[n]}$$ of the Boolean lattice, consider the graph $$G_\mathcal{F}$$ on $$\mathcal{F}$$ based on the pairwise inclusion relations among its members. Given a positive integer t, how large can $$\mathcal{F}$$ be before $$G_\mathcal{F}$$ must contain some component of order greater than t? For t = 1, this question was answered exactly almost a century ago by Sperner: the size of a middle layer of the Boolean lattice. For t = 2 n , this question is trivial. We are interested in what happens between these two extremes. For t = 2 g with g = g(n) being any integer function that satisfies $$g(n)=o(n/\log n)$$ as $$n\to\infty$$ , we give an asymptotically sharp answer to the above question: not much larger than the size of a middle layer. This constitutes a nontrivial generalisation of Sperner's theorem. We do so by a reduction to a Turán-type problem for rainbow cycles in properly edge-coloured graphs. Among other results, we also give a sharp answer to the question, how large can $$\mathcal{F}$$ be before $$G_\mathcal{F}$$ must be connected? - Open Access
- 17 May 2025
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 74 (3) , 758-770
The $\chi $-Binding Function of d-Directional Segment GraphsGiven a positive integer d, the class d-DIR is defined as all those intersection graphs formed from a finite collection of line segments in $${\mathbb R}^2$$ having at most d slopes. Since each slope induces an interval graph, it easily follows for every G in d-DIR with clique number at most $$\omega $$ that the chromatic number $$\chi (G)$$ of G is at most $$d\omega $$ . We show for every even value of $$\omega $$ how to construct a graph in d-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvořák and Noorizadeh. Furthermore, we show that the $$\chi $$ -binding function of d-DIR is $$\omega \mapsto d\omega $$ for $$\omega $$ even and $$\omega \mapsto d(\omega -1)+1$$ for $$\omega $$ odd. This extends an earlier result by Kostochka and Nešetřil, which treated the special case $$d=2$$ .- 17 May 2025
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 74 (3) , 758-770
Open AccessThe $\chi $-Binding Function of d-Directional Segment GraphsGiven a positive integer d, the class d-DIR is defined as all those intersection graphs formed from a finite collection of line segments in $${\mathbb R}^2$$ having at most d slopes. Since each slope induces an interval graph, it easily follows for every G in d-DIR with clique number at most $$\omega $$ that the chromatic number $$\chi (G)$$ of G is at most $$d\omega $$ . We show for every even value of $$\omega $$ how to construct a graph in d-DIR that meets this bound exactly. This partially confirms a conjecture of Bhattacharya, Dvořák and Noorizadeh. Furthermore, we show that the $$\chi $$ -binding function of d-DIR is $$\omega \mapsto d\omega $$ for $$\omega $$ even and $$\omega \mapsto d(\omega -1)+1$$ for $$\omega $$ odd. This extends an earlier result by Kostochka and Nešetřil, which treated the special case $$d=2$$ . - Open Access
Reconfiguration of List Colourings
Given a proper (list) colouring of a graph $G$, a recolouring step changes the colour at a single vertex to another colour (in its list) that is currently unused on its neighbours, hence maintaining a proper colouring. Suppose that each vertex $v$ has its own private list $L(v)$ of allowed colours such that $|L(v)|\ge \mbox{deg}(v)+1$. We prove that if $G$ is connected and its maximum degree $Δ$ is at least $3$, then for any two proper $L$-colourings in which at least one vertex can be recoloured, one can be transformed to the other by a sequence of $O(|V(G)|^2)$ recolouring steps. We also show that reducing the list-size of a single vertex $w$ to $\mbox{deg}(w)$ can lead to situations where the space of proper $L$-colourings is `shattered'. Our results can be interpreted as showing a sharp phase transition in the Glauber dynamics of proper $L$-colourings of graphs. This constitutes a `local' strengthening and generalisation of a result of Feghali, Johnson, and Paulusma, which considered the situation where the lists are all identical to $\{1,\ldots,Δ+1\}$.Open AccessReconfiguration of List Colourings
Given a proper (list) colouring of a graph $G$, a recolouring step changes the colour at a single vertex to another colour (in its list) that is currently unused on its neighbours, hence maintaining a proper colouring. Suppose that each vertex $v$ has its own private list $L(v)$ of allowed colours such that $|L(v)|\ge \mbox{deg}(v)+1$. We prove that if $G$ is connected and its maximum degree $Δ$ is at least $3$, then for any two proper $L$-colourings in which at least one vertex can be recoloured, one can be transformed to the other by a sequence of $O(|V(G)|^2)$ recolouring steps. We also show that reducing the list-size of a single vertex $w$ to $\mbox{deg}(w)$ can lead to situations where the space of proper $L$-colourings is `shattered'. Our results can be interpreted as showing a sharp phase transition in the Glauber dynamics of proper $L$-colourings of graphs. This constitutes a `local' strengthening and generalisation of a result of Feghali, Johnson, and Paulusma, which considered the situation where the lists are all identical to $\{1,\ldots,Δ+1\}$. - Open Access
Triangle-free graphs with the fewest independent sets
Given $d>0$ and a positive integer $n$, let $G$ be a triangle-free graph on $n$ vertices with average degree $d$. With an elegant induction, Shearer (1983) tightened a seminal result of Ajtai, Komlós and Szemerédi (1980/1981) by proving that $G$ contains an independent set of size at least $(1+o(1))\frac{\log d}{d}n$ as $d\to\infty$. By a generalisation of Shearer's method, we prove that the number of independent sets in $G$ must be at least $\exp\left((1+o(1))\frac{(\log d)^2}{2d}n\right)$ as $d\to\infty$. This improves upon results of Cooper and Mubayi (2014) and Davies, Jenssen, Perkins, and Roberts (2018). Our method also provides good lower bounds on the independence polynomial of $G$, one of which implies Shearer's result itself. As certified by a classic probabilistic construction, our bound on the number of independent sets is sharp to several leading terms as $d\to\infty$.Open AccessTriangle-free graphs with the fewest independent sets
Given $d>0$ and a positive integer $n$, let $G$ be a triangle-free graph on $n$ vertices with average degree $d$. With an elegant induction, Shearer (1983) tightened a seminal result of Ajtai, Komlós and Szemerédi (1980/1981) by proving that $G$ contains an independent set of size at least $(1+o(1))\frac{\log d}{d}n$ as $d\to\infty$. By a generalisation of Shearer's method, we prove that the number of independent sets in $G$ must be at least $\exp\left((1+o(1))\frac{(\log d)^2}{2d}n\right)$ as $d\to\infty$. This improves upon results of Cooper and Mubayi (2014) and Davies, Jenssen, Perkins, and Roberts (2018). Our method also provides good lower bounds on the independence polynomial of $G$, one of which implies Shearer's result itself. As certified by a classic probabilistic construction, our bound on the number of independent sets is sharp to several leading terms as $d\to\infty$. - Open Access
Reconfiguration of Independent Transversals
Given integers $Δ\ge 2$ and $t\ge 2Δ$, suppose there is a graph of maximum degree $Δ$ and a partition of its vertices into blocks of size at least $t$. By a seminal result of Haxell, there must be some independent set of the graph that is transversal to the blocks, a so-called independent transversal. We show that, if moreover $t\ge2Δ+1$, then every independent transversal can be transformed within the space of independent transversals to any other through a sequence of one-vertex modifications, showing connectivity of the so-called reconfigurability graph of independent transversals. This is sharp in that for $t=2Δ$ (and $Δ\ge 2$) the connectivity conclusion can fail. In this case we show furthermore that in an essential sense it can only fail for the disjoint union of copies of the complete bipartite graph $K_{Δ,Δ}$. This constitutes a qualitative strengthening of Haxell's theorem.Open AccessReconfiguration of Independent Transversals
Given integers $Δ\ge 2$ and $t\ge 2Δ$, suppose there is a graph of maximum degree $Δ$ and a partition of its vertices into blocks of size at least $t$. By a seminal result of Haxell, there must be some independent set of the graph that is transversal to the blocks, a so-called independent transversal. We show that, if moreover $t\ge2Δ+1$, then every independent transversal can be transformed within the space of independent transversals to any other through a sequence of one-vertex modifications, showing connectivity of the so-called reconfigurability graph of independent transversals. This is sharp in that for $t=2Δ$ (and $Δ\ge 2$) the connectivity conclusion can fail. In this case we show furthermore that in an essential sense it can only fail for the disjoint union of copies of the complete bipartite graph $K_{Δ,Δ}$. This constitutes a qualitative strengthening of Haxell's theorem. - 6 May 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 38 (2) , 1451-1461
A Precise Condition for Independent Transversals in Bipartite Covers
Given a bipartite graph [Formula: see text] in which any vertex in [Formula: see text] (resp., [Formula: see text]) has degree at most [Formula: see text] (resp., [Formula: see text]), suppose there is a partition of [Formula: see text] that is a refinement of the bipartition [Formula: see text] such that the parts in [Formula: see text] (resp., [Formula: see text]) have size at least [Formula: see text] (resp., [Formula: see text]). We prove that the condition [Formula: see text] is sufficient for the existence of an independent set of vertices of [Formula: see text] that is simultaneously transversal to the partition and show, moreover, that this condition is sharp. This result is a bipartite refinement of two well-known results on independent transversals, one due to the second author and the other due to Szabó and Tardos.
- 6 May 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 38 (2) , 1451-1461
A Precise Condition for Independent Transversals in Bipartite Covers
Given a bipartite graph [Formula: see text] in which any vertex in [Formula: see text] (resp., [Formula: see text]) has degree at most [Formula: see text] (resp., [Formula: see text]), suppose there is a partition of [Formula: see text] that is a refinement of the bipartition [Formula: see text] such that the parts in [Formula: see text] (resp., [Formula: see text]) have size at least [Formula: see text] (resp., [Formula: see text]). We prove that the condition [Formula: see text] is sufficient for the existence of an independent set of vertices of [Formula: see text] that is simultaneously transversal to the partition and show, moreover, that this condition is sharp. This result is a bipartite refinement of two well-known results on independent transversals, one due to the second author and the other due to Szabó and Tardos.
- Open Access
A precise condition for independent transversals in bipartite covers
Given a bipartite graph $H=(V=V_A\cup V_B,E)$ in which any vertex in $V_A$ (resp.~$V_B$) has degree at most $D_A$ (resp.~$D_B$), suppose there is a partition of $V$ that is a refinement of the bipartition $V_A\cup V_B$ such that the parts in $V_A$ (resp.~$V_B$) have size at least $k_A$ (resp.~$k_B$). We prove that the condition $D_A/k_B+D_B/k_A\le 1$ is sufficient for the existence of an independent set of vertices of $H$ that is simultaneously transversal to the partition, and show moreover that this condition is sharp. This result is a bipartite refinement of two well-known results on independent transversals, one due to the second author and the other due to Szabó and Tardos.Open AccessA precise condition for independent transversals in bipartite covers
Given a bipartite graph $H=(V=V_A\cup V_B,E)$ in which any vertex in $V_A$ (resp.~$V_B$) has degree at most $D_A$ (resp.~$D_B$), suppose there is a partition of $V$ that is a refinement of the bipartition $V_A\cup V_B$ such that the parts in $V_A$ (resp.~$V_B$) have size at least $k_A$ (resp.~$k_B$). We prove that the condition $D_A/k_B+D_B/k_A\le 1$ is sufficient for the existence of an independent set of vertices of $H$ that is simultaneously transversal to the partition, and show moreover that this condition is sharp. This result is a bipartite refinement of two well-known results on independent transversals, one due to the second author and the other due to Szabó and Tardos. - Open Access
- 1 December 2023
- Published by The Company of Biologists in Journal of Cell Science
- Vol. 136 (23)
Cell jamming in a collagen-based interface assay is tuned by collagen density and proteolysis
Tumor cell invasion into heterogenous interstitial tissues consisting of network-, channel- or rift-like architectures involves both matrix metalloproteinase (MMP)-mediated tissue remodeling and cell shape adaptation to tissue geometry. Three-dimensional (3D) models composed of either porous or linearly aligned architectures have added to the understanding of how physical spacing principles affect migration efficacy; however, the relative contribution of each architecture to decision making in the presence of varying MMP availability is not known. Here, we developed an interface assay containing a cleft between two high-density collagen lattices, and we used this assay to probe tumor cell invasion efficacy, invasion mode and MMP dependence in concert. In silico modeling predicted facilitated cell migration into confining clefts independently of MMP activity, whereas migration into dense porous matrix was predicted to require matrix degradation. This prediction was verified experimentally, where inhibition of collagen degradation was found to strongly compromise migration into 3D collagen in a density-dependent manner, but interface-guided migration remained effective, occurring by cell jamming. The 3D interface assay reported here may serve as a suitable model to better understand the impact of in vivo-relevant interstitial tissue topologies on tumor invasion patterning and responses to molecular interventions.
- 1 December 2023
- Published by The Company of Biologists in Journal of Cell Science
- Vol. 136 (23)
Open AccessCell jamming in a collagen-based interface assay is tuned by collagen density and proteolysis
Tumor cell invasion into heterogenous interstitial tissues consisting of network-, channel- or rift-like architectures involves both matrix metalloproteinase (MMP)-mediated tissue remodeling and cell shape adaptation to tissue geometry. Three-dimensional (3D) models composed of either porous or linearly aligned architectures have added to the understanding of how physical spacing principles affect migration efficacy; however, the relative contribution of each architecture to decision making in the presence of varying MMP availability is not known. Here, we developed an interface assay containing a cleft between two high-density collagen lattices, and we used this assay to probe tumor cell invasion efficacy, invasion mode and MMP dependence in concert. In silico modeling predicted facilitated cell migration into confining clefts independently of MMP activity, whereas migration into dense porous matrix was predicted to require matrix degradation. This prediction was verified experimentally, where inhibition of collagen degradation was found to strongly compromise migration into 3D collagen in a density-dependent manner, but interface-guided migration remained effective, occurring by cell jamming. The 3D interface assay reported here may serve as a suitable model to better understand the impact of in vivo-relevant interstitial tissue topologies on tumor invasion patterning and responses to molecular interventions.
- Open Access
- 28 August 2023
- Published by Masaryk University Press in European Conference on Combinatorics, Graph Theory and Applications
- No. 12,p. 263-269
A precise condition for independent transversals in bipartite covers
Given a bipartite graph $H=(V=V_A\cup V_B,E)$ in which any vertex in $V_A$ (resp. $V_B$) has degree at most $D_A$ (resp. $D_B$), suppose there is a partition of $V$ that is a refinement of the bipartition $V_A\cup V_B$ such that the parts in $V_A$ (resp. $V_B$) have size at least $k_A$ (resp. $k_B$). We prove that the condition $D_A/k_A+D_B/k_B\le 1$ is sufficient for the existence of an independent set of vertices of $H$ that is simultaneously transversal to the partition, and show moreover that this condition is sharp.- 28 August 2023
- Published by Masaryk University Press in European Conference on Combinatorics, Graph Theory and Applications
- No. 12,p. 263-269
Open AccessA precise condition for independent transversals in bipartite covers
Given a bipartite graph $H=(V=V_A\cup V_B,E)$ in which any vertex in $V_A$ (resp. $V_B$) has degree at most $D_A$ (resp. $D_B$), suppose there is a partition of $V$ that is a refinement of the bipartition $V_A\cup V_B$ such that the parts in $V_A$ (resp. $V_B$) have size at least $k_A$ (resp. $k_B$). We prove that the condition $D_A/k_A+D_B/k_B\le 1$ is sufficient for the existence of an independent set of vertices of $H$ that is simultaneously transversal to the partition, and show moreover that this condition is sharp.