Ross Kang

Centrum Wiskunde & Informatica
PO Box 94079, 1090 GB
Amsterdam, The Netherlands

rosskangcwinl

+31 20 592 4386


Veni Postdoctoral Fellow, Centrum Wiskunde & Informatica.

Previously, …

Postdoctoral Research Associate, School of Engineering and Computing Sciences, Durham University, January 2010 - January 2012. [+/-]

NSERC Postdoctoral Fellow, School of Computer Science, McGill University, January 2008 - January 2010. [+/-]

DPhil, University of Oxford, October 2003 - December 2007; thesis entitled, "Improper colourings of graphs", approved in January 2008. [+/-]

BSc (Hons) in Mathematics and Computer Science, University of Victoria (Canada), September 1999 - December 2002 (awarded June 2003). [+/-]

Research

Probabilistic and extremal combinatorics, random discrete structures, graph colouring, geometric graphs, approximation algorithms and complexity.  DBLP and MathSciNet listings.

Journal articles (including preprints)

  1. R. J. Kang.  Improper choosability and Property B.  Accepted to Journal of Graph Theory, 12 pp.  [slides, arxiv, +/-]
    2. 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. In this article, we draw similar connections for improper list colourings. This extends results of Kostochka, Alon, and Král' and Sgall for, respectively, multipartite graphs, graphs of large minimum degree, and list assignments with bounded list union.
  2. 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, +/-]
    3. A graph is a \(k\)-sphere graph if there are \(k\)-dimensional real vectors \(v_1,\dots, v_n\) such that \(ij\) is an edge if and only if the distance between \(v_i\) and \(v_j\) is at most 1. A graph is a \(k\)-dot product graph if there are \(k\)-dimensional real vectors \(v_1,\dots,v_n\) such that \(ij\) is an edge if and only if the dot product of \(v_i\) and \(v_j\) is at least 1. By relating these to oriented \(k\)-hyperplane arrangements, we show for all \(k>1\) that their corresponding recognition problems are NP-hard (ERT-complete, in fact). This confirms conjecture of Breu and Kirkpatrick (1998) and answers a question of Fiduccia, Scheinerman, Trenk and Zito (1998). Furthermore, motivated by whether these recognition problems are in NP and by the implicit graph conjecture, we show for all \(k>1\) that 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, exponentially many bits are always enough. This resolves a question of Spinrad (2003).
  3. R. J. Kang, L. Lovász, T. Müller and E. 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, +/-]
    4. A \(k\)-dot product representation of a graph is a collection of vectors of \(R^k\) in 1-1 correspondence with the vertices such that two vertices are adjacent if and only if their associated vectors have dot product at least 1. We show that not every planar graph has a 3-dot product representation; we give two examples, one of which is a triangle-free planar graph. On the other hand, every planar graph has a 4-dot product representation, and every planar graph of girth at least 5 has a 3-dot product representation. This answers a question of Fiduccia, Scheinerman, Trenk and Zito (1998).
  4. 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, doi, +/-]
    5. 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\).
  5. 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, +/-]
    6. 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 limit as the degree goes to infinity 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 the integers which are, in particular, factors of a homogeneous Poisson point process in the upper half-plane.
  6. 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, +/-]
    7. We obtain a precise formula for the size of a largest \(t\)-stable set, that is, a set that induces maximum degree at most \(t\), in a dense random graph, by use of the saddle-point method from analytic combinatorics. We also obtain sharp upper and lower bounds on the \(t\)-improper chromatic number of a dense random graph, one of which implies an improved bound for the chromatic number.
  7. 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, preprint, doi, +/-]
    8. We generalise and expand upon results of Hind, Molloy and Reed (1997) on the proper t-frugal chromatic number, and of Yuster (1998) on the acyclic proper 2-frugal chromatic number for graphs of bounded maximum degree. We also extend their study to graph colourings that are not necessarily proper, as well as to star colourings. The Lovász Local Lemma is employed extensively.
  8. 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, +/-]
    9. The \(t\)-improper chromatic number is the least number of colours needed to partition the vertices of a graph so that each part induces a subgraph of maximum degree at most \(t\). For dense random graphs we provide a description of the behaviour of this parameter where \(t\) may grow as a function of the order of the graph. A surprising finding is that, up to a certain threshold, the \(t\)-improper chromatic number is asymptotically not much smaller than the chromatic number. Analysis of the threshold requires large deviation techniques.
  9. L. Addario-Berry, L. Esperet, R. J. Kang, C. McDiarmid, and A. Pinlou.  Acyclic improper colourings of graphs with bounded maximum degree.  Discrete Mathematics 310(2): 223-229, 2010.  Note: Special issue devoted to the 21st British Combinatorial Conference (BCC 2007, Reading).  [report, preprint, doi, +/-]
    10. A colouring is acyclic if each bipartite subgraph consisting of the edges between two colour classes is acyclic. We study the supremum, over all graphs of maximum degree \(d\), of the acyclic \(t\)-improper chromatic number, for nearly all choices of \(t\) as a function of \(d\), to obtain generalisations of results of Alon, McDiarmid and Reed (1991). Our results show that even allowing \(t\) to grow very quickly does not result in improved upper bounds on the acyclic \(t\)-improper chromatic number.
  10. 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, +/-]
    11. This work derives several complexity results for the \(t\)-improper colouring of unit disk graphs, that is, graphs formed from the intersection of unit disks in the plane. We prove both negative complexity and positive approximation results for this graph class as well as a few related ones. A notable problem from this project remains open: is it NP-hard to determine the \(t\)-improper chromatic number of a unit interval graph?
  11. 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, preprint, doi, +/-]
    12. We affirm a conjecture of Boiron, Sopena and Vignal (1997) by proving a stronger statement. The vertices of any graph of maximum degree three can be partitioned into two dominating sets so that the bipartite subgraph induced by the edges between them is a forest. The proof is by a sophisticated induction. We also consider the acyclic dominating partitions of graphs of larger maximum degree and, using a linear programming approach, determine the largest number of dominating sets required, up to a logarithmic factor of the degree. NB: In the 2007 preliminary version, the proof of the conjecture of Boiron, Sopena and Vignal was announced. This extended abstract was accessible online before the submission of another paper, in which is claimed an independent proof.
  12. F. Havet, R. J. Kang, T. Müller, and J.-S. Sereni.  Circular choosability.  Journal of Graph Theory 61(4): 241-270, 2009.  [slides, report, doi, +/-]
    13. The circular choosability of a graph combines two well-studied notions in graph colouring: circular colouring and list colouring. This parameter provides a wealth of challenging problems, a handful of which are resolved in this paper. We refute a conjecture of Zhu (2005) concerning circular cliques. We give a general upper bound in terms of ordinary choosability and logarithm of the order of the graph. We consider a degree constrained version of circular choosability. We show that for planar graphs the circular choosability is between 6 and 8; we also consider planar and outerplanar graphs of bounded density.
  13. 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, +/-]
    14. We give an analysis of the t-improper chromatic number for two asymptotic models of unit disk graphs. The first model is based on a countable set of points with given density in the plane, where the radius of the disks goes to infinity. The second is the natural model of random unit disk graphs, in which points are distributed in the unit square according to a Poisson distribution, and the radius of the disks goes to zero while the number of points goes to infinity. In both cases, the behaviour of the parameter is closely tied to the clique number divided by \(t+1\).

