Open problems #
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.
The number of perfect matchings modulo 3 in random cubic bipartite graphs (2022) #
In this paper I conjectured that for any integers \(k,\ell\) the probability that a large random \(k\) -regular bipartite graph has a number of perfect matching that is congruent to \(\ell \pmod k\) is at least some positive constant that only depends on \(k\) . Actually I believe this constant should tend to \(1/k\) as the size of the graph tends to infinity.
The average degree of unit-disk graphs (2021) #
Given a point set \(X\) in the plane, the unit-disk graph on \(X\) is the graph with vertex set \(X\) in which two points \(x,y \in X\) are adjacent if and only if their Euclidean distance is at most 1. The average degree of a graph \(G\) is the average of the degrees of the vertices of \(G\) . We conjectured in this paper that for any unit-disk graph \(G\) , the average degree of \(G\) is at most \(4\omega(G)\) , where \(\omega(G)\) denotes the size of a maximum clique in \(G\) . If true, this would be best possible. It is well known that the maximum degree of a unit-disk graph \(G\) is at most \(6\omega(G)\) , so the average degree is also at most \(6\omega(G)\) . We can improve on that slightly, by showing a bound of \(5.68\omega(G)\) , which is far from impressive. I have spent quite some time on this problem and I would be happy to see any significant improvement on our bound !
Coloring unit-disk graphs on an annulus (2021) #
Given a subset \(S\) of points in a metric space \((X,d)\) , the unit-disk graph on \(S\) is the graph with vertex set \(S\) in which two points \(x,y \in S\) are adjacent if and only if \(d(x,y)\le 1\) .
Fix some real \(\varepsilon>0\) , and consider the metric space \(A\) obtained from a Euclidean rectangle \(R\) of height \(\sqrt{3}/2\) and sufficiently large width (as a function of \(\varepsilon>0\) ), by identifying the left side of \(R\) with its right side. Is it true that for any unit disk graph \(G\) on \(A\) , \(\chi(G)\le (1+\varepsilon)\omega(G)\) ? See the conclusion of this paper for the motivation. If the answer to this question is positive we think we can obtain an improved distributed algorithm in the plane. Note that if we consider the points in \(R\) rather than in \(A\) , the corresponding unit-disk graph is a co-comparability graph, and thus \(\chi(G)=\omega(G)\) .
Isometric universal graphs (2021) #
A subgraph \(H\) of \(G\) is isometric if the distances between the vertices of \(H\) in \(H\) are the same as the distances of the corresponding vertices of \(G\) in \(G\) . In this paper we proved that there is a graph on \(3^{n+o(n)}\) vertices that contains all \(n\) -vertex graphs as isometric subgraphs. Can the base of the exponent be improved? Probably not significantly below \(\sqrt{3}\) , as this would improve the best known distance labelling scheme for the class of \(n\) -vertex graphs.
Universal posets (2010, 2020) #
Hamkins asked here what is the smallest number of elements in a poset that contains all \(n\) -element posets as (induced) subposets. A simple counting argument shows that \(2^{n/4}\) elements are necessary, and a natural conjecture is that it is also sufficient, up to a lower order term. See here for the construction of a graph of this size that contains all \(n\) -vertex comparability graphs as induced subgraphs. If our construction was itself a comparability graph this would solve the conjecture, but unfortunately it is not.
Bipartite induced subgraphs (2018) #
We conjectured in this paper that any triangle-free graph of minimum degree \(d\) contains an induced subgraph which is bipartite and has minimum degree \(\Omega(\log d)\) . This was solved up to a \(\log \log d\) factor in this paper. It “only” remains to close the \(\log \log d\) gap !
Boxicity and circular dimension of graphs (2018) #
The boxicity of a graph \(G\) is the smallest \(k\) such that \(G\) can be represented as the (edge-)intersection of \(k\) interval graphs on the same vertex set. The circular dimension of a graph \(G\) is the smallest \(k\) such that \(G\) can be represented as the (edge-)intersection of \(k\) circular interval graphs on the same vertex set. In this paper we proved that graphs with no \(K_t\) -minor have boxity \(O(t^2 \log t)\) and circular dimension \(O(t^2)\) . Can either of these bounds be improved ?
While the boxity of graphs has been extensively studied, much less is known about the circular dimension. What is the maximum circular dimension of an \(n\) -vertex graph? A simple counting argument shows that almost all \(n\) -vertex graphs have circular dimension \(\Omega(n/\log n)\) . What is the maximum circular dimension of a graph with maximum degree \(\Delta\) ? It is known to be \(\Omega(\Delta)\) and \(O(\Delta \log \Delta/\log \log \Delta)\) (see this paper for references).
List coloring of degenerate graphs (2016) #
A graph is \(d\) -degenerate if there is an order on its vertices such that each vertex has at most \(d\) neighbors before it in the order. A simple greedy procedure shows that if each vertex of a \(d\) -degenerate graph has a list of \(d+1\) colors, then we can find a proper coloring such that each vertex is colored with a color from its list. It was proved in this paper that if each vertex of a \(d\) -degenerate has a list of \(d+1\) colors, except one vertex that has a list of \(d\) colors, then there is again a proper coloring such that each vertex is colored with a color from its list. (I should note that this is not proved explicitly in their paper, they actually prove something stronger when \(d+1\) is prime, but the result above easily follows from their proof.) The main point is that their proof uses the polynomial method and is purely existential. Can you find a combinatorial/constructive proof of this result?
Fractional coloring of degenerate triangle-free graphs (2016) #
David Harris conjectured the following in this paper: any \(d\) -degenerate triangle-free graph has fractional chromatic number \(O(d/\log d)\) .
Feedback vertex set in planar digraphs (2016) #
The digirth of a digraph is the length of a shortest directed cycle (it is infinite if the digraph is acyclic, i.e. the graph has no directed cycle). In this paper we proved that any \(n\) -vertex planar digraph \(G\) of digirth at least \(g\) has a set \(X\) of at most \({(2n-6)}/g\) vertices such that \(G-X\) is acyclic. What is the best possible value for the size of such a set \(X\) ? There is a lower bound of \({(n-1)}/{g}\) , and the validity of a conjecture of Goemans and Williamson would imply that \(|X|\le {3n}/{2g}\) is possible.
Bisections of cubic graphs (2015) #
A bisection of a graph is a partition of its vertex set into two sets whose size differ by at most 1. An almost-bistection is a partition of the vertex set into two sets whose size differ by at most 2. In this paper we proved that every cubic graph has a bisection such that each part induces a disjoint union of paths on at most 3 vertices. The Petersen graph shows that this is best possible for bisections, but we conjectured that every cubic graph has an almost-bisection such that each part induces a disjoint union of components on at most 2 vertices (the conjecture is already open for cubic bridgeless graphs).
Union and intersection of perfect matchings in cubic graphs #
The Berge conjecture asserts that the edge-set of any cubic bridgeless graph can be covered by 5 perfect matchings, and the Fan-Raspaud conjecture asserts that every cubic bridgeless graph has 3 perfect matchings with empty intersection (the first conjecture implies the second). For each of these two conjectures, the weaker version where 5 and 3 are replaced by any constant is still open.
- There is a constant \(k\) such that any cubic brideless graph can be covered by \(k\) perfect matchings.
- There is a constant \(k\) such that any cubic brideless graph has \(k\) perfect matchings with empty intersection.
For the two problems the best known value for \(k\) is \(O(\log n)\) in \(n\) -vertex cubic bridgeless graphs, which easily follows from the fact that the vector \((1/3,1/3,...,1/3)\) lies in the perfect matching polytope of any cubic bridgeless graph. Any improvement over \(O(\log n)\) would interesting (even if it depends on \(n\) ).
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\ge 4\) , any planar graph has an equitable partition into \(k\) induced forests (this proved a conjecture formulated by Wu, Zhang, and Li in 2013).
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 \le i\le 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.
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]\ne 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]\ne 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\) ).
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 \(\mathcal{F}\) be a hereditary class of graphs (a class closed under taking induced subgraphs), and let \(\mathcal{F}_g\) be the graphs of \(\mathcal{F}\) of girth at least \(g\) . I am interested in the following parameter: \(\mu_{g}(\mathcal{F})=\sup_{G \in \mathcal{F}_g} ad(G)\) . It is well known that for the family \(\mathcal{P}\) of planar graphs, \(\mu_{g}(\mathcal{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 \(\mathcal{F}\) , \(\mu_{g}(\mathcal{F})\) exists and tends to 2 as \(g\to \infty\) (see also this paper for a generalisation).
Interestingly, \(\mu_{g}(\mathcal{F})\) is a rational number whenever \(\mathcal{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\ge 5\) ): it is not difficult to show that \(\mu_{g}(SEG)= {2g-4}/{(g-4)}\) for any \(g\ge 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)= 2\sqrt{{(g-2)}/{(g-4)}}\) for any \(g\ge 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 \(\mathcal{F}\) such that \(\mu_{g}(\mathcal{F})=\) (some rational function of \(g)^{1/3}\) ? Is it true that \(\mu_{g}(\mathcal{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-2016) #
Let \(\mathcal{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 \(\mathcal{F}_n\) as induced subgraphs? In this paper, we proved that the answer lies somewhere between \(11 n/6\) and \( 5n/2+25 \) . In this paper, it was proved that the answer is at most \(2n-1\) . In two particular cases (when all the components are large, or all the components are small) they proved that the answer is a constant away from \(11 n/6\) .
Solved problems #
3-coloring bipartite planar graphs in the LOCAL model (2018) #
In this paper we proved that 3-coloring planar bipartite graphs on \(n\) vertices in the LOCAL model of computation takes \(\Omega(\sqrt{n})\) rounds. Is there an algorithm matching this round compexity ?
An algorithm matching this complexity (up to polylogarithmic terms) was given in 2023 in this paper, in the more general case of bipartite graphs (which are not necessarily planar).
Long induced paths (2016) #
In this paper we conjectured that for any integer \(k\) there is a constant \(c\) such that any \(k\) -degenerate graph with a path of length \(n\) has an induced path of length \(\Omega(\log^c n)\) . This would be best possible. The best known bound is \(\Omega(\log \log n)\) . The case of (topologically) minor-closed classes was recently solved in this paper.
A counterexample was given in 2023 by Defrain and Raymond (see here).
Recognition of graphs with no k independent cycles (2022) #
We say that a graph is \(O_k\) -free if it does not contain \(k\) pairwise vertex-disjoint and non-adjacent cycles. Is it polynomial to recognize whether a graph is \(O_k\) -free ? This is already open for \(k=2\) , and is connected to a conjecture of Ngoc Khang Le on the number of induced paths in these graphs, see this paper.
Problem solved in 2023 by Nguyen, Scott and Seymour (see here)
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: \mathbb{N} \to \mathbb{N}\) 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?
Problem solved in 2021 by Dvořák and Norin (see here).
Polynomial chi-boundedness (2013) #
We say that a class of graphs \(\mathcal{F}\) is \(\chi\) -bounded if there is a function \(f\) such that for any graph \(G \in \mathcal{F}\) , \(\chi(G) \le f(\omega(G))\) , where \(\chi(G)\) and \(\omega(G)\) stand for the chromatic number and the clique number of \(G\) , respectively.
I conjectured that if \(\mathcal{F}\) is hereditary (i.e. closed under taking induced subgraphs), and \(\chi\) -bounded, then there is a real \(c\) (depending on \(\mathcal{F}\) ) such that for any graph \(G \in \mathcal{F}\) , \(\chi(G) \le \omega(G)^c\) .
A counterexample was constructed in this paper in 2022. See also this paper for a counterexample to a related conjecture of mine.