Source author record

Alexandre Pinlou

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

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

Research overview

14works

2topics

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$ .

preprint2018arXiv

On non-repetitive sequences of arithmetic progressions:the cases $k \in \{4,5,6,7,8\}$

A $d$ -subsequence of a sequence $φ= x_1\dots x_n$ is a subsequence $x_i x_{i+d} x_{i+2d} \dots$ , for any positive integer $d$ and any $i$ , $1 \le i \le n$ . A \textit{ $k$ -Thue sequence} is a sequence in which every $d$ -subsequence, for $1 \le d \le k$ , is non-repetitive, i.e. it contains no consecutive equal subsequences. In 2002, Grytczuk proposed a conjecture that for any $k$ , $k+2$ symbols are enough to construct a $k$ -Thue sequences of arbitrary lengths. So far, the conjecture has been confirmed for $k \in \{1,2,3,5\}$ . Here, we present two different proving techniques, and confirm it for all $k$ , with $2 \le k \le 8$ .

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}$ .

preprint2015arXiv

Entropy compression method applied to graph colorings

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 a framework to prove upper bounds for several chromatic numbers (in particular acyclic chromatic index, star chromatic number and Thue chromatic number) using the so-called \emph{entropy compression method}. Inspired by this work, we propose a more general framework and a better analysis. This leads to improved upper bounds on chromatic numbers and indices. In particular, every graph with maximum degree $Δ$ has an acyclic chromatic number at most $\frac{3}{2}Δ^{\frac43} + O(Δ)$ . Also every planar graph with maximum degree $Δ$ has a facial Thue choice number at most $Δ+ O(Δ^\frac 12)$ and facial Thue choice index at most $10$ .

preprint2014arXiv

Homomorphisms of signed planar graphs

Signed graphs are studied since the middle of the last century. Recently, the notion of homomorphism of signed graphs has been introduced since this notion captures a number of well known conjectures which can be reformulated using the definitions of signed homomorphism. In this paper, we introduce and study the properties of some target graphs for signed homomorphism. Using these properties, we obtain upper bounds on the signed chromatic numbers of graphs with bounded acyclic chromatic number and of signed planar graphs with given girth.

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}$ .

preprint2014arXiv

Planar graphs with $Δ\geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable

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.

preprint2013arXiv

Application of entropy compression in pattern avoidance

In combinatorics on words, a word $w$ over an alphabet $Σ$ is said to avoid a pattern $p$ over an alphabet $Δ$ if there is no factor $f$ of $w$ such that $f= (p)$ where $h: Δ^*\toΣ^*$ is a non-erasing morphism. A pattern $p$ is said to be $k$ -avoidable if there exists an infinite word over a $k$ -letter alphabet that avoids $p$ . We give a positive answer to Problem 3.3.2 in Lothaire's book "Algebraic combinatorics on words", that is, every pattern with $k$ variables of length at least $2^k$ (resp. $3\times2^{k-1}$ ) is 3-avoidable (resp. 2-avoidable). This improves previous bounds due to Bell and Goh, and Rampersad.

preprint2013arXiv

Graphs with maximum degree D at least 17 and maximum average degree less than 3 are list 2-distance (D+2)-colorable

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.

preprint2013arXiv

List coloring the square of sparse graphs with large degree

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.

preprint2013arXiv

Locally identifying coloring in bounded expansion classes of graphs

A proper vertex coloring of a graph is said to be locally identifying if the sets of colors in the closed neighborhood of any two adjacent non-twin vertices are distinct. The lid-chromatic number of a graph is the minimum number of colors used by a locally identifying vertex-coloring. In this paper, we prove that for any graph class of bounded expansion, the lid-chromatic number is bounded. Classes of bounded expansion include minor closed classes of graphs. For these latter classes, we give an alternative proof to show that the lid-chromatic number is bounded. This leads to an explicit upper bound for the lid-chromatic number of planar graphs. This answers in a positive way a question of Esperet et al [L. Esperet, S. Gravier, M. Montassier, P. Ochem and A. Parreau. Locally identifying coloring of graphs. Electronic Journal of Combinatorics, 19(2), 2012.].

preprint2011arXiv

The Domination Number of Grids

In this paper, we conclude the calculation of the domination number of all $n\times m$ grid graphs. Indeed, we prove Chang's conjecture saying that for every $16\le n\le m$ , $γ(G_{n,m})=\lfloor\frac{(n+2)(m+2)}{5}\rfloor -4$ .

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.

Alexandre Pinlou

Research overview

Is this your work?

14 publications

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

On non-repetitive sequences of arithmetic progressions:the cases $k \in \{4,5,6,7,8\}$

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

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

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

Entropy compression method applied to graph colorings

Homomorphisms of signed planar graphs

Large induced forests in planar graphs with girth 4 or 5

Planar graphs with $Δ\geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable

Application of entropy compression in pattern avoidance

Graphs with maximum degree D at least 17 and maximum average degree less than 3 are list 2-distance (D+2)-colorable

List coloring the square of sparse graphs with large degree

Locally identifying coloring in bounded expansion classes of graphs

The Domination Number of Grids

See the researcher in context

Building this map preview

Alexandre Pinlou

Research overview

Is this your work?

14 publications

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

On non-repetitive sequences of arithmetic progressions:the cases k∈{4,5,6,7,8}k \in \{4,5,6,7,8\}k∈{4,5,6,7,8}

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

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

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

Entropy compression method applied to graph colorings

Homomorphisms of signed planar graphs

Large induced forests in planar graphs with girth 4 or 5

Planar graphs with Δ≥7Δ\geq 7Δ≥7 and no triangle adjacent to a C4C_4C4​ are minimally edge and total choosable

Application of entropy compression in pattern avoidance

Graphs with maximum degree D at least 17 and maximum average degree less than 3 are list 2-distance (D+2)-colorable

List coloring the square of sparse graphs with large degree

Locally identifying coloring in bounded expansion classes of graphs

The Domination Number of Grids

See the researcher in context

Building this map preview

On non-repetitive sequences of arithmetic progressions:the cases $k \in \{4,5,6,7,8\}$

Planar graphs with $Δ\geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable