N. Grelier, R. de Joannis de Verclos, R. J. Kang and F. Pirot. Approximate strong edge-colouring of unit disk graphs. 30 pp. A preliminary version of this paper appeared in Proceedings of the 17th International Workshop on Approximation and Online Algorithms (WAOA 2019, Munich), Lecture Notes in Computer Science 11926: 154-169, 2020. [abstract]
Published or accepted journal articles
J. J. Wouters, A. Giotis, R. J. Kang, D. Schuricht, L. Fritz. Lower bounds for Ramsey numbers as a statistical physics problem. Journal of Statistical Mechanics 2022(3): 033211 (14 pp.), 2022. [arxiv, doi, ±]
S. Cambie, W. Cames van Batenburg, R. de Joannis de Verclos and R. J. Kang. Maximising line subgraphs of diameter at most $t$. SIAM Journal on Discrete Mathematics 36(2), 939-950, 2022. A preliminary version of this paper appeared in Proceedings of the 11th European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2021, Barcelona), Trends in Mathematics 14: 331-338, 2021. [abstract, arxiv, doi, ±]
We wish to bring attention to a natural but slightly hidden problem, posed by Erdős and Nešetřil in the late 1980s, an edge version of the degree-diameter problem. Our main result is that, for any graph of maximum degree $\Delta$ with more than $1.5 \Delta^t$ edges, its line graph must have diameter larger than $t$. In the case where the graph contains no cycle of length $2t+1$, we can improve the bound on the number of edges to one that is exact for $t\in\{1,2,3,4,6\}$. In the case $\Delta=3$ and $t=3$, we obtain an exact bound. Our results also have implications for the related problem of bounding the distance-$t$ chromatic index, $t>2$; in particular, for this we obtain an upper bound of $1.941\Delta^t$ for graphs of large enough maximum degree $\Delta$, markedly improving upon earlier bounds for this parameter.
S. Cambie and R. J. Kang. Independent transversals in bipartite correspondence-covers. To appear in Canadian Mathematical Bulletin, 14 pp. [arxiv, doi, ±]
Suppose $G$ and $H$ are bipartite graphs and $L: V(G)\to 2^{V(H)}$ induces a partition of $V(H)$ such that
the subgraph of $H$ induced between $L(v)$ and $L(v')$ is a matching whenever $vv'\in E(G)$.
We show for each $\varepsilon>0$ that, if $H$ has maximum degree $D$ and $|L(v)| \ge (1+\varepsilon)D/\log D$ for all $v\in V(G)$, then $H$ admits an independent transversal with respect to $L$, provided $D$ is sufficiently large. This bound on the part sizes is asymptotically sharp up to a factor $2$.
We also show some asymmetric variants of this result.
We develop an improved bound for the chromatic number of graphs of maximum degree $\Delta$ under the assumption that the number of edges spanning any neighbourhood is at most $(1-\sigma)\binom{\Delta}{2}$ for some fixed $0<\sigma<1$.
The leading term in the reduction of colours achieved through this bound is best possible as $\sigma\to0$.
As two consequences, we advance the state of the art in two longstanding and well-studied graph colouring conjectures, the Erdős-Nešetřil conjecture and Reed's conjecture.
We prove that the strong chromatic index is at most $1.772\Delta^2$ for any graph $G$ with sufficiently large maximum degree $\Delta$.
We prove that the chromatic number is at most $\lceil 0.881(\Delta+1)+0.119\omega\rceil$ for any graph $G$ with clique number $\omega$ and sufficiently large maximum degree $\Delta$.
Additionally, we show how our methods can be adapted under the additional assumption that the codegree is at most $(1-\sigma)\Delta$, and establish what may be considered first progress towards a conjecture of Vu.
Given a bipartite graph with parts $A$ and $B$ having maximum degrees at most $\Delta_A$ and $\Delta_B$, respectively, consider a list assignment such that every vertex in $A$ or $B$ is given a list of colours of size $k_A$ or $k_B$, respectively.
We prove some general sufficient conditions in terms of $\Delta_A$, $\Delta_B$, $k_A$, $k_B$ to be guaranteed a proper colouring such that each vertex is coloured using only a colour from its list.
These are asymptotically nearly sharp in the very asymmetric cases.
We establish one sufficient condition in particular, where $\Delta_A=\Delta_B=\Delta$, $k_A=\log \Delta$ and $k_B=(1+o(1))\Delta/\log\Delta$ as $\Delta\to\infty$.
This amounts to partial progress towards a conjecture from 1998 of Krivelevich and the first author.
We also derive some necessary conditions through an intriguing connection between the complete case and the extremal size of approximate Steiner systems.
We show that for complete bipartite graphs these conditions are asymptotically nearly sharp in a large part of the parameter space. This has provoked the following.
In the setup above, we conjecture that a proper list colouring is always guaranteed
(i) if $k_A \ge \Delta_A^\varepsilon$ and $k_B \ge \Delta_B^\varepsilon$ for any $\varepsilon>0$ provided $\Delta_A$ and $\Delta_B$ are large enough;
(ii) if $k_A \ge C \log\Delta_B$ and $k_B \ge C \log\Delta_A$ for some absolute constant $C>1$; or
(iii) if $\Delta_A=\Delta_B = \Delta$ and $ k_B \ge C (\Delta/\log\Delta)^{1/k_A}\log \Delta$ for some absolute constant $C>0$.
These are asymmetric generalisations of the above-mentioned conjecture of Krivelevich and the first author, and if true are close to best possible.
Our general sufficient conditions provide partial progress towards these conjectures.
Notes added: Zhu has proposed an alternative formulation of our main conjecture. The main results have been shown to hold in a stronger setting, in which they are shown to be near optimal.
R. J. Kang and T. Kelly. Colourings, transversals and local sparsity. To appear in Random Structures and Algorithms, 21 pages. [arxiv, doi, ±]
Motivated both by recently introduced forms of list colouring and by earlier work on independent transversals subject to a local sparsity condition, we use the semi-random method to prove the following result.
For any function $\mu$ satisfying $\mu(d)=o(d)$ as $d\to\infty$, there is a function $\lambda$ satisfying $\lambda(d)=d+o(d)$ as $d\to\infty$ such that the following holds.
For any graph $H$ and any partition of its vertices into parts of size at least $\lambda$ such that
(a) for each part the average over its vertices of degree to other parts is at most $d$, and (b) the maximum degree from a vertex to some other part is at most $\mu$, there is guaranteed to be a transversal of the parts that forms an independent set of $H$.
This is a common strengthening of two results of Loh and Sudakov (2007) and Molloy and Thron (2012), each of which in turn implies an earlier result of Reed and Sudakov (2002).
Note added: the second problem stated in the conclusion has been resolved due to a construction by Groenland, Kaiser, Treffers, Wales!
Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number $\chi$ contains a rainbow independent set of size $\lceil\frac12\chi\rceil$.
This is sharp up to a factor $2$.
This result and its short proof have implications for the related notion of chromatic discrepancy.
Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number $\chi$ contains an induced cycle of length $\Omega(\chi\log\chi)$ as $\chi\to\infty$.
Even if one only demands an induced path of length $\Omega(\chi\log\chi)$, the conclusion would be sharp up to a constant multiple.
We prove it for regular girth $5$ graphs and for girth $21$ graphs.
As a common strengthening of the induced paths form of this conjecture and of Johansson's theorem (1996), we posit the existence of some $c >0$ such that for every forest $H$ on $D$ vertices, every triangle-free and induced $H$-free graph has chromatic number at most $c D/\log D$. We prove this assertion with `triangle-free' replaced by `regular girth $5$'.
S. Cambie, R. de Joannis de Verclos and R. J. Kang. Regular Turán numbers and some Gan-Loh-Sudakov-type problems. To appear in Journal of Graph Theory, 16 pp. [arxiv, ±]
We investigate the effect of a fixed forbidden clique minor upon the strong chromatic index, both in multigraphs and in simple graphs.
We conjecture for each $k\ge 4$ that any $K_k$-minor-free multigraph of maximum degree $\Delta$ has strong chromatic index at most $\frac32(k-2)\Delta$. We present a construction certifying that if true the conjecture is asymptotically sharp as $\Delta\to\infty$.
In support of the conjecture, we show it in the case $k=4$ and prove the statement for strong clique number in place of strong chromatic index.
By contrast, we make a basic observation that for $K_k$-minor-free simple graphs, the problem of strong edge-colouring is ``between'' Hadwiger's Conjecture and its fractional relaxation.
For $k\geq5$, we also show that $K_k$-minor-free multigraphs of edge-diameter at most $2$ have strong clique number at most $(k-\frac{1}{2})\Delta$.
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.
Note added: one of the conjectures has been confirmed by Cho, Choi, Kim, Park.
Given $\varepsilon>0$, there exists $f_0$ such that, if $f_0 \le f \le \Delta^2+1$, then for any graph $G$ on $n$ vertices of maximum degree $\Delta$ in which the neighbourhood of every vertex in $G$ spans at most $\Delta^2/f$ edges,
(i)
an independent set of $G$ drawn uniformly at random has at least $(1/2-\varepsilon)(n/\Delta)\log f$ vertices in expectation, and
(ii)
the fractional chromatic number of $G$ is at most $(2+\varepsilon)\Delta/\log f$.
These bounds cannot in general be improved by more than a factor $2$ asymptotically.
One may view these as stronger versions of results of Ajtai, Komlós and Szemerédi (1981) and Shearer (1983). The proofs use a tight analysis of the hard-core model.
Note added: numerous further local occupancy optimisations have been performed.
We prove two distinct and natural refinements of a recent breakthrough result of Molloy (and a follow-up work of Bernshteyn) on the (list) chromatic number of triangle-free graphs. In both our results, we permit the amount of colour made available to vertices of lower degree to be accordingly lower. One result concerns list colouring and correspondence colouring, while the other concerns fractional colouring.
Our proof of the second illustrates the use of the hard-core model to prove a Johansson-type result, which may be of independent interest.
Notes added: The local occupancy optimisation has been generalised to locally sparse graphs. The connection drawn in this paper has been comprehensivelyelaborated to cover a much broader class of problems.
We prove that any triangle-free graph on $n$ vertices with minimum degree at least $d$ contains a bipartite induced subgraph of minimum degree at least $d^2/(2n)$. This is sharp up to a logarithmic factor in $n$.
Relatedly, we show that the fractional chromatic number of any such triangle-free graph is at most the minimum of $n/d$ and $(2+o(1))\sqrt{n/\log n}$ as $n\to\infty$.
This is sharp up to constant factors.
Similarly, we show that the list chromatic number of any such triangle-free graph is at most $O(\min\{\sqrt{n},(n\log n)/d\})$ as $n\to\infty$.
Relatedly, we also make two conjectures. First, any triangle-free graph on $n$ vertices has fractional chromatic number at most $(\sqrt{2}+o(1))\sqrt{n/\log n}$ as $n\to\infty$. Second, any triangle-free graph on $n$ vertices has list chromatic number at most $O(\sqrt{n/\log n})$ as $n\to\infty$.
Notes added: part of this work was obtained concurrently and independently by Kwan, Letzter, Sudakov, Tran. One stronger and one more general form of the first conjecture has been posed. The second conjecture has been confirmed by Davies and Illingworth.
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, doi, ±]
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, doi, ±]
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.
Note added: the main conjecture has been generalised.
Given a multigraph, suppose that each vertex is given a local assignment of $k$ colours to its incident edges. We are interested in whether there is a choice of one local colour per vertex such that no edge has both of its local colours chosen. The least $k$ for which this is always possible given any set of local assignments we call the single-conflict chromatic number of the graph. This parameter is closely related to separation choosability and adaptable choosability. We show that single-conflict chromatic number of simple graphs embeddable on a surface of Euler genus $g$ is $O(g^{1/4}\log g)$ as $g\to\infty$. This is sharp up to the logarithmic factor.
Note added: one of the questions in this paper has been resolved (in the case of simple graphs) by Bradshaw and Masarik.
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$.
Note added: the multigraph form of the main result has been improved in the non-simple case (conditionally on the truth of the Goldberg-Seymour conjecture).
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$.
Note added: It was later realised that Property K was already subsumed by an older notion related to the extremal size of approximate Steiner systems.
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. [video, 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, doi, ±]
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.
Note added: the main result here has been generalised by Dvořák, Pekárek, Sereni.
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, doi, ±]
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 essentially 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, doi, ±]
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 by Veremyev, Boginski, Krokhmal, Jeffcoat 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 publications
L. Beunk, S. van Helvert, B. Bekker, L. Ran, R. J. Kang, T. Paulat, S. Syga, A. Deutsch, P. Friedl, K. Wolf. Extracellular matrix guidance determines proteolytic and non-proteolytic cancer cell patterning, 21 pages. [biorxiv]
J. Briët, D. Holmes, and R. J. Kang. Steps towards openness and fairness in scientific publishing. Nieuw Archief voor Wiskunde (5) 23(1): 53-55, 2022. [rr, naw]
R. J. Kang. Mathematical (online) meetings reimagined? EMS Magazine 120: 43-44, 2021. [rr, doi]
R. J. Kang. Parties a smidgen smaller. Nieuw Archief voor Wiskunde (5) 21(4): 232-235, 2020. [rr, naw]
R. J. Kang. Letter, 'Doet de Radboud Universiteit genoeg voor diversiteit?' In Vox (Radboud University magazine), July 2020. [nederlands, english]
R. J. Kang. The latest designs. Nieuw Archief voor Wiskunde (5) 15(3): 167-168, 2014. [rr, naw]
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.
As of October 2021: all manuscripts will include the line "For the purpose of open access, a CC BY public copyright licence is applied to any Author Accepted Manuscript (AAM) arising from this submission."
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: December 2021.
Fix $t>2$ and let $h_t(\Delta)$ be one more than the largest number of edges inducing a graph of maximum degree $\Delta$ whose line graph has diameter at most $t$. For every $\varepsilon>0$, is it true that $(1-\varepsilon)\Delta^t < h_t(\Delta) < (1+\varepsilon)\Delta^t$ for infinitely many $\Delta$? Cambie, Cames van Batenburg, de Joannis de Verclos, Kang 2021+.
Let $\varepsilon>0$ and let $H$ be a graph of maximum degree $D$ that admits a vertex-partition such the following properties hold: (i) every part has size at least $(1+\varepsilon)D/\log D$; (ii) the bipartite subgraph induced between any pair of parts has maximum degree $1$; (iii) letting $G$ be the auxiliary graph formed by associating an auxiliary vertex to every part and joining two auxiliary vertices if the bipartite subgraph induced between the respective parts in $H$ contains an edge, we have that $G$ is triangle-free. For $D$ sufficiently large, does $H$ admit an independent transversal with respect to the partition, that is, does $H$ have an independent set that intersects every part exactly once? Cambie, Kang 2020+. Anderson, Bernshteyn, Dhawan 2021+.
Let $G$ be a bipartite graph with vertex-bipartition $A\cup B$ such that every vertex in $A$ has degree at most $\Delta_A$ and every vertex in $B$ has degree at most $\Delta_B$. We say that $G$ is $(k_A,k_B)$-choosable if for any assignment of $k_A$ distinct (allowable) colours to each vertex in $A$ and $k_B$ to each vertex in $B$, there is guaranteed to be a proper vertex-colouring using only allowable colours. Is there some $C>0$ such that $G$ is always $(C\log \Delta_B,C\log\Delta_A)$-choosable? Alon, Cambie, Kang 2021.
Does every triangle-free graph of chromatic number $\chi$ contain an induced cycle of length $\Omega(\chi\log \chi)$ as $\chi\to\infty$? Aravind, Cambie, Cames van Batenburg, de Joannis de Verclos, Kang, Patel 2021.
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 2020. Update: Solved by Davies and Illingworth 2021+.
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 2020.
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 2020.
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. Update: This was already resolved (in the negative) in the 2012 thesis of Würfl.
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$. For $t$ large enough, it is at least $0.629^t d^t$ for infinitely many $d$. Kang, Manggala 2012. Kaiser, Kang 2014. Kang, Pirot 2016. Cambie, Cames van Batenburg, de Joannis de Verclos, Kang 2021+
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.
Postdoctoral candidates in probabilistic and extremal combinatorics are encouraged to get in touch about the Radboud Excellence Initiative.
The Department of Mathematics welcomes students wishing to conduct their PhD research under the China Scholarship Council programme.
Erdős number at most 2 via Alon, Lovász, Pach or West. Black Sabbath number at most 3 via a stint in 1996 as violinist in the BCMEA Honour Orchestra directed by David Foster, who produced for Madonna on "Something to Remember" in 1995, who was once backing singer for Ozzy Osbourne on "Shake Your Head" in 1983. (Credit to Ross Churchley for finding this path to Black Sabbath.)
kang
gmail