Source author record

Mickael Montassier

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 Information Theory math.IT

Catalog footprint

Research overview

9works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

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

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(G) \rightarrow V(H)$ that maps every edge in $G$ to an edge of the same type in $H$ . Switching a vertex $v$ of a 2-edge-colored or signed graph corresponds to changing the type of each edge incident to $v$ . There is a homomorphism from the signed graph $G$ to the signed graph $H$ if after switching some subset of the vertices of $G$ there is a 2-edge-colored homomorphism from $G$ to $H$ . The chromatic number of a 2-edge-colored (resp. signed) graph $G$ is the order of a smallest 2-edge-colored (resp. signed) graph $H$ such that there is a homomorphism from $G$ to $H$ . The chromatic number of a class of graph is the maximum of the chromatic numbers of the graphs in the class. We study the chromatic numbers of 2-edge-colored and signed graphs (connected and not necessarily connected) of a given bounded maximum degree. More precisely, we provide exact bounds for graphs of maximum degree 2. We then propose specific lower and upper bounds for graphs of maximum degree 3, 4, and 5. We finally propose general bounds for graphs of maximum degree $k$ , for every $k$ .

preprint2016arXiv

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

An $({\cal F},{\cal 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 forest with maximum degree at most $d$ . We prove that every triangle-free planar graph admits an $({\cal F},{\cal F}_5)$ -partition. Moreover we show that if for some integer $d$ there exists a triangle-free planar graph that does not admit an $({\cal F},{\cal F}_d)$ -partition, then it is an NP-complete problem to decide whether a triangle-free planar graph admits such a partition.

preprint2016arXiv

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

An $({\cal I},{\cal 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 of maximum degree at most $d$ . We show that for all $M<3$ and $d \ge \frac{2}{3-M} - 2$ , if a graph has maximum average degree less than $M$ , then it has an $({\cal I},{\cal F}_d)$ -partition. Additionally, we prove that for all $\frac{8}{3} \le M < 3$ and $d \ge \frac{1}{3-M}$ , if a graph has maximum average degree less than $M$ then it has an $({\cal I},{\cal F}_d)$ -partition.

preprint2015arXiv

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

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$ has a feedback vertex set of size at most $\frac{4m}{3g}$ , improving the trivial bound of $\frac{2m}{g}$ . We also prove that every $2$ -connected graph with maximum degree $3$ and order $n$ has a feedback vertex set of size at most $\frac{n+2}{3}$ .

preprint2014arXiv

Large induced forests in planar graphs with girth 4 or 5

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 order $n$ admits an induced forest of order at least $\frac{6n+7}{11}$ , improving the lower bound of Salavatipour [M. R. Salavatipour, Large induced forests in triangle-free planar graphs, Graphs and Combinatorics, 22:113-126, 2006]. We also prove that a planar graph of order $n$ and girth at least $5$ admits an induced forest of order at least $\frac{44n+50}{69}$ .

preprint2013arXiv

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

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 at most d_i for all 1 <= i <= l. In this paper, we focus on complexity aspects of such colorings when l=2,3. More precisely, we prove that, for any fixed integers k,j,g with (k,j) distinct form (0,0) and g >= 3, either every planar graph with girth at least g is (k,j)-colorable or it is NP-complete to determine whether a planar graph with girth at least g is (k,j)-colorable. Also, for any fixed integer k, it is NP-complete to determine whether a planar graph that is either (0,0,0)-colorable or non-(k,k,1)-colorable is (0,0,0)-colorable. Additionally, we exhibit non-(3,1)-colorable planar graphs with girth 5 and non-(2,0)-colorable planar graphs with girth 7.

preprint2012arXiv

Locally identifying coloring of graphs

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 with distinct closed neighborhood, the sets of colors that appear in the closed neighborhood of u and v are distinct. Let $χ_{lid}(G)$ be the minimum number of colors used in a locally identifying vertex-coloring of G. In this paper, we give several bounds on $χ_{lid}$ for different families of graphs (planar graphs, some subclasses of perfect graphs, graphs with bounded maximum degree) and prove that deciding whether $χ_{lid}(G)=3$ for a subcubic bipartite graph $G$ with large girth is an NP-complete problem.

preprint2011arXiv

On two variations of identifying codes

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 light codes. They correspond to fault-detection by successive rounds. We give exact bounds for those two definitions for the family of cycles.

preprint2010arXiv

Covering a graph by forests and a matching

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

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.