Peer-reviewed conference papers (besides those above with journal versions)

  1. N. Fountoulakis, R. J. Kang, and C. McDiarmid.  Largest sparse subgraphs of random graphs.  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]
  2. M. Bordewich and R. J. Kang.  Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width.  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]
  3. R. J. Kang, M. Mnich, T. Müller.  Induced matchings in subcubic planar graphs.  In Proceedings of the 18th European Symposium on Algorithms (ESA 2010, Liverpool), Lecture Notes in Computer Science 6347: 112-122, 2010.  [abstract, slides]
  4. R. J. Kang and P. Manggala.  On distance edge-colourings and matchings.  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]

Manuscripts under review or in preparation

  1. T. Kaiser and R. J. Kang.  The distance-t chromatic index of graphs.  12 pp.  [arxiv]
  2. N. Fountoulakis, R. J. Kang, and C. McDiarmid.  Largest sparse subgraphs of random graphs.  Full version submitted, 15 pp.  [arxiv]
  3. R. J. Kang, C. McDiarmid, B. Reed and A. Scott.  For most graphs H, most H-free graphs have a linear homogeneous set.  27 pp.
  4. M. Bordewich and R. J. Kang.  Rapid mixing of subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width.  25 pp.
  5. R. J. Kang and P. Manggala.  Distance edge-colourings and matchings.  Full version submitted, 11 pp.
  6. R. J. Kang, M. Mnich, T. Müller.  Induced matchings in subcubic planar graphs.  Full version submitted, 34 pp.

Theses

  1. R. J. Kang.  Improper colourings of graphs.  DPhil thesis, Mathematical and Physical Sciences Division, University of Oxford, 134 pp., May 2008.  [ora]
  2. R. J. Kang.  On improper colouring of unit disk graphs.  Transfer thesis, Mathematical and Physical Sciences Division, University of Oxford, 44 pp., January 2005.  [pdf]

Events

SMS 2012 (Montreal), Perspectives in DM 2012 (Barcelona), IMPA Pos-Doc 2012 (Rio), EuroComb 2011 (Budapest), Fields Graph Homomorphisms 2011 (Toronto), ICALP 2011 (Zürich), SOCG 2011 (Paris), CanaDAM 2011 (Victoria), DIMAP WCGT 2011 (Warwick), CMS 2010 (Vancouver), ACiD 2010 (Durham), ESA 2010 (Liverpool), PIMS Probability Summer School 2010 (Seattle), Bellairs 2010, StatComb 2009 (Paris), EuroComb 2009 (Bordeaux), CIME Complex Networks Summer School 2009 (Verres), CTW 2009 (Paris), CanaDAM 2009 (Montréal), CARP 2009 (Montréal), Bellairs 2009, RIMS Winter School on Graphs and Algorithms 2008 (Kyoto), MCW 2008 (Prague), Bellairs 2008, ADONET-CIRM School on Graphs and Algorithms 2007 (Levico Terme), EuroComb 2007 (Seville), BCC 2007 (Reading), CGGT 2007 (Kyoto), CRM Advanced Course on Analytic and Probabilistic Combinatorics 2007 (Barcelona), COMBSTRU 2006b (Barcelona), Horizons of Combinatorics 2006 (Budapest/Balatonalmádi), SIAM DM 2006 (Victoria), COMBSTRU 2006a (Prague), CMS Winter Meeting 2005 (Victoria), ICGT 2005 (Hyères), EuroComb 2005 (Berlin), COMBSTRU 2005 (Oxford), PCC 2005 (Oxford), SODA 2005 (Vancouver), PCC 2004 (London).
Durham Bannermakers

 

Page last modified . Copyright Ross Kang. CWI disclaimer.