M. Montassier · wovepaper

activity

20102021

most citedEntropy compression method applied to graph colorings

37 citations · 50 across the 12 of their papers we have counts for

collaborators

15 papers

$2$ -distance list $(Δ + 2)$ -coloring of planar graphs with girth at least 10

Hoang La, Mickael Montassier

Given a graph $G$ and a list assignment $L (v)$ for each vertex of $v$ of $G$ . A proper $L$ -list-coloring of $G$ is a function that maps every vertex to a color in $L (v)$ such that…

$2$ -distance $(Δ + 2)$ -coloring of sparse graphs

Hoang La, Mickael Montassier

A $2$ -distance $k$ -coloring of a graph is a proper $k$ -coloring of the vertices where vertices at distance at most 2 cannot share the same color. We prove the existence of a $2$ -di…

Star coloring of sparse graphs

Yuehua Bu, Daniel W. Cranston, Mickaël Montassier +2

A proper coloring of the vertices of a graph is called a \emph{star coloring} if the union of every two color classes induces a star forest. The star chromatic number $χ_{s} (G)$ is t…

math.CO2021★ 1 cited

$2$ -distance $(Δ + 1)$ -coloring of sparse graphs using the potential method

Hoang La, Mickael Montassier

A $2$ -distance $k$ -coloring of a graph is a proper $k$ -coloring of the vertices where vertices at distance at most 2 cannot share the same color. We prove the existence of a $2$ -di…

math.CO2020★ 2 cited

The chromatic number of 2-edge-colored and signed graphs of bounded maximum degree

Christopher Duffy, Fabien Jacques, Mickael Montassier +1

A 2-edge-colored graph or a signed graph is a simple graph with two types of edges. A homomorphism from a 2-edge-colored graph $G$ to a 2-edge-colored graph $H$ is a mapping $φ: V(…

A lower bound on the order of the largest induced linear forest in triangle-free planar graphs

François Dross, Mickael Montassier, Alexandre Pinlou

We prove that every triangle-free planar graph of order $n$ and size $m$ has an induced linear forest with at least $\frac{9 n - 2 m}{11}$ vertices, and thus at least $\frac{5n + 8}{…

Partitioning sparse graphs into an independent set and a forest of bounded degree

François Dross, Mickael Montassier, Alexandre Pinlou

An $(I, F_{d})$ -partition of a graph is a partition of the vertices of the graph into two sets $I$ and $F$ , such that $I$ is an independent set and $F$ induces a forest…

Partitioning a triangle-free planar graph into a forest and a forest of bounded degree

François Dross, Mickael Montassier, Alexandre Pinlou

An $(F, F_{d})$ -partition of a graph is a vertex-partition into two sets $F$ and $F_{d}$ such that the graph induced by $F$ is a forest and the one induced by $F_{d}$ is a f…

cs.DM2015★ 1 cited

A lower bound on the order of the largest induced forest in planar graphs with high girth

François Dross, Mickael Montassier, Alexandre Pinlou

We give here new upper bounds on the size of a smallest feedback vertex set in planar graphs with high girth. In particular, we prove that a planar graph with girth $g$ and size $m…

cs.DM2014★ 8 cited

Large induced forests in planar graphs with girth 4 or 5

François Dross, Mickael Montassier, Alexandre Pinlou

We give here some new lower bounds on the order of a largest induced forest in planar graphs with girth $4$ and $5$ . In particular we prove that a triangle-free planar graph of ord…

cs.DM2014★ 37 cited

Entropy compression method applied to graph colorings

Daniel Gonçalves, Mickaël Montassier, Alexandre Pinlou

Based on the algorithmic proof of Lovász local lemma due to Moser and Tardos, the works of Grytczuk et al. on words, and Dujmović et al. on colorings, Esperet and Parreau developed…

Near-colorings: non-colorable graphs and NP-completeness

Mickael Montassier, Pascal Ochem

A graph G is (d_1,..,d_l)-colorable if the vertex set of G can be partitioned into subsets V_1,..,V_l such that the graph G[V_i] induced by the vertices of V_i has maximum degree a…

Locally identifying coloring of graphs

Louis Esperet, Sylvain Gravier, Mickael Montassier +2

We introduce the notion of locally identifying coloring of a graph. A proper vertex-coloring c of a graph G is said to be locally identifying, if for any adjacent vertices u and v…

Covering a graph by forests and a matching

Tomas Kaiser, Mickael Montassier, Andre Raspaud

We prove that for any positive integer $k$ , the edges of any graph whose fractional arboricity is at most $k + 1/ (3 k + 2)$ can be decomposed into $k$ forests and a matching.

cs.DM2010★ 1 cited

On two variations of identifying codes

Olivier Delmas, Sylvain Gravier, Mickael Montassier +1

Identifying codes have been introduced in 1998 to model fault-detection in multiprocessor systems. In this paper, we introduce two variations of identifying codes: weak codes and l…