This page gathers a certain number of (not very well known) problems I was interested in at some point. I would be curious to see proofs or counterexamples if you find some.

## Coloring graphs on surfaces such that every monochromatic component has bounded size (2014)

We proved in this paper that every graph of Euler genus `g` is 5-list-colorable in such a way that every monochromatic component has size `O(g)`. We conjectured that 5 can be replaced by 4 (this is known to be true for planar graphs, see this paper). A similar conjecture was made independently by Chappell and Gimbel for the chromatic number.

We also proved that graphs of Euler genus `g` and girth at least 6 are 2-list-colorable in such a way that every monochromatic component has size `O(g)`. We conjectured that it should also be true for graphs of girth 5. This is still open for planar graphs. A related problem was posed independently by Axenovich, Ueckerdt, and Weiner in this paper.

## Equitable partition of planar graphs into 3 induced forests (2013, 2015)

An equitable partition of a graph `G` is a partition of the vertex-set of `G` such that the sizes of any two parts differ by at most one.

Is it true that any planar graph has an equitable partition into 3 induced forests?

In this paper we proved that for any `k>=4`, any planar graph has an equitable partition into `k` induced forests (this proved a conjecture formulated by Wu, Zhang, and Li in 2013).

## Coloring triangle-free planar graphs with bounded monochromatic components (2014)

In this paper we proved that planar graphs with bounded maximum degree can be colored with 3 colors, in such way that every color class is the union of connected components of bounded size.

A natural question is the following:

Is there a function `f: NN rarr NN` such that the vertices of every triangle-free planar graph with maximum degree `Delta` can be 2-colored in such a way that each monochromatic component has at most `f(Delta)` vertices?

## Two firefighters in planar graphs (2013)

In a graph `G`, a fire starts at some vertex. At every time step, firefighters can protect up to `k` vertices, and then the fire spreads to all unprotected neighbours. The `k`-surviving rate `rho_k(G)` of `G` is the expectation of the proportion of vertices that can be saved from the fire, if the starting vertex of the fire is chosen uniformly at random.

We conjectured in this paper that there is a constant `epsilon>0`, such that for any planar graph `G`, `rho_2(G)>epsilon` (i.e. two firefighters can save (in average) a constant proportion of the vertices of any planar graph). We proved the conjecture for triangle-free planar graphs and subsequently it was proved for any planar graphs without cycles of length `i` (for any fixed `4 <=i<=7`).

This paper shows the following result: for any planar graph `G`, if 3 firefighters are available at the first round and then only 2 at each subsequent round, then a fraction of `2//21` of the vertices of `G` can be saved in average.

## Polynomial `chi`-boundedness (2012)

We say that a class of graphs `cc F` is `chi`-bounded if there is a function `f` such that for any graph `G in cc F`, `chi(G) <= f(omega(G))`, where `chi(G)` and `omega(G)` stand for the chromatic number and the clique number of `G`, respectively.

Is it true that if `cc F` is hereditary (i.e. closed under taking induced subgraphs), and `chi`-bounded, then there is a real `c` (depending on `cc F`) such that for any graph `G in cc F`, `chi(G) <= omega(G)^c`?

## Locally identifying coloring of chordal graphs (2012)

Let `N[u]` denote the closed neighborhood of a vertex `u` (i.e. `u` together with its neighbors).

We conjectured in this paper that every chordal graph with maximum clique size `k` can be properly colored with `2k` colors in such a way that for any two adjacent vertices `u` and `v` with `N[u]!=N[v]`, the set of colors appearing in `N[u]` is distinct from the set of colors appearing in `N[v]`.

We proved the conjecture for several subclasses of chordal graphs: interval graphs, split graphs, and `k`-trees. Note that there are perfect graphs with clique number 3, requiring an arbitrary number of colors to make sure that for any two adjacent vertices `u` and `v` with `N[u]!=N[v]`, the set of colors appearing in `N[u]` is distinct from the set of colors appearing in `N[v]`.

## Constructive lower bounds for ayclic and star coloring

A proper coloring of the vertices of a graph `G` is *acyclic* if every cycle of `G` contains at least 3 colors. It was proved by Alon, McDiarmid and Reed in 1991 that graphs with maximum degree `Delta` have an acyclic coloring with `O(Delta^{4//3})`. They also gave a simple probabilistic argument showing that there exist graphs with maximum degree `Delta` with no acyclic coloring with `c Delta^{4//3}//(log Delta)^{1//3}` colors, for some constant `c`.

Interestingly, as far as I know, there is no deterministic construction of an infinite family of graphs with maximum degree `Delta` and with no acyclic coloring with `c Delta` colors, for some constant `c>1` (let alone with `Delta^{1+epsilon}` colors, for some constant `epsilon>0`). This is hard to believe.

## Boxicity of graphs (and dimension of posets) of bounded maximum degree (1986, 1991, 2011)

This is probably the hardest problem on this page. The boxicity of a graph of maximum degree at most `Delta` is known to be `O(Delta (log Delta)^2)`, and there are examples showing that we cannot obtain better than `Omega(Delta log Delta)` (see this paper). What is the right bound? I tend to believe that the lower bound can be improved.

The same questions can be asked for the dimension of posets of height two whose comparability graphs have bounded degree (the two problems are almost equivalent, see this paper).

## Girth and density in hereditary classes (2009)

The *girth* of a graph `G` is the size of a smallest cycle of `G`, and the *average degree* of `G` is `"ad"(G)= 2|E(G)|//|V(G)|`.

Let `cc F` be a hereditary class of graphs (a class closed under taking induced subgraphs), and let `cc "F"_g` be the graphs of `cc F` of girth ast least `g`. I am interested in the following parameter: `mu_{g}(cc F)="sup"_{G in cc "F"_g} "ad"(G)`. It is well known that for the family `cc P` of planar graphs, `mu_{g}(cc P)= {2g}/{g-2}` (this mainly follows from Euler's Formula). More generally, a classical result of Gallucio, Goddyn and Hell implies that in any proper minor-closed family `cc F`, `mu_{g}(cc F)` exists and tends to 2 as `g->oo` (see also this recent paper for a generalisation).

Interestingly, `mu_{g}(cc F)` is a rational number whenever `cc F` is the class of planar graphs, outerplanar graphs, partial 2-trees, but also the class SEG of intersection graphs of segments in the plane (when `g>=5`): it is not difficult to show that `mu_{g}("SEG")= {2g-4}/{g-4}` for any `g>=5`. But for the class CIRCLE of intersection graphs of the chords of a circle, things are quite different. We proved in this paper that `mu_{g}("CIRCLE")= 2sqrt{{g-2}/{g-4}}` for any `g>=5`.

This is fairly surprising and a bit mysterious. What other kind of function of `g` can you obtain? For instance, can you find a hereditary class `cc F` such that `mu_{g}(cc F)=` (some rational function of `g)^{1//3}`? Is it true that `mu_{g}(cc F)` is a rational function of `g` for graphs embeddable on a fixed surface? for any minor-closed class?

## Induced universal graphs for graphs with maximum degree at most two (2008)

Let `F_n` be the class of graphs on `n` vertices and maximum degree at most two. What is the smallest number of vertices in a graph that contains all graphs of `F_n` as induced subgraphs? In this paper, we proved that the answer lies somewhere between `11 |__ n/6 __|` and ` 5 |__ n/2 __|+25 `.