Ross J. Kang

activity

20082026

most citedOn r-dynamic Coloring of Grids

37 citations · 312 across the 39 of their papers we have counts for

collaborators

49 papers

math.CO2026

Strong edge-colouring via local flag algebras

Eoin Davey, Eoin Hurley, Rémi de Joannis de Verclos +2

The strong chromatic index $χ_{s}^{'} (G)$ is the smallest number of colours needed to colour the edges of a graph $G$ so that any two edges at distance at most $2$ receive different col…

math.CO2026

Local flag algebras

Eoin Davey, Eoin Hurley, Rémi de Joannis de Verclos +2

We introduce local flag algebras, a variant of Razborov's flag algebra framework in which densities are normalised by the maximum degree $Δ (G)$ rather than the order $∣ G ∣$ . The fra…

math.CO2023

A precise condition for independent transversals in bipartite covers

Stijn Cambie, Penny Haxell, Ross J. Kang +1

Given a bipartite graph $H = (V = V_{A} \cup V_{B}, E)$ in which any vertex in $V_{A}$ (resp.~ $V_{B}$ ) has degree at most $D_{A}$ (resp.~ $D_{B}$ ), suppose there is a partition of $V$ that is a refin…

math.CO2023★ 2 cited

List packing number of bounded degree graphs

Stijn Cambie, Wouter Cames van Batenburg, Ewan Davies +1

We investigate the list packing number of a graph, the least $k$ such that there are always $k$ disjoint proper list-colourings whenever we have lists all of size $k$ associated to…

math.CO2022★ 4 cited

When removing an independent set is optimal for reducing the chromatic number

Stijn Cambie, John Haslegrave, Ross J. Kang

How large must the chromatic number of a graph be, in terms of the graph's maximum degree, to ensure that the most efficient way to reduce the chromatic number by removing vertices…

math.CO2021★ 18 cited

Lower bounds for Ramsey numbers as a statistical physics problem

Jurriaan Wouters, Aris Giotis, Ross Kang +2

Ramsey's theorem, concerning the guarantee of certain monochromatic patterns in large enough edge-coloured complete graphs, is a fundamental result in combinatorial mathematics. In…

math.CO2021★ 5 cited

Packing list-colourings

Stijn Cambie, Wouter Cames van Batenburg, Ewan Davies +1

List colouring is an influential and classic topic in graph theory. We initiate the study of a natural strengthening of this problem, where instead of one list-colouring, we seek m…

math.CO2021

Maximising line subgraphs of diameter at most $t$

Stijn Cambie, Wouter Cames van Batenburg, Rémi de Joannis de Verclos +1

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…

math.CO2020★ 9 cited

Independent transversals in bipartite correspondence-covers

Stijn Cambie, Ross J. Kang

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 when…

math.CO2020★ 16 cited

An improved procedure for colouring graphs of bounded local density

Eoin Hurley, Rémi de Joannis de Verclos, Ross J. Kang

We develop an improved bound for the chromatic number of graphs of maximum degree $Δ$ under the assumption that the number of edges spanning any neighbourhood is at most $(1-σ)\bin…

cs.DS2020★ 6 cited

An algorithmic framework for colouring locally sparse graphs

Ewan Davies, Ross J. Kang, François Pirot +1

We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fix…

math.CO2020★ 2 cited

Asymmetric list sizes in bipartite graphs

Noga Alon, Stijn Cambie, Ross J. Kang

Given a bipartite graph with parts $A$ and $B$ having maximum degrees at most $Δ_{A}$ and $Δ_{B}$ , respectively, consider a list assignment such that every vertex in $A$ or $B$ is give…

math.CO2020★ 15 cited

Graph structure via local occupancy

Ewan Davies, Ross J. Kang, François Pirot +1

The first author together with Jenssen, Perkins and Roberts (2017) recently showed how local properties of the hard-core model on triangle-free graphs guarantee the existence of la…

math.CO2019

Structure and colour in triangle-free graphs

N. R. Aravind, Stijn Cambie, Wouter Cames van Batenburg +3

Motivated by a recent conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number $χ$ contains a rainbow independent set of size $…

math.CO2019★ 1 cited

Regular Turán numbers and some Gan-Loh-Sudakov-type problems

Stijn Cambie, Rémi de Joannis de Verclos, Ross J. Kang

Motivated by a Gan-Loh-Sudakov-type problem, we introduce the regular Turán numbers, a natural variation on the classical Turán numbers for which the host graph is required to be r…

math.CO2019

Strong chromatic index and Hadwiger number

Wouter Cames van Batenburg, Rémi de Joannis de Verclos, Ross J. Kang +1

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 \geq 4$ that any $K_k…

math.CO2019

Strong cliques and forbidden cycles

Wouter Cames van Batenburg, Ross J. Kang, François Pirot

Given a graph $G$ , the strong clique number $ω_{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…

math.CO2018

Occupancy fraction, fractional colouring, and triangle fraction

Ewan Davies, Rémi de Joannis de Verclos, Ross J. Kang +1

Given $ε > 0$ , there exists $f_{0}$ such that, if $f_{0} \leq f \leq Δ^{2} + 1$ , then for any graph $G$ on $n$ vertices of maximum degree $Δ$ in which the neighbourhood of every vert…

math.CO2018★ 24 cited

Colouring triangle-free graphs with local list sizes

Ewan Davies, Rémi de Joannis de Verclos, Ross J. Kang +1

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

math.CO2018

Bipartite induced density in triangle-free graphs

Wouter Cames van Batenburg, Rémi de Joannis de Verclos, Ross J. Kang +1

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} / (2 n)$ . This is sharp up…

math.CO2018

VC dimension and a union theorem for set systems

Stijn Cambie, António Girão, Ross J. Kang

Fix positive integers $k$ and $d$ . We show that, as $n \to \infty$ , any set system $A \subset 2^{[n]}$ for which the VC dimension of $\{ \triangle_{i=1}^k S_i \mid S_i \in…

math.CO2018

Tree-like distance colouring for planar graphs of sufficient girth

Ross J. Kang, Willem van Loon

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…

math.CO2018

Single-conflict colouring

Zdeněk Dvořák, Louis Esperet, Ross J. Kang +1

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 pe…

math.CO2018★ 20 cited

Separation choosability and dense bipartite induced subgraphs

Louis Esperet, Ross J. Kang, Stéphan Thomassé

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…

Strong edge-colouring via local flag algebras

Local flag algebras

A precise condition for independent transversals in bipartite covers

List packing number of bounded degree graphs

When removing an independent set is optimal for reducing the chromatic number

Lower bounds for Ramsey numbers as a statistical physics problem

Packing list-colourings

Maximising line subgraphs of diameter at most t

Independent transversals in bipartite correspondence-covers

An improved procedure for colouring graphs of bounded local density

An algorithmic framework for colouring locally sparse graphs

Asymmetric list sizes in bipartite graphs

Graph structure via local occupancy

Structure and colour in triangle-free graphs

Regular Turán numbers and some Gan-Loh-Sudakov-type problems

Strong chromatic index and Hadwiger number

Strong cliques and forbidden cycles

Occupancy fraction, fractional colouring, and triangle fraction

Colouring triangle-free graphs with local list sizes

Bipartite induced density in triangle-free graphs

VC dimension and a union theorem for set systems

Tree-like distance colouring for planar graphs of sufficient girth

Single-conflict colouring

Separation choosability and dense bipartite induced subgraphs

Maximising line subgraphs of diameter at most $t$