Source author record

Frédéric Havet

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 Computational Complexity

Catalog footprint

Research overview

10works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On the minimum number of arcs in $k$ -dicritical oriented graphs

The dichromatic number $\dic(D)$ of a digraph $D$ is the least integer $k$ such that $D$ can be partitioned into $k$ directed acyclic digraphs. A digraph is $k$ -dicritical if $\dic(D) = k$ and each proper subgraph $D'$ of $D$ satisfies $\dic(D') \leq k-1$. An oriented graph is a digraph with no directed cycle of length $2$ . For integers $k$ and $n$ , we denote by $o_k(n)$ the minimum number of edges of a $k$ -critical oriented graph on $n$ vertices (with the convention $o_k(n)=+\infty$ if there is no $k$ -dicritical oriented graph of order $n$ ). The main result of this paper is a proof that $o_3(n) \geq \frac{7n+2}{3}$ together with a construction witnessing that $o_3(n) \leq \left \lceil \frac{5n}{2} \right \rceil$ for all $n \geq 12$ . We also give a construction showing that for all sufficiently large $n$ and all $k\geq 3$ , $o_k(n) < (2k-3)n$ , disproving a conjecture of Hoshino and Kawarabayashi. Finally, we prove that, for all $k\geq 2$ , $o_k(n) \geq \pth{ k - \frac{3}{4}-\frac{1}{4k-6}} n + \frac{3}{4(2k-3)}$, improving the previous best known lower bound of Bang-Jensen, Bellitto, Schweser and Stiebitz.

preprint2021arXiv

Powers of paths in tournaments

In this short note we prove that every tournament contains the $k$ -th power of a directed path of linear length. This improves upon recent results of Yuster and of Girão. We also give a complete solution for this problem when $k=2$ , showing that there is always a square of a directed path of length $\lceil 2n/3 \rceil-1$ , which is best possible.

preprint2020arXiv

Cooperative colorings of trees and of bipartite graphs

Given a system $(G_1, \ldots ,G_m)$ of graphs on the same vertex set $V$ , a cooperative coloring is a choice of vertex sets $I_1, \ldots ,I_m$ , such that $I_j$ is independent in $G_j$ and $\bigcup_{j=1}^{m}I_j = V$ . For a class $\mathcal{G}$ of graphs, let $m_{\mathcal{G}}(d)$ be the minimal $m$ such that every $m$ graphs from $\mathcal{G}$ with maximum degree $d$ have a cooperative coloring. We prove that $Ω(\log\log d) \le m_\mathcal{T}(d) \le O(\log d)$ and $Ω(\log d)\le m_\mathcal{B}(d) \le O(d/\log d)$ , where $\mathcal{T}$ is the class of trees and $\mathcal{B}$ is the class of bipartite graphs.

preprint2016arXiv

$χ$ -bounded families of oriented graphs

A famous conjecture of Gyárfás and Sumner states for any tree $T$ and integer $k$ , if the chromatic number of a graph is large enough, either the graph contains a clique of size $k$ or it contains $T$ as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star $S$ and integer $k$ , if the chromatic number of a digraph is large enough, either the digraph contains a clique of size $k$ or it contains $S$ as an induced subgraph. As an evidence, we prove that for any oriented star $S$ , every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order $3$ or $S$ as an induced subdigraph. We then study for which sets ${\cal P}$ of orientations of $P_4$ (the path on four vertices) similar statements hold. We establish some positive and negative results.

preprint2016arXiv

Colouring graphs with constraints on connectivity

