Source author record

Laetitia Lemoine

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Long induced paths in graphs

We prove that every 3-connected planar graph on $n$ vertices contains an induced path on $Ω(\log n)$ vertices, which is best possible and improves the best known lower bound by a multiplicative factor of $\log \log n$ . We deduce that any planar graph (or more generally, any graph embeddable on a fixed surface) with a path on $n$ vertices, also contains an induced path on $Ω(\sqrt{\log n})$ vertices. We conjecture that for any $k$ , there is a contant $c(k)$ such that any $k$ -degenerate graph with a path on $n$ vertices also contains an induced path on $Ω((\log n)^{c(k)})$ vertices. We provide examples showing that this order of magnitude would be best possible (already for chordal graphs), and prove the conjecture in the case of interval graphs.

preprint2015arXiv

Equitable partition of graphs into induced forests

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. We show that every graph with an acyclic coloring with at most $k$ colors can be equitably partitioned into $k-1$ induced forests. We also prove that for any integers $d\ge 1$ and $k\ge 3^{d-1}$ , any $d$ -degenerate graph can be equitably partitioned into $k$ induced forests. Each of these results implies the existence of a constant $c$ such that for any $k \ge c$ , any planar graph has an equitable partition into $k$ induced forests. This was conjectured by Wu, Zhang, and Li in 2013.

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.