BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Marthe Bonamy appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
In 1968, Gallai conjectured that the edges of any connected graph with $n$ vertices can be partitioned into $\lceil \frac{n}{2} \rceil$ paths. We show that this conjecture is true for every planar graph. More precisely, we show that every connected planar graph except $K_3$ and $K_5^-$ ($K_5$ minus one edge) can be decomposed into $\lfloor \frac{n}{2} \rfloor$ paths.
The Burning Number Conjecture claims that for every connected graph $G$ of order $n,$ its burning number satisfies $b(G) \le \lceil \sqrt{n} \rceil.$ While the conjecture remains open, we prove that it is asymptotically true when the order of the graph is much larger than its \emph{growth}, which is the maximal distance of a vertex to a well-chosen path in the graph. We prove that the conjecture for graphs of bounded growth reduces to a finite number of cases. We provide the best-known bound on the burning number of a connected graph $G$ of order $n,$ given by $b(G) \le \sqrt{4n/3} + 1,$ improving on the previously known $\sqrt{3n/2}+O(1)$ bound. Using the improved upper bound, we show that the conjecture almost holds for all graphs with minimum degree at least $3$ and holds for all large enough graphs with minimum degree at least $4$. The previous best-known result was for graphs with minimum degree $23$.
We introduce a variant of the well-studied sum choice number of graphs, which we call the interactive sum choice number. In this variant, we request colours to be added to the vertices' colour-lists one at a time, and so we are able to make use of information about the colours assigned so far to determine our future choices. The interactive sum choice number cannot exceed the sum choice number and we conjecture that, except in the case of complete graphs, the interactive sum choice number is always strictly smaller than the sum choice number. In this paper we provide evidence in support of this conjecture, demonstrating that it holds for a number of graph classes, and indeed that in many cases the difference between the two quantities grows as a linear function of the number of vertices.
It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we investigate this problem in graph classes defined by forbidding an induced subgraph. In particular, we provide output-polynomial time algorithms for $K_t$-free graphs and variants. This answers a question of Kanté et al. about enumeration in bipartite graphs.
We prove that if $\mathcal{C}$ is a hereditary class of graphs that is polynomially $χ$-bounded, then the class of graphs that admit decompositions into pieces belonging to $\mathcal{C}$ along cuts of bounded rank is also polynomially $χ$-bounded. In particular, this implies that for every positive integer $k$, the class of graphs of cliquewidth at most $k$ is polynomially $χ$-bounded.
We introduce a model for random geodesic drawings of the complete bipartite graph $K_{n,n}$ on the unit sphere $\mathbb{S}^2$ in $\mathbb{R}^3$, where we select the vertices in each bipartite class of $K_{n,n}$ with respect to two non-degenerate probability measures on $\mathbb{S}^2$. It has been proved recently that many such measures give drawings whose crossing number approximates the Zarankiewicz number (the conjectured crossing number of $K_{n,n}$). In this paper we consider the intersection graphs associated with such random drawings. We prove that for any probability measures, the resulting random intersection graphs form a convergent graph sequence in the sense of graph limits. The edge density of the limiting graphon turns out to be independent of the two measures as long as they are antipodally symmetric. However, it is shown that the triangle densities behave differently. We examine a specific random model, blow-ups of antipodal drawings $D$ of $K_{4,4}$, and show that the triangle density in the corresponding crossing graphon depends on the angles between the great circles containing the edges in $D$ and can attain any value in the interval $\bigl(\frac{83}{12288}, \frac{128}{12288}\bigr)$.
We consider a classic rendezvous game where two players try to meet each other on a set of $n$ locations. In each round, every player visits one of the locations and the game finishes when the players meet at the same location. The goal is to devise strategies for both players that minimize the expected waiting time till the rendezvous. In the asymmetric case, when the strategies of the players may differ, it is known that the optimum expected waiting time of $\frac{n+1}{2}$ is achieved by the wait-for-mommy pair of strategies, where one of the players stays at one location for $n$ rounds, while the other player searches through all the $n$ locations in a random order. However, if we insist that the players are symmetric --- they are expected to follow the same strategy --- then the best known strategy, proposed by Anderson and Weber, achieves an asymptotic expected waiting time of $0.829 n$. We show that the symmetry requirement indeed implies that the expected waiting time needs to be asymptotically larger than in the asymmetric case. Precisely, we prove that for every $n\geqslant 2$, if the players need to employ the same strategy, then the expected waiting time is at least $\frac{n+1}{2}+\varepsilon n$, where $\varepsilon=2^{-36}$.
Let $H$ be an induced subgraph of the torus $C_k^m$. We show that when $k \ge 3$ is even and $|V(H)|$ divides some power of $k$, then for sufficiently large $n$ the torus $C_k^n$ has a perfect vertex-packing with induced copies of $H$. On the other hand, disproving a conjecture of Gruslys, we show that when $k$ is odd and not a prime power, then there exists $H$ such that $|V(H)|$ divides some power of $k$, but there is no $n$ such that $C_k^n$ has a perfect vertex-packing with copies of $H$. We also disprove a conjecture of Gruslys, Leader and Tan by exhibiting a subgraph $H$ of the $k$-dimensional hypercube $Q_k$, such that there is no $n$ for which $Q_n$ has a perfect edge-packing with copies of $H$.
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most $2$ plus the maximum over all subgraphs of the difference between half the number of vertices and the independence number.
An \emph{adjacency labeling scheme} for a given class of graphs is an algorithm that for every graph $G$ from the class, assigns bit strings (labels) to vertices of $G$ so that for any two vertices $u,v$, whether $u$ and $v$ are adjacent can be determined by a fixed procedure that examines only their labels. It is known that planar graphs with $n$ vertices admit a labeling scheme with labels of bit length $(2+o(1))\log{n}$. In this work we improve this bound by designing a labeling scheme with labels of bit length $(\frac{4}{3}+o(1))\log{n}$. In graph-theoretical terms, this implies an explicit construction of a graph on $n^{4/3+o(1)}$ vertices that contains all planar graphs on $n$ vertices as induced subgraphs, improving the previous best upper bound of $n^{2+o(1)}$. Our scheme generalizes to graphs of bounded Euler genus with the same label length up to a second-order term. All the labels of the input graph can be computed in polynomial time, while adjacency can be decided from the labels in constant time.
Gallai's path decomposition conjecture states that the edges of any connected graph on n vertices can be decomposed into at most (n+1)/2 paths. We confirm that conjecture for all graphs with maximum degree at most five.
Let $G$ be a graph with a vertex colouring $α$. Let $a$ and $b$ be two colours. Then a connected component of the subgraph induced by those vertices coloured either $a$ or $b$ is known as a Kempe chain. A colouring of $G$ obtained from $α$ by swapping the colours on the vertices of a Kempe chain is said to have been obtained by a Kempe change. Two colourings of $G$ are Kempe equivalent if one can be obtained from the other by a sequence of Kempe changes. A conjecture of Mohar (2007) asserts that, for $k \geq 3$, all $k$-colourings of a $k$-regular graph that is not complete are Kempe equivalent. It was later shown that all $3$-colourings of a cubic graph that is neither $K_4$ nor the triangular prism are Kempe equivalent. In this paper, we prove that the conjecture holds for each $k\geq 4$. We also report the implications of this result on the validity of the Wang-Swendsen-Kotecký algorithm for the antiferromagnetic Potts model at zero-temperature.
Let I be an independent set of a graph G. Imagine that a token is located on any vertex of I. We can now move the tokens of I along the edges of the graph as long as the set of tokens still defines an independent set of G. Given two independent sets I and J, the Token Sliding problem consists in deciding whether there exists a sequence of independent sets which transforms I into J so that every pair of consecutive independent sets of the sequence can be obtained via a token move. This problem is known to be PSPACE-complete even on planar graphs. In 2014, Demaine et al. asked whether the Token Sliding reconfiguration problem is polynomial time solvable on interval graphs and more generally in chordal graphs. Yamada and Uehara showed in 2016 that a polynomial time transformation can be found in proper interval graphs. In this paper, we answer the first question of Demaine et al. and generalize the result of Yamada and Uehara by showing that we can decide in polynomial time whether two independent sets of an interval graph are in the same connected component. Moveover, we answer similar questions by showing that: (i) determining if there exists a token sliding transformation between every pair of k-independent sets in an interval graph can be decided in polynomial time; (ii) deciding this problem becomes co-NP-hard and even co-W[2]-hard (parameterized by the size of the independent set) on split graphs, a sub-class of chordal graphs.
An incidence of an undirected graph G is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ an edge of $G$ incident with $v$. Two incidences $(v,e)$ and $(w,f)$ are adjacent if one of the following holds: (i) $v = w$, (ii) $e = f$ or (iii) $vw = e$ or $f$. An incidence coloring of $G$ assigns a color to each incidence of $G$ in such a way that adjacent incidences get distinct colors. In 2005, Hosseini Dolama \emph{et al.}~\citep{ds05} proved that every graph with maximum average degree strictly less than $3$ can be incidence colored with $Δ+3$ colors. Recently, Bonamy \emph{et al.}~\citep{Bonamy} proved that every graph with maximum degree at least $4$ and with maximum average degree strictly less than $\frac{7}{3}$ admits an incidence $(Δ+1)$-coloring. In this paper we give bounds for the number of colors needed to color graphs having maximum average degrees bounded by different values between $4$ and $6$. In particular we prove that every graph with maximum degree at least $7$ and with maximum average degree less than $4$ admits an incidence $(Δ+3)$-coloring. This result implies that every triangle-free planar graph with maximum degree at least $7$ is incidence $(Δ+3)$-colorable. We also prove that every graph with maximum average degree less than 6 admits an incidence $(Δ+ 7)$-coloring. More generally, we prove that $Δ+k-1$ colors are enough when the maximum average degree is less than $k$ and the maximum degree is sufficiently large.
In the $k$-Leaf Out-Branching and $k$-Internal Out-Branching problems we are given a directed graph $D$ with a designated root $r$ and a nonnegative integer $k$. The question is to determine the existence of an outbranching rooted at $r$ that has at least $k$ leaves, or at least $k$ internal vertices, respectively. Both these problems were intensively studied from the points of view of parameterized complexity and kernelization, and in particular for both of them kernels with $O(k^2)$ vertices are known on general graphs. In this work we show that $k$-Leaf Out-Branching admits a kernel with $O(k)$ vertices on $\mathcal{H}$-minor-free graphs, for any fixed family of graphs $\mathcal{H}$, whereas $k$-Internal Out-Branching admits a kernel with $O(k)$ vertices on any graph class of bounded expansion.
We show a kernel of at most $13k$ vertices for the Planar Feedback Vertex Set problem restricted to planar graphs, i.e., a polynomial-time algorithm that transforms an input instance $(G,k)$ to an equivalent instance with at most $13k$ vertices. To this end we introduce a few new reduction rules. However, our main contribution is an application of the region decomposition technique in the analysis of the kernel size. We show that our analysis is tight, up to a constant additive term.
Answering a question of Kalai and Meshulam, we prove that graphs without induced cycles of length $3k$ have bounded chromatic number. This implies the very first case of a much broader question asserting that every graph with large chromatic number induces a graph $H$ such that the sum of the Betti numbers of the independence complex of $H$ is also large.
For planar graphs, we consider the problems of \emph{list edge coloring} and \emph{list total coloring}. Edge coloring is the problem of coloring the edges while ensuring that two edges that are adjacent receive different colors. Total coloring is the problem of coloring the edges and the vertices while ensuring that two edges that are adjacent, two vertices that are adjacent, or a vertex and an edge that are incident receive different colors. In their list extensions, instead of having the same set of colors for the whole graph, every vertex or edge is assigned some set of colors and has to be colored from it. A graph is minimally edge or total choosable if it is list edge $Δ$-colorable or list total $(Δ+1)$-colorable, respectively, where $Δ$ is the maximum degree in the graph. It is already known that planar graphs with $Δ\geq 8$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable (Li Xu 2011), and that planar graphs with $Δ\geq 7$ and no triangle sharing a vertex with a $C_4$ or no triangle adjacent to a $C_k$ ($\forall 3 \leq k \leq 6$) are minimally total colorable (Wang Wu 2011). We strengthen here these results and prove that planar graphs with $Δ\geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable.
Let $k$ be an integer. Two vertex $k$-colorings of a graph are \emph{adjacent} if they differ on exactly one vertex. A graph is \emph{$k$-mixing} if any proper $k$-coloring can be transformed into any other through a sequence of adjacent proper $k$-colorings. Jerrum proved that any graph is $k$-mixing if $k$ is at least the maximum degree plus two. We first improve Jerrum's bound using the grundy number, which is the worst number of colors in a greedy coloring. Any graph is $(tw+2)$-mixing, where $tw$ is the treewidth of the graph (Cereceda 2006). We prove that the shortest sequence between any two $(tw+2)$-colorings is at most quadratic (which is optimal up to a constant factor), a problem left open in Bonamy et al. (2012). We also prove that given any two $(χ(G)+1)$-colorings of a cograph (resp. distance-hereditary graph) $G$, we can find a linear (resp. quadratic) sequence between them. In both cases, the bounds cannot be improved by more than a constant factor for a fixed $χ(G)$. The graph classes are also optimal in some sense: one of the smallest interesting superclass of distance-hereditary graphs corresponds to comparability graphs, for which no such property holds (even when relaxing the constraint on the length of the sequence). As for cographs, they are equivalently the graphs with no induced $P_4$, and there exist $P_5$-free graphs that admit no sequence between two of their $(χ(G)+1)$-colorings. All the proofs are constructivist and lead to polynomial-time recoloring algorithm
Two independent sets of a graph are adjacent if they differ on exactly one vertex (i.e. we can transform one into the other by adding or deleting a vertex). Let $k$ be an integer. We consider the reconfiguration graph $TAR_k(G)$ on the set of independent sets of size at least $k$ in a graph $G$, with the above notion of adjacency. Here we provide a cubic-time algorithm to decide whether $TAR_k(G)$ is connected when $G$ is a cograph, thus solving an open question of~[Bonsma 2014]. As a by-product, we also describe a linear-time algorithm which decides whether two elements of $TAR_k(G)$ are in the same connected component.
Erdős and Hajnal conjectured that, for every graph $H$, there exists a constant $c_H$ such that every graph $G$ on $n$ vertices which does not contain any induced copy of $H$ has a clique or a stable set of size $n^{c_H}$. We prove that for every $k$, there exists $c_k>0$ such that every graph $G$ on $n$ vertices not inducing a cycle of length at least $k$ nor its complement contains a clique or a stable set of size $n^{c_k}$.
We prove that for $k\geq 3$, the bound given by Brooks' theorem on the chromatic number of $k$-th powers of graphs of maximum degree $Δ\geq 3$ can be lowered by 1, even in the case of online list coloring.
For graphs of bounded maximum average degree, we consider the problem of 2-distance coloring. This is the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbor receive different colors. It is already known that planar graphs of girth at least 6 and of maximum degree D are list 2-distance (D+2)-colorable when D>=24 (Borodin and Ivanova (2009)) and 2-distance (D+2)-colorable when D>=18 (Borodin and Ivanova (2009)). We prove here that D>=17 suffices in both cases. More generally, we show that graphs with maximum average degree less than 3 and D>=17 are list 2-distance (D+2)-colorable. The proof can be transposed to list injective (D+1)-coloring.
We consider the problem of coloring the squares of graphs of bounded maximum average degree, that is, the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbour receive different colors. Borodin et al. proved in 2004 and 2008 that the squares of planar graphs of girth at least seven and sufficiently large maximum degree $Δ$ are list $(Δ+1)$-colorable, while the squares of some planar graphs of girth six and arbitrarily large maximum degree are not. By Euler's Formula, planar graphs of girth at least $6$ are of maximum average degree less than $3$, and planar graphs of girth at least $7$ are of maximum average degree less than $14/5<3$. We strengthen their result and prove that there exists a function $f$ such that the square of any graph with maximum average degree $m<3$ and maximum degree $Δ\geq f(m)$ is list $(Δ+1)$-colorable. This bound of $3$ is optimal in the sense that the above-mentioned planar graphs with girth $6$ have maximum average degree less than $3$ and arbitrarily large maximum degree, while their square cannot be $(Δ+1)$-colored. The same holds for list injective $Δ$-coloring.
We consider the problem of list edge coloring for planar graphs. Edge coloring is the problem of coloring the edges while ensuring that two edges that are incident receive different colors. A graph is k-edge-choosable if for any assignment of k colors to every edge, there is an edge coloring such that the color of every edge belongs to its color assignment. Vizing conjectured in 1965 that every graph is (D+1)-edge-choosable, where D is the maximum degree. In 1990, Borodin solved the conjecture for planar graphs with maximum degree at least 9, and asked whether the bound could be lowered to 8. We prove here that planar graphs with maximum degree D at least 8 are (D+1)-edge-choosable.
Let $k$ be an integer. Two vertex $k$-colorings of a graph are \emph{adjacent} if they differ on exactly one vertex. A graph is \emph{$k$-mixing} if any proper $k$-coloring can be transformed into any other through a sequence of adjacent proper $k$-colorings. Any graph is $(tw+2)$-mixing, where $tw$ is the treewidth of the graph (Cereceda 2006). We prove that the shortest sequence between any two $(tw+2)$-colorings is at most quadratic, a problem left open in Bonamy et al. (2012). Jerrum proved that any graph is $k$-mixing if $k$ is at least the maximum degree plus two. We improve Jerrum's bound using the grundy number, which is the worst number of colors in a greedy coloring.