A graph $G$ has maximal local edge-connectivity $k$ if the maximum number of edge-disjoint paths between every pair of distinct vertices $x$ and $y$ is at most $k$ . We prove Brooks-type theorems for $k$ -connected graphs with maximal local edge-connectivity $k$ , and for any graph with maximal local edge-connectivity 3. We also consider several related graph classes defined by constraints on connectivity. In particular, we show that there is a polynomial-time algorithm that, given a 3-connected graph $G$ with maximal local connectivity 3, outputs an optimal colouring for $G$ . On the other hand, we prove, for $k \ge 3$ , that $k$ -colourability is NP-complete when restricted to minimally $k$ -connected graphs, and 3-colourability is NP-complete when restricted to $(k-1)$ -connected graphs with maximal local connectivity $k$ . Finally, we consider a parameterization of $k$ -colourability based on the number of vertices of degree at least $k+1$ , and prove that, even when $k$ is part of the input, the corresponding parameterized problem is FPT.

preprint2016arXiv

Subdivisions of oriented cycles in digraphs with large chromatic number

An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle $C$ , there are digraphs containing no subdivision of $C$ (as a subdigraph) and arbitrarily large chromatic number. In contrast, we show that for any $C$ a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number contains a subdivision of $C$ . We prove a similar result for the antidirected cycle on four vertices (in which two vertices have out-degree $2$ and two vertices have in-degree $2$ ).

preprint2013arXiv

Finding an induced subdivision of a digraph

We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) $G$ , does it contain an induced subdivision of a prescribed digraph $D$ ? The complexity of this problem depends on $D$ and on whether $G$ must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP-completeness proofs.

preprint2013arXiv

On wheel-free graphs

A wheel is a graph formed by a chordless cycle and a vertex that has at least three neighbors in the cycle. We prove that every 3-connected graph that does not contain a wheel as a subgraph is in fact minimally 3-connected. We give a new proof of a theorem of Thomassen and Toft: every graph that does not contain a wheel as a subgraph is 3-colorable.

preprint2011arXiv

5-choosability of graphs with 2 crossings

We show that every graph with two crossings is 5-choosable. We also prove that every graph which can be made planar by removing one edge is 5-choosable.

preprint2010arXiv

k-L(2,1)-Labelling for Planar Graphs is NP-Complete for k >= 4

A mapping from the vertex set of a graph G = (V,E) into an interval of integers {0,...,k} is an L(2,1)-labelling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbour are mapped onto distinct integers. It is known that for any fixed k >= 4, deciding the existence of such a labelling is an NP-complete problem while it is polynomial for k <= 3. For even k >= 8, it remains NP-complete when restricted to planar graphs. In this paper, we show that it remains NP-complete for any k >= 4 by reduction from Planar Cubic Two-Colourable Perfect Matching. Schaefer stated without proof that Planar Cubic Two-Colourable Perfect Matching is NP-complete. In this paper we give a proof of this.

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.

Frédéric Havet

Research overview

Is this your work?

10 publications

On the minimum number of arcs in $k$ -dicritical oriented graphs

Powers of paths in tournaments

Cooperative colorings of trees and of bipartite graphs

$χ$ -bounded families of oriented graphs

Colouring graphs with constraints on connectivity

Subdivisions of oriented cycles in digraphs with large chromatic number

Finding an induced subdivision of a digraph

On wheel-free graphs

5-choosability of graphs with 2 crossings

k-L(2,1)-Labelling for Planar Graphs is NP-Complete for k >= 4

See the researcher in context

Building this map preview

Frédéric Havet

Research overview

Is this your work?

10 publications

On the minimum number of arcs in kkk-dicritical oriented graphs

Powers of paths in tournaments

Cooperative colorings of trees and of bipartite graphs

χχχ-bounded families of oriented graphs

Colouring graphs with constraints on connectivity

Subdivisions of oriented cycles in digraphs with large chromatic number

Finding an induced subdivision of a digraph

On wheel-free graphs

5-choosability of graphs with 2 crossings

k-L(2,1)-Labelling for Planar Graphs is NP-Complete for k >= 4

See the researcher in context

Building this map preview

On the minimum number of arcs in $k$ -dicritical oriented graphs

$χ$ -bounded families of oriented graphs