Source author record

Rémi de Joannis de Verclos

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

5works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

An improved procedure for colouring graphs of bounded local density

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-σ)\binomΔ{2}$ for some fixed $0<σ<1$ . The leading term in the reduction of colours achieved through this bound is best possible as $σ\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Δ^2$ for any graph $G$ with sufficiently large maximum degree $Δ$ . We prove that the chromatic number is at most $\lceil 0.881(Δ+1)+0.119ω\rceil$ for any graph $G$ with clique number $ω$ and sufficiently large maximum degree $Δ$ . Additionally, we show how our methods can be adapted under the additional assumption that the codegree is at most $(1-σ)Δ$ , and establish what may be considered first progress towards a conjecture of Vu.

preprint2020arXiv

Bipartite induced density in triangle-free graphs

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

preprint2020arXiv

Colouring triangle-free graphs with local list sizes

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.

preprint2020arXiv

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

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 regular. Among other results, we prove a striking supersaturation version of Mantel's theorem in the case of a regular host graph of odd order. We also characterise the graphs for which the regular Turán numbers behave classically or otherwise.

preprint2020arXiv

Structure and colour in triangle-free graphs

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 $\lceil\frac12χ\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 $χ$ contains an induced cycle of length $Ω(χ\logχ)$ as $χ\to\infty$ . Even if one only demands an induced path of length $Ω(χ\logχ)$ , 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$ '.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Rémi de Joannis de Verclos

Research overview

Is this your work?

5 publications

An improved procedure for colouring graphs of bounded local density

Bipartite induced density in triangle-free graphs

Colouring triangle-free graphs with local list sizes

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

Structure and colour in triangle-free graphs

See the researcher in context

Building this map preview