As of April 2017: support of Fair Open Access principles. See also this, this, this, this and, last but not least, this.
As of April 2019: requests to review manuscripts not yet on a public preprint repository are likely to be refused.
(Do not hesitate to email if you have trouble accessing any of the manuscripts listed below.)
Given a graph $G$, the strong clique number $\omega_2'(G)$ of $G$ is the cardinality of a largest collection of edges every pair of which are incident or connected by an edge in $G$.
We study the strong clique number of graphs missing some set of cycle lengths.
For a graph $G$ of large enough maximum degree $\Delta$, we show among other results the following:
$\omega_2'(G)\le5\Delta^2/4$ if $G$ is triangle-free;
$\omega_2'(G)\le3(\Delta-1)$ if $G$ is $C_4$-free;
$\omega_2'(G)\le\Delta^2$ if $G$ is $C_{2k+1}$-free for some $k\ge 2$.
These bounds are attained by natural extremal examples. Our work extends and improves upon previous work of Faudree, Gyárfás, Schelp and Tuza (1990), Mahdian (2000) and Faron and Postle (2019).
We are motivated by the corresponding problems for the strong chromatic index.
S. Cambie, A. Girão and R. J. Kang. VC dimension and a union theorem for set systems. Electronic Journal of Combinatorics 26(3): P3.24 (7 pp.), 2019. [arxiv, ejc, ±]
Fix positive integers $k$ and $d$. We show that, as $n\to\infty$, any set system $\mathcal{A} \subset 2^{[n]}$ for which the VC dimension of $\{ \triangle_{i=1}^k S_i \mid S_i \in \mathcal{A}\}$ is at most $d$ has size at most $(2^{d\bmod{k}}+o(1))\binom{n}{\lfloor d/k\rfloor}$. Here $\triangle$ denotes the symmetric difference operator. This is a $k$-fold generalisation of a result of Dvir and Moran, and it settles one of their questions.
A key insight is that, by a compression method, the problem is equivalent to an extremal set theoretic problem on $k$-wise intersection or union that was originally due to Erdős and Frankl.
We also give an example of a family $\mathcal{A} \subset 2^{[n]}$ such that the VC dimension of $\mathcal{A}\cap \mathcal{A}$ and of $\mathcal{A}\cup \mathcal{A}$ are both at most $d$, while $\lvert \mathcal{A} \rvert = \Omega(n^d)$. This provides a negative answer to another question of Dvir and Moran.
R. J. Kang and W. van Loon. Tree-like distance colouring for planar graphs of sufficient girth. Electronic Journal of Combinatorics 26(1): P1.23 (15 pp.), 2019. [slides, arxiv, ejc, ±]
Given a multigraph $G$ and a positive integer $t$, the distance-$t$ chromatic index of $G$ is the least number of colours needed for a colouring of the edges so that every pair of distinct edges connected by a path of fewer than $t$ edges must receive different colours.
Let $\pi'_t(d)$ and $\tau'_t(d)$ be the largest values of this parameter over the class of planar multigraphs and of (simple) trees, respectively, of maximum degree $d$.
We have that $\pi'_t(d)$ is at most and at least a non-trivial constant multiple larger than $\tau'_t(d)$.
(We conjecture $\limsup_{d\to\infty}\pi'_2(d)/\tau'_2(d) =9/4$ in particular.)
We prove for odd $t$ the existence of a quantity $g$ depending only on $t$ such that the distance-$t$ chromatic index of any planar multigraph of maximum degree $d$ and girth at least $g$ is at most $\tau'_t(d)$ if $d$ is sufficiently large.
Such a quantity does not exist for even $t$.
We also show a related, similar phenomenon for distance vertex-colouring.
L. Esperet, R. J. Kang and S. Thomassé. Separation choosability and dense bipartite induced subgraphs. Combinatorics, Probability and Computing 28(5): 720-732, 2019. [slides, arxiv, doi, ±]
We study a restricted form of list colouring, for which every pair of lists that correspond to adjacent vertices may not share more than one colour. The optimal list size such that a proper list colouring is always possible given this restriction, we call separation choosability. We show for bipartite graphs that separation choosability increases with (the logarithm of) the minimum degree. This strengthens results of Molloy and Thron and, partially, of Alon. One attempt to drop the bipartiteness assumption precipitates a natural class of Ramsey-type questions, of independent interest. For example, does every triangle-free graph of minimum degree $d$ contain a bipartite induced subgraph of minimum degree $\Omega(\log d)$ as $d\to\infty$?
Note added: several of the conjectures/problems posed have been solved or partially solved in two independentworks.
R. J. Kang and F. Pirot. Distance colouring without one cycle length. Combinatorics, Probability and Computing 27(5): 794-807, 2018. A preliminary version of this paper appeared in Proceedings of the 9th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2017, Vienna), Electronic Notes in Discrete Mathematics 61: 695-701, 2017. [slides, abstract, arxiv, doi, ±]
We consider distance colourings in graphs of maximum degree at most $d$ and how excluding one fixed cycle of length $\ell$ affects the number of colours required as $d\to\infty$. For vertex-colouring and $t\ge 1$, if any two distinct vertices connected by a path of at most $t$ edges are required to be coloured differently, then a reduction by a logarithmic (in $d$) factor against the trivial bound $O(d^t)$ can be obtained by excluding an odd cycle length $\ell \ge 3t$ if $t$ is odd or by excluding an even cycle length $\ell \ge 2t+2$. For edge-colouring and $t\ge 2$, if any two distinct edges connected by a path of fewer than $t$ edges are required to be coloured differently, then excluding an even cycle length $\ell \ge 2t$ is sufficient for a logarithmic factor reduction.
For $t\ge 2$, neither of the above statements are possible for other parity combinations of $\ell$ and $t$.
These results can be considered extensions of results due to Johansson (1996) and Mahdian (2000), and are related to open problems of Alon and Mohar (2002) and Kaiser and Kang (2014).
A. Girão and R. J. Kang. A precolouring extension of Vizing's theorem. Journal of Graph Theory 92(3): 255-260, 2019. [arxiv, doi, ±]
Fix a palette $\mathcal K$ of $\Delta+1$ colours, a graph with maximum degree $\Delta$, and a subset $M$ of the edge set with minimum distance between edges at least $9$. If the edges of $M$ are arbitrarily precoloured from $\mathcal K$, then there is guaranteed to be a proper edge-colouring using only colours from $\mathcal K$ that extends the precolouring on $M$ to the entire graph. This result is a first general precolouring extension form of Vizing's theorem, and it proves a conjecture of Albertson and Moore under a slightly stronger distance requirement. We also show that the condition on the distance can be lowered to $5$ when the graph contains no cycle of length $5$.
R. J. Kang, V. Patel and G. Regts. Discrepancy and large dense monochromatic subsets. Journal of Combinatorics 10(1): 87-109, 2019. [arxiv, doi, ±]
Erdős and Pach (1983) introduced the natural degree-based generalisations of Ramsey numbers, where instead of seeking large monochromatic cliques in a 2-edge coloured complete graph, we seek monochromatic subgraphs of high minimum or average degree. Here we expand the study of these so-called quasi-Ramsey numbers in a few ways, in particular, to multiple colours and to uniform hypergraphs.
Quasi-Ramsey numbers are known to exhibit a certain unique phase transition and we show that this is also the case across the settings we consider. Our results depend on a density-biased notion of hypergraph discrepancy optimised over sets of bounded size, which may be of independent interest.
W. Cames van Batenburg and R. J. Kang. Squared chromatic number without claws or large cliques. Canadian Mathematical Bulletin 62(1): 23-35, 2019. [slides, arxiv, doi, ±]
Let $G$ be a claw-free graph on $n$ vertices with clique number $\omega$, and consider the chromatic number $\chi(G^2)$ of the square $G^2$ of $G$. Writing $\chi'_s(d)$ for the supremum of $\chi(L^2)$ over the line graphs $L$ of simple graphs of maximum degree at most $d$, we prove that $\chi(G^2)\le \chi'_s(\omega)$ for $\omega \in \{3,4\}$. For $\omega=3$, this implies the sharp bound $\chi(G^2) \leq 10$. For $\omega=4$, this implies $\chi(G^2)\leq 22$, which is within $2$ of the conjectured best bound. This work is motivated by a strengthened form of a conjecture of Erdős and Nešetřil.
R. de Joannis de Verclos, R. J. Kang and L. Pastor. Colouring squares of claw-free graphs. Canadian Journal of Mathematics 71(1): 113-129, 2019. A preliminary version of this paper appeared in Proceedings of the 9th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2017, Vienna), Electronic Notes in Discrete Mathematics 61: 663-669, 2017. [slides, abstract, arxiv, doi, ±]
Is there some absolute $\varepsilon > 0$ such that for any claw-free graph $G$, the chromatic number of the square of $G$ satisfies $\chi(G^2) \le (2-\varepsilon) \omega(G)^2$, where $\omega(G)$ is the clique number of $G$? Erdős and Nešetřil asked this question for the specific case of $G$ the line graph of a simple graph and this was answered in the affirmative by Molloy and Reed. We show that the answer to the more general question is also yes, and moreover that it essentially reduces to the original question of Erdős and Nešetřil.
W. Cames van Batenburg and R. J. Kang. Packing graphs of bounded codegree. Combinatorics, Probability and Computing 27(5): 725-740, 2018. [arxiv, doi, ±]
Two graphs $G_1$ and $G_2$ on $n$ vertices are said to pack if there exist injective mappings of their vertex sets into $[n]$ such that the images of their edge sets are disjoint. A longstanding conjecture due to Bollobás and Eldridge and, independently, Catlin, asserts that, if $(\Delta(G_1)+1) (\Delta(G_2)+1) \le n+1$, then $G_1$ and $G_2$ pack. We consider the validity of this assertion under the additional assumption that $G_1$ or $G_2$ has bounded codegree. In particular, we prove for all $t \ge 2$ that, if $G_1$ contains no copy of the complete bipartite graph $K_{2,t}$ and $\Delta(G_1) > 17 t \cdot \Delta(G_2)$, then $(\Delta(G_1)+1) (\Delta(G_2)+1) \le n+1$ implies that $G_1$ and $G_2$ pack.
We also provide a mild improvement if moreover $G_2$ contains no copy of the complete tripartite graph $K_{1,1,s}$, $s\ge 1$.
R. J. Kang and F. Pirot. Colouring powers and girth. SIAM Journal on Discrete Mathematics 30(4): 1938-1949, 2016. [slides, arxiv, postprint, doi, ±]
Alon and Mohar (2002) posed the following problem: among all graphs $G$ of maximum degree at most $d$ and girth at least $g$, what is the largest possible value of $\chi(G^t)$, the chromatic number of the $t$th power of $G$? For $t\ge 3$, we provide several upper and lower bounds concerning this problem, all of which are sharp up to a constant factor as $d\to \infty$. The upper bounds rely in part on the probabilistic method, while the lower bounds are various direct constructions whose building blocks are incidence structures.
Note added: Many of the results of this paper have been strengthened in a follow-up work.
M. Bonamy and R. J. Kang. List colouring with a bounded palette. Journal of Graph Theory 84(1): 93-103, 2017. [slides, arxiv, doi, ±]
Král' and Sgall (2005) introduced a refinement of list colouring where every colour list must be subset to one predetermined palette of colours. We call this $(k,\ell)$-choosability when the palette is of size at most $\ell$ and the lists must be of size at least $k$. They showed that, for any integer $k\ge 2$, there is an integer $C=C(k,2k-1)$, satisfying $C = O(16^{k}\ln k)$ as $k\to \infty$, such that, if a graph is $(k,2k-1)$-choosable, then it is $C$-choosable, and asked if $C$ is required to be exponential in $k$. We demonstrate it must satisfy $C = \Omega(4^k/\sqrt{k})$.
For an integer $\ell \ge 2k-1$, if $C(k,\ell)$ is the least integer such that a graph is $C(k,\ell)$-choosable if it is $(k,\ell)$-choosable, then we more generally supply a lower bound on $C(k,\ell)$, one that is super-polynomial in $k$ if $\ell = o(k^2/\ln k)$, by relation to an extremal set theoretic property. By the use of containers, we also give upper bounds on $C(k,\ell)$ that improve on earlier bounds if $\ell \ge 2.75 k$.
R. J. Kang, E. Long, V. Patel and G. Regts. On a Ramsey-type problem of Erdős and Pach. Bulletin of the London Mathematical Society 49(6), 991-999, 2017. A preliminary version of this paper (with only three authors) appeared in Proceedings of the 8th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015, Bergen), Electronic Notes in Discrete Mathematics 49, 821-827, 2015. [slides, abstract, arxiv, doi, ±]
We affirmatively answer a question of Erdős and Pach from 1983 by showing the following: there is some constant $C>0$ such that for any graph $G$ on $Ck\ln k$ vertices either $G$ or its complement $\overline{G}$ has an induced subgraph on $k$ vertices with minimum degree at least $\frac12(k-1)$.
R. J. Kang and G. Perarnau. Decomposition of bounded degree graphs into $C_4$-free subgraphs. European Journal of Combinatorics 44: 99-105, 2015. [arxiv, doi, ±]
We prove that every graph with maximum degree $\Delta$ admits a partition of its edges into $O(\sqrt{\Delta})$ parts (as $\Delta\to\infty$) none of which contains $C_4$ as a subgraph. This bound is sharp up to a constant factor. Our proof uses an iterated random colouring procedure.
Note added: The method introduced here was shown by Tait to have wider applicability.
We consider precolouring extension problems for proper edge-colourings of graphs and multigraphs, in an attempt to prove stronger versions of Vizing's and Shannon's bounds on the chromatic index of (multi)graphs in terms of their maximum degree $\Delta$. We are especially interested in the following question: when is it possible to extend a precoloured matching to a colouring of all edges of a (multi)graph? This question turns out to be related to the notorious List Colouring Conjecture and other classic notions of choosability.
Note added: A slightly weaker version of the main conjecture of this paper has been shown by a subset of the authors.
N. Broutin and R. J. Kang. Bounded monochromatic components for random graphs. Journal of Combinatorics 9(3): 411-446, 2018. [slides, arxiv, doi, ±]
We consider vertex partitions of the binomial random graph $G_{n,p}$. For $np\to\infty$, we observe the following phenomenon: in any partition into asymptotically fewer than $\chi(G_{n,p})$ parts, i.e. $o(np/\log np)$ parts, one part must induce a connected component of order at least roughly the average part size.
Stated another way, we consider the $t$-component chromatic number, the smallest number of colours needed in a colouring of the vertices for which no monochromatic component has more than $t$ vertices. As long as $np \to \infty$, there is a threshold for $t$ around $\Theta(p^{-1}\log np)$: if $t$ is smaller then the $t$-component chromatic number is nearly as large as the chromatic number, while if $t$ is greater then it is around $n/t$.
For $0 < p <1$ fixed, we obtain more precise information. We find something more subtle happens at the threshold $t = \Theta(\log n)$, and we determine that the asymptotic first-order behaviour is characterised by a non-smooth function. Moreover, we consider the $t$-component stability number, the maximum order of a vertex subset that induces a subgraph with maximum component order at most $t$, and show that it is concentrated in a constant length interval about an explicitly given formula, so long as $t = O(\log \log n)$.
We also consider a related Ramsey-type parameter and use bounds on the component stability number of $G_{n,1/2}$ to describe its basic asymptotic growth.
R. J. Kang, T. Müller and D. B. West. On r-dynamic colouring of grids. Discrete Applied Mathematics 186: 286-290, 2015. [arxiv, doi, ±]
An $r$-dynamic $k$-colouring of a graph $G$ is a proper $k$-colouring of $G$ such that every vertex in $V(G)$ has neighbours in at least $\min\{d(v),r\}$ different color classes. The $r$-dynamic chromatic number of a graph $G$, written $\chi_r(G)$, is the least $k$ such that $G$ has such a colouring. Proving a conjecture of Jahanbekam, Kim, O, and West, we show that the $m$-by-$n$ grid has no $3$-dynamic $4$-colouring when $mn\equiv2\mod 4$. This completes the determination of the $r$-dynamic chromatic number of the $m$-by-$n$ grid for all $r,m,n$.
We consider a variation of Ramsey numbers introduced by Erdős and Pach (1983), where instead of seeking complete or independent sets we only seek a $t$-homogeneous set, a vertex subset that induces a subgraph of minimum degree at least $t$ or the complement of such a graph.
For any $\nu > 0$ and positive integer $k$, we show that any graph $G$ or its complement contains as an induced subgraph some graph $H$ on $\ell \ge k$ vertices with minimum degree at least $\frac12(\ell-1) + \nu$ provided that $G$ has at least $k^{\Omega(\nu^2)}$ vertices. We also show this to be best possible in a sense. This may be viewed as correction to a result claimed in Erdős and Pach (1983).
For the above result, we permit $H$ to have order at least $k$. In the harder problem where we insist that $H$ have exactly $k$ vertices, we do not obtain sharp results, although we show a way to translate results of one form of the problem to the other.
Note added: Most of the results here have been generalised by a subset of the authors.
R. J. Kang and T. Müller. Arrangements of pseudocircles and circles. Discrete and Computational Geometry 51(4): 896-925, 2014. A preliminary version appeared in Proceedings of the 7th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2013, Pisa), Publications of the Scuola Normale Superiore (CRM Series) 16, 179-183, 2013. [slides, abstract, preprint, doi, ±]
An arrangement of pseudocircles is a finite collection of Jordan curves in the plane with the additional properties that (i) every two curves meet in at most two points and (ii) if two curves meet in a point $p$, then they cross at $p$. We say that two arrangements $\cal{C} = (c_1,\dots, c_n )$, $\cal{D} = (d_1,\dots, d_n )$ are equivalent if there is a homeomorphism $\varphi$ of the plane onto itself such that $\varphi[c_i ] = d_i$ for all $1 \le i \le n$. Linhart and Ortner (2005) gave an example of an arrangement of five pseudocircles that is not equivalent to an arrangement of circles, and they conjectured that every arrangement of at most four pseudocircles is equivalent to an arrangement of circles. Here we prove their conjecture. We also consider two related recognition problems. The first is the problem of deciding, given a (combinatorial description of a) pseudocircle arrangement, whether it is equivalent to an arrangement of circles. The second is deciding whether it is equivalent to an arrangement of convex pseudocircles. We prove that both problems are NP-hard, answering questions of Bultena, Grünbaum and Ruskey (1998) and of Linhart and Ortner (2008). We also give an example of an arrangement of convex pseudocircles with the property that its intersection graph (i.e. the graph with one vertex for each pseudocircle and an edge between two vertices if and only if the corresponding pseudocircles intersect) cannot be realised as the intersection graph of a collection of circles. This disproves a folklore conjecture communicated to us by Pyatkin.
We seek families of subsets of an n-set of given size that contain the fewest $k$-chains. We prove a "supersaturation-type" extension of both Sperner's Theorem (1928) and its generalization by Erdős (1945). Erdős showed that a largest $k$-chain free family in the Boolean lattice is formed by taking all subsets of the $(k-1)$ middle sizes. Our result implies that by taking this family together with $x$ subsets of the $k$-th middle size, we obtain a family with the minimum number of $k$-chains, over all families of this size. We prove our result using the symmetric chain decomposition method of de Bruijn, van Ebbenhorst Tengbergen, and Kruyswijk (1951).
Note added: This was obtained simultaneously, independently, with a different method, by Das, Gan and Sudakov. Finally, Kleitman's conjecture has been solved in full by Samotij!
S. Griffiths, R. J. Kang, R. I. Oliveira and V. Patel. Tight inequalities among set hitting times in Markov chains. Proceedings of the American Mathematical Society 142(9): 3285-3298, 2014. [slides, arxiv, doi, ±]
Given an irreducible discrete-time Markov chain on a finite state space, we consider the largest expected hitting time $T(\alpha)$ of a set of stationary measure at least $\alpha$ for $\alpha\in(0,1)$. We obtain tight inequalities among the values of $T(\alpha)$ for different choices of $\alpha$. One consequence is that $T(\alpha) \le T(1/2)/\alpha$ for all $\alpha < 1/2$. As a corollary we have that, if the chain is lazy in a certain sense as well as reversible, then $T(1/2)$ is equivalent to the chain's mixing time, answering a question of Peres (2007). We furthermore demonstrate that the inequalities we establish give an almost everywhere pointwise limiting characterisation of possible hitting time functions $T(\alpha)$ over the domain $\alpha\in(0,1/2]$.
T. Kaiser and R. J. Kang. The distance-t chromatic index of graphs. Combinatorics, Probability and Computing 23(1): 90-101, 2014. [slides, arxiv, doi, ±]
We consider two graph colouring problems in which edges at distance at most $t$ are given distinct colours, for some fixed positive integer $t$. We obtain two upper bounds for the distance-$t$ chromatic index, the least number of colours necessary for such a colouring. One is a bound of $(2-\varepsilon)\Delta^t$ for graphs of maximum degree at most $\Delta$, where $\varepsilon$ is some absolute positive constant independent of $t$. The other is a bound of $O(\Delta^t/\log \Delta)$ (as $\Delta\to\infty$) for graphs of maximum degree at most $\Delta$ and girth at least $2t+1$. The first bound is an analogue of Molloy and Reed's bound on the strong chromatic index (1997). The second bound is tight up to a constant multiplicative factor, as certified by a class of graphs of girth at least $g$, for every fixed $g \ge 3$, of arbitrarily large maximum degree $\Delta$, with distance-$t$ chromatic index at least $\Omega(\Delta^t/\log \Delta)$.
Note added: The result on girth has been successively improvedwith Pirot.
N. Fountoulakis, R. J. Kang, and C. McDiarmid. Largest sparse subgraphs of random graphs. European Journal of Combinatorics 35: 232-244, 2014. A preliminary version of this paper appeared in Proceedings of the 6th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2011, Budapest), Electronic Notes in Discrete Mathematics 38: 349-354, 2011. [slides, abstract, arxiv, doi, ±]
For the Erdős–Rényi random graph, we give a precise asymptotic formula for the size of a largest vertex subset that induces a subgraph with average degree at most $t$, provided that the edge probability $p = p(n)$ is not too small and $t = t(n)$ is not too large. In the case of fixed $t$ and $p$, we find that this value is asymptotically almost surely concentrated on at most two explicitly given points. This generalises a result on the independence number of random graphs. For both the upper and lower bounds, we rely on large deviations inequalities for the binomial distribution.
R. J. Kang, C. McDiarmid, B. Reed and A. Scott. For most graphs H, most H-free graphs have a linear homogeneous set. Random Structures and Algorithms 45(3): 343-361, 2014. [slides, preprint, doi, ±]
Erdős and Hajnal (1977/1989) conjectured that for every graph $H$ there is a constant $\varepsilon = \varepsilon(H) > 0$ such that every graph $G$ that does not have $H$ as an induced subgraph contains a clique or a stable set of order $\Omega(|V(G)|^\varepsilon)$.
The conjecture would be false if we set $\varepsilon = 1$; however, in an asymptotic setting, we obtain this strengthened form of Erdős and Hajnal's conjecture for almost every graph $H$, and in particular for a large class of graphs $H$ defined by variants of the colouring number.
M. Bordewich and R. J. Kang. Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width. Electronic Journal of Combinatorics 21(4): #P4.19 (26 pp.), 2014. A preliminary version of this paper appeared in Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011, Zürich), Lecture Notes in Computer Science 6755: 533-544, 2011. [slides, abstract, arxiv, ejc, ±]
Motivated by the `subgraphs world' view of the ferromagnetic Ising model, we analyse the mixing times of Glauber dynamics based on subset expansion expressions for classes of graph, hypergraph and matroid polynomials. With a canonical paths argument, we demonstrate that the chains defined within this framework mix rapidly upon graphs, hypergraphs and matroids of bounded tree-width.
This extends known results on rapid mixing for the Tutte polynomial, adjacency- rank (R2-)polynomial and interlace polynomial. In particular Glauber dynamics for the R2-polynomial was known to mix rapidly on trees, which led to hope of rapid mixing on a wider class of graphs. We show that Glauber dynamics for a very wide class of polynomials mixes rapidly on graphs of bounded tree-width, including many cases in which the Glauber dynamics does not mix rapidly for all graphs. This demonstrates that rapid mixing on trees or bounded tree-width graphs does not offer strong evidence towards rapid mixing on all graphs.
R. J. Kang. Improper choosability and Property B. Journal of Graph Theory 73(3): 342-353, 2013. [slides, arxiv, doi, ±]
A fundamental connection between list vertex colourings of graphs and Property B (also known as hypergraph 2-colourability) was already known to Erdős, Rubin and Taylor (1980). In this article, we draw similar connections for improper list colourings. This extends results of Kostochka (2002), Alon (1993/2000), and Král' and Sgall (2005) for, respectively, multipartite graphs, graphs of large minimum degree, and list assignments with bounded list union.
R. J. Kang and T. Müller. Sphere and dot product representations of graphs. Discrete and Computational Geometry 47(3): 548-568, 2012. A preliminary version of this paper appeared in Proceedings of the 27th ACM Symposium on Computational Geometry (SOCG 2011, Paris), 308-314, 2011. [abstractdoi, abstractpdf, doi, ±]
A graph $G$ is a $k$-sphere graph if there are $k$-dimensional real vectors $v_1,\dots,v_n$ such that $ij \in E(G)$ if and only if the distance between $v_i$ and $v_j$ is at most $1$. A graph $G$ is a $k$-dot product graph if there are $k$-dimensional real vectors $v1,\dots,v_n$ such that $ij \in E(G)$ if and only if the dot product of $v_i$ and $v_j$ is at least $1$.
By relating these two geometric graph constructions to oriented $k$-hyperplane arrangements, we prove that the problems of deciding, given a graph $G$, whether $G$ is a $k$-sphere or a $k$-dot product graph are NP-hard for all $k > 1$. In the former case, this proves a conjecture of Breu and Kirkpatrick (1998). In the latter, this answers a question of Fiduccia, Scheinerman, Trenk and Zito (1998).
Furthermore, motivated by the question of whether these two recognition problems are in NP, as well as by the implicit graph conjecture, we demonstrate that, for all $k > 1$, there exist $k$-sphere graphs and $k$-dot product graphs such that each representation in $k$-dimensional real vectors needs at least an exponential number of bits to be stored in the memory of a computer. On the other hand, we show that exponentially many bits are always enough. This resolves a question of Spinrad (2003).
R. J. Kang and P. Manggala. Distance edge-colourings and matchings. Discrete Applied Mathematics 160(16-17): 2435-2439, 2012. A preliminary version of this paper appeared in Proceedings of the 5th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009, Bordeaux), Electronic Notes in Discrete Mathematics 34: 301-306, 2009. [slides, abstract, doi, ±]
We consider a distance generalisation of the strong chromatic index and the maximum induced matching number. We study graphs of bounded maximum degree and Erdős–Rényi random graphs. We work in three settings. The first is a distance generalisation of an Erdős–Nešetřil problem. The second is an upper bound on the size of a largest distance matching in a random graph. The third is an upper bound on the distance chromatic index for sparse random graphs. One of our results gives a counterexample to a conjecture of Skupień (1995).
Note added: Later work with Kaiser gives initial progress in the Erdős–Nešetřil-type problem
R. J. Kang, L. Lovász, T. Müller and E. R. Scheinerman. Dot product representations of planar graphs. Electronic Journal of Combinatorics 18(1): #P216 (14 pp.), 2011. A preliminary version of this paper appeared in Proceedings of the 18th Symposium on Graph Drawing (GD 2010, Konstanz), Lecture Notes in Computer Science 6502: 287-292, 2011. [abstract, ejc, ±]
A graph $G$ is a $k$-dot product graph if there exists a vector labelling $u : V (G) \to \mathbb{R}^k$ such that $u(i)^Tu(j) \ge 1$ if and only if $ij \in E(G)$. Fiduccia, Scheinerman, Trenk and Zito (1998) asked whether every planar graph is a $3$-dot product graph. We show that the answer is "no". On the other hand, every planar graph is a $4$-dot product graph. We also answer the corresponding questions for planar graphs of prescribed girth and for outerplanar graphs.
R. J. Kang, M. Mnich, T. Müller. Induced matchings in subcubic planar graphs. SIAM Journal on Discrete Mathematics 26(3): 1383-1411, 2012. A preliminary version of this paper appeared in Proceedings of the 18th European Symposium on Algorithms (ESA 2010, Liverpool), Lecture Notes in Computer Science 6347: 112-122, 2010. [slides, abstract, postprint, doi, ±]
We present a linear-time algorithm that, given a planar graph with $m$ edges and maximum degree 3, finds an induced matching of size at least $m/9$. This is best possible.
Note added: This work has been superseded in two different ways, by Joos, Rautenbach and Sasse and by Kostochka, Li, Ruksasakchai, Santana, Wang and Yu.
R. J. Kang, J.-S. Sereni, and M. Stehlík. Every plane graph of maximum degree 8 has an edge-face 9-colouring. SIAM Journal on Discrete Mathematics 25(2): 514-533, 2011. [arxiv, postprint, doi, ±]
An edge-face colouring of a plane graph with edge set $E$ and face set $F$ is a colouring of the elements of $E$ and $F$ such that adjacent or incident elements receive different colours. Borodin (1994) proved that every plane graph of maximum degree $\Delta \ge 10$ can be edge-face coloured with $\Delta+1$ colours. Borodin's bound was recently extended to the case where $\Delta=9$. In this paper, we extend it to the case $\Delta=8$.
L. Addario-Berry, S. Griffiths, and R. J. Kang. Invasion percolation on the Poisson-weighted infinite tree. Annals of Applied Probability 22(3): 931-970, 2012. [arxiv, pdf, doi, ±]
We study invasion percolation on Aldous' Poisson-weighted infinite tree, and derive two distinct Markovian representations of the resulting process. One of these is the $\sigma\to\infty$ limit of a representation discovered by Angel, Goodman, den Hollander and Slade (2008). We also introduce an exploration process of a randomly weighted Poisson incipient infinite cluster. The dynamics of the new process are much more straightforward to describe than those of invasion percolation, but it turns out that the two processes have extremely similar behaviour. Finally, we introduce two new "stationary" representations of the Poisson incipient infinite cluster as random graphs on $\mathbb{Z}$ which are, in particular, factors of a homogeneous Poisson point process on the upper half-plane $\mathbb{R}\times[0,\infty)$.
Note added: Addario-Berry has built quite substantially upon this work.
N. Fountoulakis, R. J. Kang, and C. McDiarmid. The t-stability number of a random graph. Electronic Journal of Combinatorics 17(1): #R59 (29 pp.), 2010. [arxiv, ejc, ±]
Given a graph $G = (V,E)$, a vertex subset $S \subseteq V$ is called $t$-stable (or $t$-dependent) if the subgraph $G[S]$ induced on $S$ has maximum degree at most $t$. The $t$-stability number $\alpha_t(G)$ of $G$ is the maximum order of a $t$-stable set in $G$. The theme of this paper is the typical values that this parameter takes on a random graph on $n$ vertices and edge probability equal to $p$. For any fixed $0 < p < 1$ and fixed non-negative integer $t$, we show that, with probability tending to $1$ as $n \to \infty$, the $t$-stability number takes on at most two values which we identify as functions of $t$, $p$ and $n$. The main tool we use is an asymptotic expression for the expected number of $t$-stable sets of order $k$. We derive this expression by performing a precise count of the number of graphs on $k$ vertices that have maximum degree at most $t$.
R. J. Kang and T. Müller. Frugal, acyclic and star colourings of graphs. Discrete Applied Mathematics 159(16): 1806-1814, 2011. A preliminary version of this paper appeared in Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009, Paris): 60-63. [slides, abstract, report, postprint, doi, ±]
Given a graph $G = (V, E)$, a colouring of $V$ is $t$-frugal if no colour appears more than $t$ times in any neighbourhood and is acyclic if each of the bipartite graphs consisting of the edges between any two colour classes is acyclic. For graphs of bounded maximum degree, Hind, Molloy and Reed (1997) studied proper $t$-frugal colourings and Yuster (1998) studied acyclic proper $2$-frugal colourings. In this paper, we expand and generalise this study.
R. J. Kang and C. McDiarmid. The t-improper chromatic number of random graphs. Combinatorics, Probability and Computing 19: 87-98, 2010. A preliminary version of this paper appeared in Proceedings of the 4th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2007, Seville), Electronic Notes in Discrete Mathematics 29: 411-417, 2007. [slides, abstract, arxiv, doi, ±]
We consider the $t$-improper chromatic number of the Erdős–Rényi random graph $G_{n,p}$. The $t$-improper chromatic number $\chi^t(G)$ is the smallest number of colours needed in a colouring of the vertices in which each colour class induces a subgraph of maximum degree at most $t$. If $t = 0$, then this is the usual notion of proper colouring. When the edge probability $p$ is constant, we provide a detailed description of the asymptotic behaviour of $\chi^t(G_{n,p})$ over the range of choices for the growth of $t = t(n)$.
Note added: A later work claims a significantly weaker result.
For graphs of bounded maximum degree, we consider acyclic $t$-improper colourings, that is, colourings in which each bipartite subgraph consisting of the edges between two colour classes is acyclic, and each colour class induces a graph with maximum degree at most $t$.
We consider the supremum, over all graphs of maximum degree at most $d$, of the acyclic $t$-improper chromatic number and provide $t$-improper analogues of results by Alon, McDiarmid and Reed (1991) and Fertin, Raspaud and Reed (2004).
F. Havet, R. J. Kang, and J.-S. Sereni. Improper colouring of unit disk graphs. Networks 54(3): 150-164, 2009. A preliminary version of this paper appeared in Proceedings of the 7th International Colloquium on Graph Theory (ICGT 2005, Hyères), Electronic Notes in Discrete Mathematics 22: 123-128, 2005. [slides, abstract, report, doi, ±]
Motivated by a satellite communications problem, we consider a generalized coloring problem on unit disk graphs. A coloring is $k$-improper if no more than $k$ neighbors of every vertex have the same colour as that assigned to the vertex. The $k$-improper chromatic number $\chi^k(G)$ is the least number of colors needed in a $k$-improper coloring of a graph $G$ . The main subject of this work is analyzing the complexity of computing $\chi^k$ for the class of unit disk graphs and some related classes, e.g., hexagonal graphs and interval graphs. We show NP-completeness in many restricted cases and also provide both positive and negative approximability results. Because of the challenging nature of this topic, many seemingly simple questions remain: for example, it remains open to determine the complexity of computing $\chi^k$ for unit interval graphs.
L. Addario-Berry, R. J. Kang, and T. Müller. Acyclic dominating partitions. Journal of Graph Theory 64(4): 292-311, 2010. A preliminary version of this paper appeared in Proceedings of the 4th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2007, Seville), Electronic Notes in Discrete Mathematics 29: 419-425, 2007. [slides, abstract, report, postprint, doi, ±]
Given a graph $G=(V,E)$, let $\cal{P}$ be a partition of $V$. We say that $\cal{P}$ is dominating if, for each part $P$ of $\cal{P}$, the set $V\setminus P$ is a dominating set in $G$ (equivalently, if every vertex has a neighbor of a different part from its own). We say that $\cal{P}$ is acyclic if for any parts $P$, $P'$ of $\cal{P}$, the bipartite subgraph $G[P,P']$ consisting of the edges between $P$ and $P'$ in $\cal{P}$ contains no cycles. The acyclic dominating number ad$(G)$ of $G$ is the least number of parts in any partition of $V$ that is both acyclic and dominating; and we shall denote by ad$(d)$ the maximum over all graphs $G$ of maximum degree at most $d$ of ad$(G)$. In this article, we prove that ad$(3)=2$, which establishes a conjecture of Boiron, Sopena, and Vignal (1997). For general $d$, we prove the upper bound ad$(d)=O(d\ln d)$ and a lower bound of ad$(d)=\Omega(d)$.
Note added: The proof of the conjecture of Boiron, Sopena and Vignal was announced in the preliminary version of 2007. In a later paper is claimed an independent proof.
We study circular choosability, a notion recently introduced by Mohar and Zhu. First, we provide a negative answer to a question of Zhu about circular cliques. We next prove that cch$(G)=O($ch$(G)+\ln|V(G)|)$ for every graph $G$. We investigate a generalization of circular choosability, the circular $f$-choosability, where $f$ is a function of the degrees. We also consider the circular choice number of planar graphs. Mohar asked for the value of $\tau := \sup\{$cch$(G) : G$ is planar$\}$, and we prove that $6 \le \tau \le 8$, thereby providing a negative answer to another question of Mohar. We also study the circular choice number of planar and outerplanar graphs with prescribed girth, and graphs with bounded density.
R. J. Kang, T. Müller, and J.-S. Sereni. Improper colouring of (random) unit disk graphs. Discrete Mathematics 308(8): 1438-1454, 2008. A preliminary version of this paper appeared in Proceedings of the 3rd European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2005, Berlin), Discrete Mathematics and Theoretical Computer Science AE: 193-198, 2005. [slides, abstract, report, doi, ±]
For any graph $G$, the $k$-improper chromatic number $\chi^k(G)$ is the smallest number of colours used in a colouring of $G$ such that each colour class induces a subgraph of maximum degree $k$. We investigate $\chi^k$ for unit disk graphs and random unit disk graphs to generalise results of McDiarmid and Reed (1999), McDiarmid (2003), and McDiarmid and Müller (2011).
Book chapter
R. J. Kang and C. McDiarmid. Colouring random graphs. In R. J. Wilson and L. W. Beineke (Eds.), Topics in Chromatic Graph Theory, Encyclopedia of Mathematics and its Applications 156: 199-229, 2015. [preprint, doi, ±]
Typically how many colours are required to colour a graph? In other words, given a graph chosen randomly, what can we expect its chromatic number to be? We survey the classic interpretation of this question, with the binomial or Erdős–Rényi random graph and the usual chromatic number. We also treat a few variations, not only of the random graph model, but also of the chromatic parameter.
Note added: One problem posed here was resolved by Heckel.
Abstract in peer-reviewed conference proceedings (besides those above with journal versions)
W. Cames van Batenburg and R. J. Kang. The Bollobás-Eldridge-Catlin conjecture for even girth at least 10. In Proceedings of the 9th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2017, Vienna), Electronic Notes in Discrete Mathematics 61: 191-197, 2017. [abstract, arxiv]
Theses
R. J. Kang. Improper colourings of graphs. DPhil thesis, Mathematical and Physical Sciences Division, University of Oxford, 134 pp., 2008. [ora]
R. J. Kang. On improper colouring of unit disk graphs. Transfer thesis, Mathematical and Physical Sciences Division, University of Oxford, 44 pp., 2005. [pdf]
Other publication
R. J. Kang. The latest designs. Nieuw Archief voor Wiskunde (5) 15(3): 167-168, 2014. [rr, naw]
Personal open questions listed roughly in reverse chronological order. Each entry is self-contained but stated as concisely as possible; for fuller context, consult the corresponding paper(s) indicated. Last updated: September 2019.
The strong chromatic index of a multigraph is the least number of parts in a partition of the edges into induced matchings. For each $k\ge 4$, what is the largest strong chromatic index over all $K_k$-minor-free multigraphs of maximum degree $d$? Is it at most $1.5(k-2)d$? The $k=4$ case is settled and for $k=5$ the four colour theorem implies it is at most $(6+o(1))d$. Kang, van Loon 2019. Cames van Batenburg, de Joannis de Verclos, Kang, Pirot 2019+.
Is it true that the list chromatic number of any triangle-free graph on $n$ vertices is $O(\sqrt{n/\ln n})$ as $n\to\infty$? An $O(\sqrt{n})$ bound is known. Cames van Batenburg, de Joannis de Verclos, Kang, Pirot 2018+.
Is it true that any triangle-free graph on $n$ vertices has (fractional) chromatic number at most $(\sqrt{2}+o(1))\sqrt{n/\ln n}$ as $n\to\infty$? The bound holds with $2$ in the place of $\sqrt{2}$. Cames van Batenburg, de Joannis de Verclos, Kang, Pirot 2018+.
Is it true that, for some $c>0$, every triangle-free graph of minimum degree $d$ contains a bipartite induced subgraph of minimum degree $c\log d$? A lower bound of the form $c\log d/\log\log d$ has been established. Esperet, Kang, Thomassé 2019. Kwan, Letzter, Sudakov, Tran 2019+.
The distance-$t$ chromatic number of a graph is the least number of colours in a vertex-colouring of the graph such that no two vertices of the same colour are connected by a path containing at most $t$ edges. For each fixed $t$ and fixed $\ell$, asymptotically up to a constant factor what is the largest distance-$t$ chromatic number of a graph with no cycle of length $\ell$ as a subgraph and of maximum degree $d$ as $d\to \infty$? Kang, Pirot 2018.
A graph is $(k,\ell)$-choosable if for any assignment of lists of $k$ distinct (allowable) colours chosen from $\{1,\dots,\ell\}$ to every vertex, there is guaranteed to be a proper vertex-colouring using only allowable colours. Is every $(3,9)$-choosable graph $(4,\infty)$-choosable? Bonamy, Kang 2017.
Given a graph of maximum degree $d$, suppose that some induced matching that has been pre-assigned colours from $\{1,\dots,d+1\}$. Is there a proper edge-colouring of the whole graph that obeys the pre-assignment? It is true if the edges in the precoloured matching are mutually at distance at least $9$ from each other. Edwards, Girão, van den Heuvel, Kang, Puleo, Sereni 2018. Girão, Kang 2019.
Let $P_n$ be a graph chosen uniformly at random from all planar graphs on $[n] = \{1,\dots,n\}$. What is the largest constant $c$ such that, with probability tending to $1$ as $n\to\infty$, the largest stable set in $P_n$ has at least $c n$ vertices? It is known that $c >0.269$. Kang, McDiarmid 2015.
The fixed quasi-Ramsey number is the least integer $R_t(k)$ such that any graph of order $R_t(k)$ contains a vertex subset of $k$ vertices that induces a subgraph either of minimum degree at least $t$ or of maximum degree at most $k-1-t$. For each fixed $c\in(1/2,1)$, is it true that $\lim_{k\to\infty} (\ln R_0(k)-\ln R_{\lfloor c(k-1) \rfloor}(k))/k >0$? The answer is yes if $c \in [0,1/2]$. Kang, Pach, Patel, Regts 2015.
An arrangement of pseudocircles is a finite collection of Jordan curves in the plane such that every two curves intersect in at most two points and two curves must cross at any point where they meet. A pseudocircle arrangement is convexible if there is a curve-preserving homeomorphism of the plane with respect to another pseudocircle arrangement in which every curve is convex. What is the least number of pseudocircles in an arrangment that is not convexible? The answer cannot be lower than $5$. Kang, Müller 2014.
The distance-$t$ chromatic index of a graph is the least number of colours in an edge-colouring of the graph such that no two edges of the same colour are connected by a path containing fewer than $t$ edges. For each fixed $t$ and fixed $g$, asymptotically up to a constant factor what is the largest distance-$t$ chromatic index of a graph with no cycle of length greater than $g$ as a subgraph and of maximum degree $d$ as $d\to \infty$? The answer is known to be $\Theta(d^t/\log d)$ if $g \ge 2t+3$ and for most other cases it is only known to be between $\Omega(d^t/\log d)$ and $O(d^t)$. Kaiser, Kang 2014. Kang, Pirot 2016.
Given a graph $H$, let $Forb(H)^n$ be the class of all graphs on $[n] = \{1,\dots,n\}$ that do not contain $H$ as an induced subgraph. Given a graph $G$, let $h(G)$ be the number of vertices in a largest stable set or clique of $G$. If $P_4$ is the $4$-vertex path, is there some $b>0$ such that $|\{G\in Forb(P_4)^n | h(G) \ge bn\}|/|Forb(P_4)^n| \to 1$ as $n\to\infty$? It is known that the statement holds if $P_4$ is replaced by almost every graph. Kang, McDiarmid, Reed, Scott 2014.
A graph is $t$-improper $k$-choosable if for any assignment of lists of $k$ distinct (allowable) colours per vertex, there is guaranteed to be a vertex-colouring using only allowable colours such that no vertex has more than $t$ neighbours of the same colour; the least such $k$ is the $t$-improper choosability $ch_t$ of the graph. What is the fastest growing function $f$ such that $ch_t \ge f(ch_0)$ for every graph? It is known that $f(x) \le x$ and $f(x)$ can be chosen $\Omega(\log x)$ as $x\to\infty$. Kang 2013.
The distance-$t$ chromatic index of a graph is the least number of colours in an edge-colouring of the graph such that no two edges of the same colour are connected by a path containing fewer than $t$ edges. For each fixed $t$, asymptotically what is the largest distance-$t$ chromatic index of a graph of maximum degree $d$ as $d\to \infty$? In general, it is known to be at least $d^t/2^t$ and at most $(2-\varepsilon)d^t$ for some absolute $\varepsilon>0$ as $d\to\infty$. Kang, Manggala 2012. Kaiser, Kang 2014. Kang, Pirot 2016.
A graph is $k$-dot product if there is a vertex labelling $u$ with vectors from $\mathbb R^k$ such that $u(i)^Tu(j)\ge 1$ if and only if $ij$ is an edge of the graph. What characterises the class of planar graphs that are not $3$-dot product? It is known that every planar graph is $4$-dot product and there are planar graphs that are not $3$-dot product. Kang, Lovász, Müller, Scheinerman 2011.
The $t$-frugal chromatic number of a graph is the least number of parts in a partition of the vertices so that no colour appears more than $t$ times in any neighbourhood. Asymptotically what is the largest $t$-frugal chromatic number of a graph of maximum degree $d$ as $d\to\infty$? Is it $(1+o(1))d^{1+1/t}/t$? Kang, Müller 2011.
The acyclic $t$-improper chromatic number of a graph is the least number of parts in a partition of the vertices so that no vertex has more than $t$ neighbours of the same colour and there is no (even) cycle that alternates between two of the parts. For every $t$ a (monotone) function of $d$, asymptotically up to a constant factor what is the largest acyclic $t$-improper chromatic number of a graph of maximum degree $d$ as $d\to\infty$? It is always $O(d^{4/3})$ and, if $d-t = \Omega(d)$, then it is $\Omega(d^{4/3}/(\log d)^{1/3})$ as $d\to\infty$. Addario-Berry, Esperet, Kang, McDiarmid, Pinlou 2010.
The $t$-improper chromatic number of a graph is the least number of parts in a partition of the vertices so that no vertex has more than $t$ neighbours of the same colour. For each fixed $t$, is it NP-hard to determine the $t$-improper chromatic number of a given unit interval graph? It is known that the output can be determined in polynomial time to be one of two consecutive integers. Havet, Kang, Sereni 2009.
The acyclic dominating number of a graph is the least number of parts in a partition of the vertices so that every vertex has at least one neighbour in another part and there is no (even) cycle that alternates between two of the parts. Asymptotically up to a constant factor what is the largest acyclic dominating number of a graph of maximum degree $d$ as $d\to\infty$? It is known to be $\Omega(d)$ and $O(d\log d)$ as $d\to\infty$. Addario-Berry, Kang, Müller 2010.
Mohar and Zhu introduced a natural list version of circular chromatic number, called circular choosability. Mohar asked, what is the largest possible circular choosability of a planar graph? This is known to be between $6$ and $8$. Havet, Kang, Müller, Sereni 2008.
Interested international postdoctoral candidates in probabilistic and extremal combinatorics are encouraged to get in touch about potential nomination under the Radboud Excellence Initiative.
Nijmegen mathematics welcomes Chinese students wishing to conduct their PhD research under the China Scholarship Council programme. Please email for more information.
Erdős number at most 2 via Lovász, Pach or West. Black Sabbath number at most 3 via a stint as violinist in the BCMEA Youth Orchestra directed by David Foster, who produced for Madonna, who was once backing singer for Ozzy Osbourne. (Credit to Ross Churchley for finding this path to Black Sabbath.)
kang
gmail