R. J. Kang, E. Long, V. Patel and G. Regts. On a Ramsey-type problem of Erdős and Pach. 9 pp. 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. [abstract, arxiv]

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.

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.

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 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.

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 result 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.

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. [abstract, slides, 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. [abstract, arxiv, slides, 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. [abstract, slides, 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. [abstract, slides, 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. [abstract, slides, 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. [abstract, slides, 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)\).

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. [abstract, slides, 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. [abstract, slides, 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. [abstract, slides, 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.

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.

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.

Let \(P_n\) be a graph chosen uniformly at random from all planar graphs on \([n] = \{1,\dots,n\}\). Find 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.

Given a graph, the distance-\(t\) chromatic index 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.

Given a graph, the distance-\(t\) chromatic index 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.

Given a graph, the acyclic \(t\)-improper chromatic number is the least number of parts in any 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.

Given a graph, the \(t\)-improper chromatic number is the least number of parts in any 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.

Given a graph, the acyclic dominating number is the least number of parts in any 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.

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.)