### International journals with program committee

[BibTeX] [Abstract]

We prove a conjecture of Nadjafi-Arani, Khodashenas and Ashrafi on the difference between the Szeged and Wiener index of a graph. Namely, if is a 2-connected non-complete graph on vertices, then . Furthermore, the equality is obtained if and only if is the complete graph with an extra vertex attached to either or vertices of . We apply our method to strengthen some known results on the difference between the Szeged and Wiener index of bipartite graphs, graphs of girth at least five, and the difference between the revised Szeged and Wiener index. We also propose a stronger version of the aforementioned conjecture.

```
@article{bklps17,
title = {On the difference between the Szeged and Wiener index},
abstract = {We prove a conjecture of Nadjafi-Arani, Khodashenas and Ashrafi on the difference between the Szeged and Wiener index of a graph. Namely, if is a 2-connected non-complete graph on vertices, then . Furthermore, the equality is obtained if and only if is the complete graph with an extra vertex attached to either or vertices of . We apply our method to strengthen some known results on the difference between the Szeged and Wiener index of bipartite graphs, graphs of girth at least five, and the difference between the revised Szeged and Wiener index. We also propose a stronger version of the aforementioned conjecture.},
journal = {Applied Mathematics and Computation},
committee = {Yes},
author = {Bonamy, M. and Knor, M. and Lužar, B. and Pinlou, A. and Škrekovski, R.},
year = {2017},
volume = {312},
pages = {202-213},
%%Arxiv = {1602.05184},
Pdf = {bklps17.pdf},
DOI = {10.1016/j.amc.2017.05.047},
URL = {http://www.sciencedirect.com/science/article/pii/S009630031730348X}
}
```

[BibTeX] [Abstract]

In this paper, we introduce and study the properties of some target graphs for 2-edge-colored homomorphism. Using these properties, we obtain in particular that the 2-edge-colored chromatic number of the class of triangle-free planar graphs is at most 50. We also show that it is at least 12.

```
@article{ops17,
Abstract = {In this paper, we introduce and study the properties of some target graphs for 2-edge-colored homomorphism. Using these properties, we obtain in particular that the 2-edge-colored chromatic number of the class of triangle-free planar graphs is at most 50. We also show that it is at least 12.},
%% Arxiv = {1401.3308},
Author = {Ochem, P. and Pinlou, A. and Sen, S.},
Pdf = {ops17.pdf},
Title = {Homomorphisms of 2-edge-colored triangle-free planar graphs},
Committee = {Yes},
Journal = {Journal of Graph Theory},
Volume = {85},
Number={1},
Pages = {258-277},
%URL = {http://onlinelibrary.wiley.com/journal/10.1002/%28ISSN%291097-0118},
Year = {2017},
DOI = {10.1002/jgt.22059},
}
```

[BibTeX] [Abstract]

An -partition of a graph is a vertex-partition into two sets and such that the graph induced by is a forest and the one induced by is a forest with maximum degree at most . We prove that every triangle-free planar graph admits an -partition. Moreover we show that if for some integer there exists a triangle-free planar graph that does not admit an -partition, then it is an NP-complete problem to decide whether a triangle-free planar graph admits such a partition.

```
@article{dmp17,
title = {Partitioning a triangle-free planar graph into a forest and a forest of bounded degree},abstract = {An -partition of a graph is a vertex-partition into two sets and such that the graph induced by is a forest and the one induced by is a forest with maximum degree at most . We prove that every triangle-free planar graph admits an -partition. Moreover we show that if for some integer there exists a triangle-free planar graph that does not admit an -partition, then it is an NP-complete problem to decide whether a triangle-free planar graph admits such a partition. },
author = {Dross, F. and Montassier, M. and Pinlou, A.},
year = {2017},
%%Arxiv = {1601.01523},
committee = {Yes},
journal = {European Journal of Combinatorics},
volume = {66},
pages = {81-94},
Pdf = {dmp17.pdf},
DOI = {10.1016/j.ejc.2017.06.014}
}
```

[BibTeX] [Abstract]

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 and size has a feedback vertex set of size at most , improving the trivial bound of . We also prove that every -connected graph with maximum degree and order has a feedback vertex set of size at most .

```
@article{dmp16d,
title = {A lower bound on the order of the largest induced forest in planar graphs with high girth},
abstract = {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 and size has a feedback vertex set of size at most , improving the trivial bound of . We also prove that every -connected graph with maximum degree and order has a feedback vertex set of size at most .},
author = {Dross, F. and Montassier, M. and Pinlou, A.},
year = {2016},
%% Arxiv = {1504.01949},
Committee = {Yes},
Journal = {Discrete Applied Mathematics},
Volume = {214},
Pages = {99-107},
DOI = {10.1016/j.dam.2016.06.011},
Pdf = {dmp16d.pdf},
}
```

[BibTeX] [Abstract]

For planar graphs, we consider the

problems of \emphlist edge coloring and \emphlist 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 -colorable,

respectively, where is the maximum degree in the graph.It is already known that planar graphs with and no

triangle adjacent to a are minimally edge and total choosable (Li

Xu 2011), and that planar graphs with and no triangle

sharing a vertex with a or no triangle adjacent to a

() are minimally total colorable (Wang Wu

2011). We strengthen here these results and prove that planar graphs

with and no triangle adjacent to a are minimally

edge and total choosable.

```
@article{blp16,
Abstract = {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 -colorable,
respectively, where is the maximum degree in the graph.
It is already known that planar graphs with and no
triangle adjacent to a are minimally edge and total choosable (Li
Xu 2011), and that planar graphs with and no triangle
sharing a vertex with a or no triangle adjacent to a
() are minimally total colorable (Wang Wu
2011). We strengthen here these results and prove that planar graphs
with and no triangle adjacent to a are minimally
edge and total choosable.},
%% Arxiv = {1405.3422},
Author = {Bonamy, M. and Lév{\^e}que, B. and Pinlou, A.},
Pdf = {blp16.pdf},
Title = {Planar graphs with and no triangle adjacent to a are minimally edge- and total-choosable},
Committee = {Yes},
Journal = {Discrete Mathematics and Theoretical Computer Science},
Volume = {17},
Number = {3},
URL = {http://www.dmtcs.org/},
Year = {2016},
}
```

[BibTeX] [Abstract]

A graph is planar if it can be embedded on the plane without edge-crossings. A graph is

2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the

vertices of the external face is outerplanar (i.e. with all its vertices on the external face).

An oriented k-coloring of an oriented graph G is a homomorphism from G to an oriented

graph H of order k. We prove that every oriented triangle-free planar graph has an oriented

chromatic number at most 40, that improves the previous known bound of 47 [Borodin,

O. V. and Ivanova, A. O., An oriented colouring of planar graphs with girth at least 4,

Sib. Electron. Math. Reports, vol. 2, 239-249, 2005]. We also prove that every oriented 2-

outerplanar graph has an oriented chromatic number at most 40, that improves the previous

known bound of 67 [Esperet, L. and Ochem, P. Oriented colouring of 2-outerplanar graphs,

Inform. Process. Lett., vol. 101(5), 215-219, 2005].

```
@article{op14,
Abstract = {A graph is planar if it can be embedded on the plane without edge-crossings. A graph is
2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the
vertices of the external face is outerplanar (i.e. with all its vertices on the external face).
An oriented k-coloring of an oriented graph G is a homomorphism from G to an oriented
graph H of order k. We prove that every oriented triangle-free planar graph has an oriented
chromatic number at most 40, that improves the previous known bound of 47 [Borodin,
O. V. and Ivanova, A. O., An oriented colouring of planar graphs with girth at least 4,
Sib. Electron. Math. Reports, vol. 2, 239-249, 2005]. We also prove that every oriented 2-
outerplanar graph has an oriented chromatic number at most 40, that improves the previous
known bound of 67 [Esperet, L. and Ochem, P. Oriented colouring of 2-outerplanar graphs,
Inform. Process. Lett., vol. 101(5), 215-219, 2005].},
Author = {Ochem, P. and Pinlou, A.},
Committee = {Yes},
Journal = {Graphs and Combinatorics},
DOI = {10.1007/s00373-013-1283-2},
Pdf = {op14.pdf},
Title = {Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs},
Volume = {30},
Number = {2},
Pages = {439-453},
Year = {2014}}
```

[BibTeX] [Abstract]

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 are list 2-distance ()-colorable when $\Delta \ge 24$ (Borodin and Ivanova (2009)) and 2-distance ($\Delta + 2$)-colorable when $\Delta\ge 18$ (Borodin and Ivanova (2009)). We prove here that $\Delta \ge 17$ suffices in both cases. More generally, we show that graphs with maximum average degree less than 3 and $\Delta \ge 17$ are list 2-distance ($\Delta + 2$)-colorable. The proof can be transposed to list injective ($\Delta+ 1$)-coloring.

```
@article{blp14b,
Abstract = {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 are list 2-distance ()-colorable when $\Delta \ge 24$ (Borodin and Ivanova (2009)) and 2-distance ($\Delta + 2$)-colorable when $\Delta\ge 18$ (Borodin and Ivanova (2009)). We prove here that $\Delta \ge 17$ suffices in both cases. More generally, we show that graphs with maximum average degree less than 3 and $\Delta \ge 17$ are list 2-distance ($\Delta + 2$)-colorable. The proof can be transposed to list injective ($\Delta+ 1$)-coloring.},
Author = {Bonamy, M. and Lév{\^e}que, B. and Pinlou, A.},
Pdf = {blp14b.pdf},
Committee = {Yes},
Pages = {19-32},
Journal = {Discrete Mathematics},
Volume = {317},
DOI = {10.1016/j.disc.2013.10.022},
Title = {Graphs with maximum degree and maximum average degree less than 3 are list 2-distance ()-colorable},
Year = {2014}}
```

[BibTeX] [Abstract]

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 -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 are of maximum average degree less than , and

planar graphs of girth at least 7 are of maximum average degree less than .

We strengthen their result and prove that there exists a function f such that the square of

any graph with maximum average degreem and maximum degree –

colorable. This bound of 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 -colored. The same holds for list injective -coloring.

```
@article{blp14c,
Abstract = {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 -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 are of maximum average degree less than , and
planar graphs of girth at least 7 are of maximum average degree less than .
We strengthen their result and prove that there exists a function f such that the square of
any graph with maximum average degreem and maximum degree is list -
colorable. This bound of 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 -colored. The same holds for list injective -coloring.},
Author = {Bonamy, M. and Lévêque, B. and Pinlou, A.},
Pdf = {blp14c.pdf},
Committee = {Yes},
Journal = {European Journal of Combinatorics},
Volume = {41},
Pages = {128-137},
DOI = {10.1016/j.ejc.2014.03.006},
Title = {List coloring the square of sparse graphs with large degree},
Year = {2014}}
```

[BibTeX] [Abstract]

In combinatorics on words, a word over an alphabet is said to avoid a pattern over an alphabet if there is no factor of such that where is a non-erasing morphism. A pattern is said to be -avoidable if there exists an infinite word over a -letter alphabet that avoids . We give a positive answer to Problem 3.3.2 in Lothaire’s book “Algebraic combinatorics on words”, that is, every pattern with variables of length at least (resp. ) is 3-avoidable (resp. 2-avoidable). This improves previous bounds due to Bell and Goh, and Rampersad.

```
@article{op14b,
Abstract = {In combinatorics on words, a word over an alphabet is said to avoid a pattern over an alphabet if there is no factor of such that where is a non-erasing morphism. A pattern is said to be -avoidable if there exists an infinite word over a -letter alphabet that avoids . We give a positive answer to Problem 3.3.2 in Lothaire's book ``Algebraic combinatorics on words'', that is, every pattern with variables of length at least (resp. ) is 3-avoidable (resp. 2-avoidable). This improves previous bounds due to Bell and Goh, and Rampersad.},
%% Arxiv = {1301.1873},
Author = {Ochem, P. and Pinlou, A.},
Pdf = {op14b.pdf},
Title = {Application of entropy compression in pattern avoidance},
Committee = {Yes},
Journal = {The Electronic Journal of Combinatorics},
Volume = {21},
Number = {2},
Pages = {1-12},
URL = {http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p7},
Year = {2014}}
```

[BibTeX] [Abstract]

For graphs of bounded maximum average degree, we consider the problem of -distance coloring, that is, the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbour receive different colors. We prove that graphs with maximum average degree less than and maximum degree at least are -distance -colorable, which is optimal and improves previous results from Dolama and Sopena, and from Borodin et al. We prove that graphs with maximum average degree less than (resp. , ) and maximum degree at least (resp. , ) are list -distance -colorable, which improves previous results from Borodin et al, and from Ivanova. We prove that any graph with maximum average degree less than and with large enough maximum degree (depending only on ) can be list -distance -colored. There exist graphs with arbitrarily large maximum degree and maximum average degree less than that cannot be -distance -colored: the question of what happens between and remains open. We prove also that any graph with maximum average degree can be list -distance -colored ( depending only on ). It is optimal as there exist graphs with arbitrarily large maximum degree and maximum average degree less than that cannot be -distance colored with less than colors. We then justify that most of the above results can be transposed to injective list coloring with one color less.

```
@article{blp14,
Abstract = {For graphs of bounded maximum average degree, we consider the problem of -distance coloring, that is, the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbour receive different colors. We prove that graphs with maximum average degree less than and maximum degree at least are -distance -colorable, which is optimal and improves previous results from Dolama and Sopena, and from Borodin et al. We prove that graphs with maximum average degree less than (resp. , ) and maximum degree at least (resp. , ) are list -distance -colorable, which improves previous results from Borodin et al, and from Ivanova. We prove that any graph with maximum average degree less than and with large enough maximum degree (depending only on ) can be list -distance -colored. There exist graphs with arbitrarily large maximum degree and maximum average degree less than that cannot be -distance -colored: the question of what happens between and remains open. We prove also that any graph with maximum average degree can be list -distance -colored ( depending only on ). It is optimal as there exist graphs with arbitrarily large maximum degree and maximum average degree less than that cannot be -distance colored with less than colors. We then justify that most of the above results can be transposed to injective list coloring with one color less.},
Title = {2-distance coloring of sparse graphs},
Author = {Bonamy, M. and Lévêque, B. and Pinlou, A.},
Committee = {Yes},
Journal = {Journal of Graph Theory},
Pdf = {blp14.pdf},
Volume = {77},
Number = {3},
Pages = {190-218},
DOI = {10.1002/jgt.21782},
Year = {2014}}
```

[BibTeX] [Abstract]

Gallucio, Goddyn and Hell proved in 2001 that in any minor-closed class, graphs with large enough girth have a homomorphism to any given odd cycle. In this paper, we study the computational aspects of this problem. We show that for any minor-closed class containing all planar graphs, and such that all minimal forbidden minors are 3-connected, the following holds: for any there is a such that every graph of girth at least in has a homomorphism to , but deciding whether a graph of girth in has a homomorphism to is NP-complete. The classes of graphs on which this result applies include planar graphs, -minor free graphs, and graphs with bounded Colin de Verdière parameter (for instance, linklessly embeddable graphs).

We also show that the same dichotomy occurs in problems related to a question of Havel (1969) and a conjecture of Steinberg (1976) about the 3-colorability of sparse planar graphs.

```
@article{emop13,
Abstract = {Gallucio, Goddyn and Hell proved in 2001 that in any minor-closed class, graphs with large enough girth have a homomorphism to any given odd cycle. In this paper, we study the computational aspects of this problem. We show that for any minor-closed class containing all planar graphs, and such that all minimal forbidden minors are 3-connected, the following holds: for any there is a such that every graph of girth at least in has a homomorphism to , but deciding whether a graph of girth in has a homomorphism to is NP-complete. The classes of graphs on which this result applies include planar graphs, -minor free graphs, and graphs with bounded Colin de Verdi{\`e}re parameter (for instance, linklessly embeddable graphs).
We also show that the same dichotomy occurs in problems related to a question of Havel (1969) and a conjecture of Steinberg (1976) about the 3-colorability of sparse planar graphs.},
Author = {Esperet, L. and Montassier, M. and Ochem, P. and Pinlou, A.},
Committee = {Yes},
Journal = {Journal of Graph Theory},
Number = {1},
Pages = {85-102},
Pdf = {emop13.pdf},
Title = {A complexity dichotomy for the coloring of sparse graphs},
Url = {http://dx.doi.org/10.1002/jgt.21659},
Volume = {73},
Year = {2013},
Bdsk-Url-1 = {http://dx.doi.org/10.1002/jgt.21659}}
```

[BibTeX] [Abstract]

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

```
@article{gpp13,
Abstract = {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.].},
%% Arxiv = {1212.5468},
Author = {Goncalves, D. and Parreau, A. and Pinlou, A.},
Committee = {Yes},
Journal = {Discrete Applied Mathematics},
Volume = {161},
Number = {18},
Pages = {2946-2951},
DOI = {10.1016/j.dam.2013.07.003},
Pdf = {gpp13.pdf},
Title = {Locally identifying coloring in bounded expansion classes of graphs},
Year = {2013}}
```

[BibTeX] [Abstract]

A contact representation by triangles of a graph is a set of triangles in the plane

such that two triangles intersect on at most one point, each triangle represents a

vertex of the graph and two triangles intersects if and only if their corresponding

vertices are adjacent. de Fraysseix, Ossona de Mendez and Rosenstiehl proved that

every planar graph admits a contact representation by triangles. We strengthen this

in terms of a simultaneous contact representation by triangles of a planar map and

of its dual.

A primal-dual contact representation by triangles of a planar map is a contact

representation by triangles of the primal and a contact representation by triangles

of the dual such that for every edge uv, bordering faces f and g, the intersection

between the triangles corresponding to u and v is the same point as the intersection

between the triangles corresponding to f and g. We prove that every 3-connected

planar map admits a primal-dual contact representation by triangles. Moreover, the

interiors of the triangles form a tiling of the triangle corresponding to the outer face

and each contact point is a node of exactly three triangles. Then we show that these

representations are in one-to-one correspondence with generalized Schnyder woods

defined by Felsner for 3-connected planar maps.

```
@article{glp12,
Abstract = {A contact representation by triangles of a graph is a set of triangles in the plane
such that two triangles intersect on at most one point, each triangle represents a
vertex of the graph and two triangles intersects if and only if their corresponding
vertices are adjacent. de Fraysseix, Ossona de Mendez and Rosenstiehl proved that
every planar graph admits a contact representation by triangles. We strengthen this
in terms of a simultaneous contact representation by triangles of a planar map and
of its dual.
A primal-dual contact representation by triangles of a planar map is a contact
representation by triangles of the primal and a contact representation by triangles
of the dual such that for every edge uv, bordering faces f and g, the intersection
between the triangles corresponding to u and v is the same point as the intersection
between the triangles corresponding to f and g. We prove that every 3-connected
planar map admits a primal-dual contact representation by triangles. Moreover, the
interiors of the triangles form a tiling of the triangle corresponding to the outer face
and each contact point is a node of exactly three triangles. Then we show that these
representations are in one-to-one correspondence with generalized Schnyder woods
defined by Felsner for 3-connected planar maps.},
Author = {Goncalves, D. and Lév{\^e}que, B. and Pinlou, A.},
Committee = {Yes},
Journal = {Discrete and Computational Geometry},
Number = {1},
Pages = {239-254},
Pdf = {glp12.pdf},
Title = {Triangle contact representations and duality},
Url = {http://dx.doi.org/10.1007/s00454-012-9400-1},
Volume = {48},
Year = {2012},
Bdsk-Url-1 = {http://dx.doi.org/10.1007/s00454-012-9400-1}}
```

[BibTeX] [Abstract]

In a directed graph, a star is an arborescence with at least one arc, in which the root dominates all the other vertices. A galaxy is a vertex-disjoint union of stars. In this paper, we consider the \textscSpanning Galaxy problem of deciding whether a digraph has a spanning galaxy or not. We show that although this problem is NP-complete (even when restricted to acyclic digraphs), it becomes polynomial-time solvable when restricted to strong digraphs.

In fact, we prove that restricted to this class, the \textscSpanning Galaxy problem is equivalent to the problem of deciding if a strong digraph has a strong digraph with an even number of vertices. We then show a polynomial time algorithm to solve this problem.

We also consider some parameterized version of the \textscSpanning Galaxy problem.

Finally, we improve some results concerning the notion of directed star arboricity of a digraph , which is the minimum number of galaxies needed to cover all the arcs of . We show in particular that for every digraph and that for every acyclic digraph .

```
@article{ghpt12,
Abstract = {In a directed graph, a star is an arborescence with at least one arc, in which the root dominates all the other vertices. A galaxy is a vertex-disjoint union of stars. In this paper, we consider the {\textsc{Spanning} Galaxy} problem of deciding whether a digraph {} has a spanning galaxy or not. We show that although this problem is {NP-complete} (even when restricted to acyclic digraphs), it becomes polynomial-time solvable when restricted to strong digraphs.
In fact, we prove that restricted to this class, the {\textsc{Spanning} Galaxy} problem is equivalent to the problem of deciding if a strong digraph has a strong digraph with an even number of vertices. We then show a polynomial time algorithm to solve this problem.
We also consider some parameterized version of the {\textsc{Spanning} Galaxy} problem.
Finally, we improve some results concerning the notion of directed star arboricity of a digraph {,} which is the minimum number of galaxies needed to cover all the arcs of {.} We show in particular that for every digraph {} and that {} for every acyclic digraph {.}},
Author = {Goncalves, D. and Havet, F. and Pinlou, A. and Thomass{\'e}, S.},
Committee = {Yes},
Journal = {Discrete Applied Mathematics},
Number = {6},
Pages = {744--754},
Pdf = {ghpt12.pdf},
Title = {On spanning galaxies in digraphs},
Url = {http://dx.doi.org/10.1016/j.dam.2011.07.013},
Volume = {160},
Year = {2012},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.dam.2011.07.013}}
```

[BibTeX] [Abstract]

In this paper, we conclude the calculation of the domination number of all

n×m grid graphs. Indeed, we prove Chang’s conjecture saying that for every $16 łeq n łeq m, \gamma(G_n,m) = łeftłfloor((n+2)(m+2))/5\right\rfloor – 4$.

```
@article{gprt11,
Abstract = {In this paper, we conclude the calculation of the domination number of all
n×m grid graphs. Indeed, we prove Chang's conjecture saying that for every $16 \leq n \leq m, \gamma(G_{n,m}) = \left\lfloor((n+2)(m+2))/5\right\rfloor - 4$.},
Author = {Goncalves, D. and Pinlou, A. and Rao, M. and Thomassé, S.},
Committee = {Yes},
Journal = {SIAM Journal of Discrete Mathematics},
Keywords = {grid, domination},
Pages = {1443-1453},
Pdf = {gprt11.pdf},
Title = {The Domination Number of Grids},
Url = {http://dx.doi.org/10.1137/11082574},
Volume = {25},
Year = {2011},
Bdsk-Url-1 = {http://dx.doi.org/10.1137/11082574}}
```

[BibTeX] [Abstract]

In this paper, we study homomorphisms of 2-edge-colored graphs, that is graphs with edges colored with two colors. We consider various graph classes (outerplanar graphs, partial 2-trees, partial 3-trees, planar graphs) and the problem is to find, for each class, the smallest number of vertices of a 2-edge-colored graph H such that each graph of the considered class admits a homomorphism to H.

```
@article{moprs10,
Abstract = {
In this paper, we study homomorphisms of 2-edge-colored graphs, that is graphs with edges colored with two colors. We consider various graph classes (outerplanar graphs, partial 2-trees, partial 3-trees, planar graphs) and the problem is to find, for each class, the smallest number of vertices of a 2-edge-colored graph H such that each graph of the considered class admits a homomorphism to H.},
Author = {Montejano, A. and Ochem, P. and Pinlou, A. and Raspaud, A. and Sopena, {É}.},
Doi = {10.1016/j.dam.2009.09.017},
Issn = {0166-218X},
Journal = {Discrete Applied Mathematics},
Keywords = {Graph coloring; Maximum average degree; Homorphism; Outerplanar graph; Partial $k$-tree; Planar graph; Girth; Discharging procedure},
Number = {12},
Pages = {1365-1379},
Pdf = {moprs10.pdf},
Title = {Homomorphisms of 2-edge-colored graphs},
Url = {http://www.sciencedirect.com/science/article/B6TYW-4XNVT7P-1/2/9503c3da9ee58db4cf8d97f07fd4467d},
Volume = {158},
Year = {2010},
Bdsk-Url-1 = {http://www.sciencedirect.com/science/article/B6TYW-4XNVT7P-1/2/9503c3da9ee58db4cf8d97f07fd4467d},
Bdsk-Url-2 = {http://dx.doi.org/10.1016/j.dam.2009.09.017}}
```

[BibTeX] [Abstract]

For graphs of bounded maximum degree, we consider acyclic t-improper colourings, that is, colourings in which each bipartite subgraph consisting of the edges between two colour classes is acyclic, and each colour class induces a graph with maximum degree at most t.

We consider the supremum, over all graphs of maximum degree at most d, of the acyclic t-improper chromatic number and provide t-improper analogues of results by Alon, McDiarmid and Reed [N. Alon, C.J.H. McDiarmid, B. Reed, Acyclic coloring of graphs, Random Structures Algorithms 2 (3) (1991) 277-288] and Fertin, Raspaud and Reed [G. Fertin, A. Raspaud, B. Reed, Star coloring of graphs, J. Graph Theory 47 (3) (2004) 163-182].

```
@article{aekmp10,
Abstract = {
For graphs of bounded maximum degree, we consider acyclic t-improper colourings, that is, colourings in which each bipartite subgraph consisting of the edges between two colour classes is acyclic, and each colour class induces a graph with maximum degree at most t.
We consider the supremum, over all graphs of maximum degree at most d, of the acyclic t-improper chromatic number and provide t-improper analogues of results by Alon, McDiarmid and Reed [N. Alon, C.J.H. McDiarmid, B. Reed, Acyclic coloring of graphs, Random Structures Algorithms 2 (3) (1991) 277-288] and Fertin, Raspaud and Reed [G. Fertin, A. Raspaud, B. Reed, Star coloring of graphs, J. Graph Theory 47 (3) (2004) 163-182].},
Author = {Addario-Berry, L. and Esperet, L. and Kang, R.J. and McDiarmid, C.J.H and Pinlou, A.},
Doi = {10.1016/j.disc.2008.09.009},
Issn = {0012-365X},
Journal = {Discrete Mathematics},
Keywords = {Bounded degree graphs},
Note = {Selected Papers from the 21st British Combinatorial Conference},
Number = {2},
Pages = {223 - 229},
Pdf = {aekmp10.pdf},
Title = {Acyclic improper colourings of graphs with bounded maximum degree},
Url = {http://www.sciencedirect.com/science/article/B6V00-4THS3KV-2/2/627c703785ef66a3c99541bedc1b3cd2},
Volume = {310},
Year = {2010},
Bdsk-Url-1 = {http://www.sciencedirect.com/science/article/B6V00-4THS3KV-2/2/627c703785ef66a3c99541bedc1b3cd2},
Bdsk-Url-2 = {http://dx.doi.org/10.1016/j.disc.2008.09.009}}
```

[BibTeX] [Abstract]

An oriented $k$-coloring of an oriented graph $G$ is a homomorphism from $G$ to an oriented graph $H$ of order $k$. We prove that every oriented graph with a maximum average degree less than $\frac103$ and girth at least $5$ has an oriented chromatic number at most $16$. This implies that every oriented planar graph with girth at least $5$ has an oriented chromatic number at most $16$, that improves the previous known bound of 19 due to Borodin et al. [O.V. Borodin, A.V. Kostochka, J. Ne\v setril, A. Raspaud, É. Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math. 206 (1999) 77–89].

```
@article{pin09,
Abstract = {An oriented $k$-coloring of an oriented graph $G$ is a homomorphism from $G$ to an oriented graph $H$ of order $k$. We prove that every oriented graph with a maximum average degree less than $\frac{10}{3}$ and girth at least $5$ has an oriented chromatic number at most $16$. This implies that every oriented planar graph with girth at least $5$ has an oriented chromatic number at most $16$, that improves the previous known bound of 19 due to Borodin et al. [O.V. Borodin, A.V. Kostochka, J. Ne{\v s}etril, A. Raspaud, {É}. Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math. 206 (1999) 77--89].},
Author = {Pinlou, A.},
Committee = {Yes},
Doi = {10.1016/j.disc.2008.04.030},
Issn = {0012-365X},
Journal = {Discrete Mathematics},
Keywords = {oriented coloring; planar graph; girth; discharging procedure; maximum average degree},
Number = {8},
Pages = {2108 - 2118},
Pdf = {pin09.pdf},
Title = {An oriented coloring of planar graphs with girth at least five},
Url = {http://dx.doi.org/10.1016/j.disc.2008.04.030},
Volume = {309},
Year = {2009},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.disc.2008.04.030}}
```

[BibTeX] [Abstract]

Let $M$ be an additive abelian group. A strong oriented coloring of an oriented graph $G$ is a mapping $\phi$ from $V(G)$ to $M$ such that (1) $\phi(u) \neq \phi(v)$ whenever $uv$ is an arc in $G$ and (2) $\phi(v) – \phi(u) \neq -(\phi(t) – \phi(z))$ whenever $uv$ and $zt$ are two arcs in $G$. We say that $G$ has a $M$-strong-oriented coloring. The strong oriented chromatic number of an oriented graph, denoted by $\chi_s(G)$, is the minimal order of a group $M$, such that $G$ has $M$-strong-oriented coloring. This notion was introduced by Ne\v set\v ril and Raspaud. In this paper, we pose the following problem: Let $i \ge 4$ be an integer. Let G be an oriented planar graph without cycles of lengths 4 to $i$. Which is the strong oriented chromatic number of $G$? Our aim is to determine the impact of triangles on the strong oriented coloring. We give some hints of answers to this problem by proving that: (1) the strong oriented chromatic number of any oriented planar graph without cycles of lengths 4 to 12 is at most 7, and (2) the strong oriented chromatic number of any oriented planar graph without cycles of length 4 or 6 is at most 19.

```
@article{mop08,
Abstract = {Let $M$ be an additive abelian group. A strong oriented coloring of an oriented graph $G$ is a mapping $\phi$ from $V(G)$ to $M$ such that (1) $\phi(u) \neq \phi(v)$ whenever $uv$ is an arc in $G$ and (2) $\phi(v) - \phi(u) \neq -(\phi(t) - \phi(z))$ whenever $uv$ and $zt$ are two arcs in $G$. We say that $G$ has a $M$-strong-oriented coloring. The strong oriented chromatic number of an oriented graph, denoted by $\chi_s(G)$, is the minimal order of a group $M$, such that $G$ has $M$-strong-oriented coloring. This notion was introduced by Ne{\v s}et{\v r}il and Raspaud. In this paper, we pose the following problem: Let $i \ge 4$ be an integer. Let G be an oriented planar graph without cycles of lengths 4 to $i$. Which is the strong oriented chromatic number of $G$? Our aim is to determine the impact of triangles on the strong oriented coloring. We give some hints of answers to this problem by proving that: (1) the strong oriented chromatic number of any oriented planar graph without cycles of lengths 4 to 12 is at most 7, and (2) the strong oriented chromatic number of any oriented planar graph without cycles of length 4 or 6 is at most 19. },
Author = {Montassier, M. and Ochem, P. and Pinlou, A.},
Committee = {Yes},
Journal = {Discrete Mathematics and Theoretical Computer Science},
Keywords = {strong oriented coloring, oriented coloring, planar graphs},
Number = {1},
Pages = {1--24},
Pdf = {mop08.pdf},
Title = {Strong oriented chromatic number of planar graphs without short cycles},
Url = {http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/455},
Volume = {10},
Year = {2008},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RFFpOUy5vYmplY3RzV05TLmtleXNWJGNsYXNzog8QgASABqISE4ACgAOAB1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgNGRpXTlMuZGF0YU8RAYAAAAAAAYAAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMkCXXlIKwAAAAnPtAltb3AwOC5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACdALw6j3hFBERiBDQVJPAAUAAwAACSAAAAAAAAAAAAAAAAAAAAANYmlibGlvZ3JhcGhpZQAAEAAIAADJAk9pAAAAEQAIAADDqOl0AAAAAQAQAAnPtAAJyZMACEyrAACTJwACADVNYWNpbnRvc2ggSEQ6VXNlcnM6YWxleDpUaGVzZTpiaWJsaW9ncmFwaGllOm1vcDA4LnBkZgAADgAUAAkAbQBvAHAAMAA4AC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgAoVXNlcnMvYWxleC9UaGVzZS9iaWJsaW9ncmFwaGllL21vcDA4LnBkZgATAAEvAAAVAAIAC///AACABdIcHR4fWCRjbGFzc2VzWiRjbGFzc25hbWWjHyAhXU5TTXV0YWJsZURhdGFWTlNEYXRhWE5TT2JqZWN0XxAsLi4vLi4vLi4vLi4vLi4vVGhlc2UvYmlibGlvZ3JhcGhpZS9tb3AwOC5wZGbSHB0kJaIlIVxOU0RpY3Rpb25hcnkSAAGGoF8QD05TS2V5ZWRBcmNoaXZlcgAIABEAFgAfACgAMgA1ADoAPABFAEsAUgBdAGUAbABvAHEAcwB2AHgAegB8AIYAkwCYAKACJAImAisCNAI/AkMCUQJYAmECkAKVApgCpQKqAAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAArw=},
Bdsk-Url-1 = {http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/455}}
```

[BibTeX] [Abstract]

A homomorphism from an oriented graph $G$ to an oriented graph $H$ is an arc-preserving mapping $f$ from $V(G)$ to $V(H)$, that is $f(x)f(y)$ is an arc in $H$ whenever $xy$ is an arc in $G$. The oriented chromatic number of $G$ is the minimum order of an oriented graph $H$ such that $G$ has a homomorphism to $H$. In this paper, we determine the oriented chromatic number of the class of partial 2-trees for every girth $g\ge 3$. We also give an upper bound for the oriented chromatic number of planar graphs with girth at least 11.

```
@article{op08,
Abstract = {A homomorphism from an oriented graph $G$ to an oriented graph $H$ is an arc-preserving mapping $f$ from $V(G)$ to $V(H)$, that is $f(x)f(y)$ is an arc in $H$ whenever $xy$ is an arc in $G$. The oriented chromatic number of $G$ is the minimum order of an oriented graph $H$ such that $G$ has a homomorphism to $H$. In this paper, we determine the oriented chromatic number of the class of partial 2-trees for every girth $g\ge 3$. We also give an upper bound for the oriented chromatic number of planar graphs with girth at least 11.},
Author = {Ochem, P. and Pinlou, A.},
Committee = {Yes},
Journal = {Information Processing Letters},
Pages = {82--86},
Pdf = {op08.pdf},
Title = {Oriented colorings of partial 2-trees},
Url = {http://dx.doi.org/10.1016/j.ipl.2008.04.007},
Volume = {108},
Year = {2008},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RFFpOUy5vYmplY3RzV05TLmtleXNWJGNsYXNzog8QgASABqISE4ACgAOAB1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgNGRpXTlMuZGF0YU8RAXwAAAAAAXwAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMkCXXlIKwAAAAnPtAhvcDA4LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACdAgxRLyKgAAAAAAAAAAAAUAAwAACSAAAAAAAAAAAAAAAAAAAAANYmlibGlvZ3JhcGhpZQAAEAAIAADJAk9pAAAAEQAIAADFEtYKAAAAAQAQAAnPtAAJyZMACEyrAACTJwACADRNYWNpbnRvc2ggSEQ6VXNlcnM6YWxleDpUaGVzZTpiaWJsaW9ncmFwaGllOm9wMDgucGRmAA4AEgAIAG8AcAAwADgALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASACdVc2Vycy9hbGV4L1RoZXNlL2JpYmxpb2dyYXBoaWUvb3AwOC5wZGYAABMAAS8AABUAAgAL//8AAIAF0hwdHh9YJGNsYXNzZXNaJGNsYXNzbmFtZaMfICFdTlNNdXRhYmxlRGF0YVZOU0RhdGFYTlNPYmplY3RfECsuLi8uLi8uLi8uLi8uLi9UaGVzZS9iaWJsaW9ncmFwaGllL29wMDgucGRm0hwdJCWiJSFcTlNEaWN0aW9uYXJ5EgABhqBfEA9OU0tleWVkQXJjaGl2ZXIACAARABYAHwAoADIANQA6ADwARQBLAFIAXQBlAGwAbwBxAHMAdgB4AHoAfACGAJMAmACgAiACIgInAjACOwI/Ak0CVAJdAosCkAKTAqACpQAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAAK3},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.ipl.2008.04.007}}
```

[BibTeX] [Abstract]

A homomorphism from an oriented graph $G$ to an oriented graph $H$ is a mapping $\phi$ from the set of vertices of $G$ to the set of vertices of $H$ such that $\phi(u)\phi(v)$ is an arc in $H$ whenever $uv$ is an arc in $G$. The oriented chromatic index of an oriented graph $G$ is the minimum number of vertices in an oriented graph $H$ such that there exists a homomorphism from the line digraph $LD(G)$ of $G$ to $H$ (the line digraph $LD(G)$ of $G$ is given by $V(LD(G)) = A(G)$ and $ab \in A(LD(G))$ whenever $a = uv$ and $b = vw$. We give upper bounds for the oriented chromatic index of graphs with bounded acyclic chromatic number, of planar graphs and of graphs with bounded degree. We also consider lower and upper bounds of oriented chromatic number in terms of oriented chromatic index. We finally prove that the problem of deciding whether an oriented graph has oriented chromatic index at most $k$ is polynomial time solvable if $k łe 3$ and is NP-complete if $k \ge 4$.

```
@article{ops08,
Abstract = {A homomorphism from an oriented graph $G$ to an oriented graph $H$ is a mapping $\phi$ from the set of vertices of $G$ to the set of vertices of $H$ such that $\phi(u)\phi(v)$ is an arc in $H$ whenever $uv$ is an arc in $G$. The oriented chromatic index of an oriented graph $G$ is the minimum number of vertices in an oriented graph $H$ such that there exists a homomorphism from the line digraph $LD(G)$ of $G$ to $H$ (the line digraph $LD(G)$ of $G$ is given by $V(LD(G)) = A(G)$ and $ab \in A(LD(G))$ whenever $a = uv$ and $b = vw$. We give upper bounds for the oriented chromatic index of graphs with bounded acyclic chromatic number, of planar graphs and of graphs with bounded degree. We also consider lower and upper bounds of oriented chromatic number in terms of oriented chromatic index. We finally prove that the problem of deciding whether an oriented graph has oriented chromatic index at most $k$ is polynomial time solvable if $k \le 3$ and is NP-complete if $k \ge 4$.},
Author = {Ochem, P. and Pinlou, A. and Sopena, {É}.},
Committee = {Yes},
Journal = {Journal of Graph Theory},
Keywords = {oriented coloring, oriented graphs, oriented chromatic index, oriented graphs},
Number = {4},
Pages = {313--332},
Pdf = {ops08.pdf},
Title = {On the oriented chromatic index of oriented graphs},
Url = {http://dx.doi.org/10.1002/jgt.20286},
Volume = {57},
Year = {2008},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RFFpOUy5vYmplY3RzV05TLmtleXNWJGNsYXNzog8QgASABqISE4ACgAOAB1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgNGRpXTlMuZGF0YU8RAYAAAAAAAYAAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMkCXXlIKwAAAAnPtAlvcHMwOC5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACdAkw/LBuFBERiBDQVJPAAUAAwAACSAAAAAAAAAAAAAAAAAAAAANYmlibGlvZ3JhcGhpZQAAEAAIAADJAk9pAAAAEQAIAADD8rOoAAAAAQAQAAnPtAAJyZMACEyrAACTJwACADVNYWNpbnRvc2ggSEQ6VXNlcnM6YWxleDpUaGVzZTpiaWJsaW9ncmFwaGllOm9wczA4LnBkZgAADgAUAAkAbwBwAHMAMAA4AC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgAoVXNlcnMvYWxleC9UaGVzZS9iaWJsaW9ncmFwaGllL29wczA4LnBkZgATAAEvAAAVAAIAC///AACABdIcHR4fWCRjbGFzc2VzWiRjbGFzc25hbWWjHyAhXU5TTXV0YWJsZURhdGFWTlNEYXRhWE5TT2JqZWN0XxAsLi4vLi4vLi4vLi4vLi4vVGhlc2UvYmlibGlvZ3JhcGhpZS9vcHMwOC5wZGbSHB0kJaIlIVxOU0RpY3Rpb25hcnkSAAGGoF8QD05TS2V5ZWRBcmNoaXZlcgAIABEAFgAfACgAMgA1ADoAPABFAEsAUgBdAGUAbABvAHEAcwB2AHgAegB8AIYAkwCYAKACJAImAisCNAI/AkMCUQJYAmECkAKVApgCpQKqAAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAArw=},
Bdsk-Url-1 = {http://dx.doi.org/10.1002/jgt.20286}}
```

[BibTeX] [Abstract]

A homomorphism from an oriented graph $G$ to an oriented graph $H$ is an arc-preserving mapping $\phi$ from $V(G)$ to $V(H)$, that is $\phi(x)\phi(y$) is an arc in $H$ whenever $xy$ is an arc in $G$. The oriented chromatic number of $G$ is the minimum order of an oriented graph $H$ such that $G$ has a homomorphism to $H$. The oriented chromatic index of $G$ is the minimum order of an oriented graph $H$ such that the line-digraph of $G$ has a homomorphism to $H$. In this paper, we determine for every $k \ge 3$ the oriented chromatic number and the oriented chromatic index of the class of oriented outerplanar graphs with girth at least $k$.

```
@article{ps06,
Abstract = {A homomorphism from an oriented graph $G$ to an oriented graph $H$ is an arc-preserving mapping $\phi$ from $V(G)$ to $V(H)$, that is $\phi(x)\phi(y$) is an arc in $H$ whenever $xy$ is an arc in $G$. The oriented chromatic number of $G$ is the minimum order of an oriented graph $H$ such that $G$ has a homomorphism to $H$. The oriented chromatic index of $G$ is the minimum order of an oriented graph $H$ such that the line-digraph of $G$ has a homomorphism to $H$. In this paper, we determine for every $k \ge 3$ the oriented chromatic number and the oriented chromatic index of the class of oriented outerplanar graphs with girth at least $k$.},
Author = {Pinlou, A. and Sopena, {É}.},
Committee = {Yes},
Journal = {Information Processing Letters},
Keywords = {oriented chromatic number, oriented chromatic index, oriented coloring, girth, outerplanar graphs, oriented graphs},
Number = {3},
Pages = {97--104},
Pdf = {ps06.pdf},
Title = {Oriented vertex and arc colorings of outerplanar graphs},
Url = {http://dx.doi.org/10.1016/j.ipl.2006.06.012},
Volume = {100},
Year = {2006},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RFFpOUy5vYmplY3RzV05TLmtleXNWJGNsYXNzog8QgASABqISE4ACgAOAB1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgNGRpXTlMuZGF0YU8RAYAAAAAAAYAAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMkCXXlIKwAAAAnPtAlwczA2YS5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACdAvwQ9UzEJJTkFoRG1wAAUAAwAACSAAAAAAAAAAAAAAAAAAAAANYmlibGlvZ3JhcGhpZQAAEAAIAADJAk9pAAAAEQAIAADBDzisAAAAAQAQAAnPtAAJyZMACEyrAACTJwACADVNYWNpbnRvc2ggSEQ6VXNlcnM6YWxleDpUaGVzZTpiaWJsaW9ncmFwaGllOnBzMDZhLnBkZgAADgAUAAkAcABzADAANgBhAC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgAoVXNlcnMvYWxleC9UaGVzZS9iaWJsaW9ncmFwaGllL3BzMDZhLnBkZgATAAEvAAAVAAIAC///AACABdIcHR4fWCRjbGFzc2VzWiRjbGFzc25hbWWjHyAhXU5TTXV0YWJsZURhdGFWTlNEYXRhWE5TT2JqZWN0XxAsLi4vLi4vLi4vLi4vLi4vVGhlc2UvYmlibGlvZ3JhcGhpZS9wczA2YS5wZGbSHB0kJaIlIVxOU0RpY3Rpb25hcnkSAAGGoF8QD05TS2V5ZWRBcmNoaXZlcgAIABEAFgAfACgAMgA1ADoAPABFAEsAUgBdAGUAbABvAHEAcwB2AHgAegB8AIYAkwCYAKACJAImAisCNAI/AkMCUQJYAmECkAKVApgCpQKqAAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAArw=},
Bdsk-File-2 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RFFpOUy5vYmplY3RzV05TLmtleXNWJGNsYXNzog8QgASABqISE4ACgAOAB1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgNGRpXTlMuZGF0YU8RAYQAAAAAAYQAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMkCXXlIKwAAAAnPtApwczA2YTIucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACdAww9cfflBERiBDQVJPAAUAAwAACSAAAAAAAAAAAAAAAAAAAAANYmlibGlvZ3JhcGhpZQAAEAAIAADJAk9pAAAAEQAIAADD1xFuAAAAAQAQAAnPtAAJyZMACEyrAACTJwACADZNYWNpbnRvc2ggSEQ6VXNlcnM6YWxleDpUaGVzZTpiaWJsaW9ncmFwaGllOnBzMDZhMi5wZGYADgAWAAoAcABzADAANgBhADIALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASAClVc2Vycy9hbGV4L1RoZXNlL2JpYmxpb2dyYXBoaWUvcHMwNmEyLnBkZgAAEwABLwAAFQACAAv//wAAgAXSHB0eH1gkY2xhc3Nlc1okY2xhc3NuYW1lox8gIV1OU011dGFibGVEYXRhVk5TRGF0YVhOU09iamVjdF8QLS4uLy4uLy4uLy4uLy4uL1RoZXNlL2JpYmxpb2dyYXBoaWUvcHMwNmEyLnBkZtIcHSQloiUhXE5TRGljdGlvbmFyeRIAAYagXxAPTlNLZXllZEFyY2hpdmVyAAgAEQAWAB8AKAAyADUAOgA8AEUASwBSAF0AZQBsAG8AcQBzAHYAeAB6AHwAhgCTAJgAoAIoAioCLwI4AkMCRwJVAlwCZQKVApoCnQKqAq8AAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAACwQ==},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.ipl.2006.06.012}}
```

[BibTeX] [Abstract]

A homomorphism from an oriented graph $G$ to an oriented graph $H$ is a mapping

$\phi$ from the set of vertices of $G$ to the set of vertices of $H$ such that $\vec\phi(u)\phi(v)$ is an arc in $H$ whenever $\vecuv$ is an arc in $G$. The oriented chromatic index of an oriented graph $G$ is the minimum number of vertices in an oriented graph $H$ such that there exists a homomorphism from the line digraph $LD(G)$ of $G$ to $H$ (Recall that $LD(G)$ is given by $V(LD(G)) = A(G)$ and $\vecab \in A(LD(G))$ whenever $a = \vecuv$ and $b = \vecvw$. We prove that every oriented subcubic graph has oriented chromatic index at most 7 and construct a subcubic graph with oriented chromatic index 6.

```
@article{pin06,
Abstract = {A homomorphism from an oriented graph $G$ to an oriented graph $H$ is a mapping
$\phi$ from the set of vertices of $G$ to the set of vertices of $H$ such that $\vec{\phi(u)\phi(v)}$ is an arc in $H$ whenever $\vec{uv}$ is an arc in $G$. The oriented chromatic index of an oriented graph $G$ is the minimum number of vertices in an oriented graph $H$ such that there exists a homomorphism from the line digraph $LD(G)$ of $G$ to $H$ (Recall that $LD(G)$ is given by $V(LD(G)) = A(G)$ and $\vec{ab} \in A(LD(G))$ whenever $a = \vec{uv}$ and $b = \vec{vw}$. We prove that every oriented subcubic graph has oriented chromatic index at most 7 and construct a subcubic graph with oriented chromatic index 6.},
Author = {Pinlou, A.},
Committee = {Yes},
Journal = {Electronic Journal of Combinatorics},
Keywords = {oriented coloring, cubic graphs, oriented chromatic index, oriented graphs},
Number = {1},
Pages = {1--13},
Pdf = {pin06.pdf},
Title = {On oriented arc-coloring of subcubic graphs},
Url = {http://www.combinatorics.org/Volume_13/Abstracts/v13i1r69.html},
Volume = {13},
Year = {2006},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RFFpOUy5vYmplY3RzV05TLmtleXNWJGNsYXNzog8QgASABqISE4ACgAOAB1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgNGRpXTlMuZGF0YU8RAYAAAAAAAYAAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMkCXXlIKwAAAAnPtAlwaW4wNi5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACdAmwRHs3VBERiBDQVJPAAUAAwAACSAAAAAAAAAAAAAAAAAAAAANYmlibGlvZ3JhcGhpZQAAEAAIAADJAk9pAAAAEQAIAADBEdC9AAAAAQAQAAnPtAAJyZMACEyrAACTJwACADVNYWNpbnRvc2ggSEQ6VXNlcnM6YWxleDpUaGVzZTpiaWJsaW9ncmFwaGllOnBpbjA2LnBkZgAADgAUAAkAcABpAG4AMAA2AC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgAoVXNlcnMvYWxleC9UaGVzZS9iaWJsaW9ncmFwaGllL3BpbjA2LnBkZgATAAEvAAAVAAIAC///AACABdIcHR4fWCRjbGFzc2VzWiRjbGFzc25hbWWjHyAhXU5TTXV0YWJsZURhdGFWTlNEYXRhWE5TT2JqZWN0XxAsLi4vLi4vLi4vLi4vLi4vVGhlc2UvYmlibGlvZ3JhcGhpZS9waW4wNi5wZGbSHB0kJaIlIVxOU0RpY3Rpb25hcnkSAAGGoF8QD05TS2V5ZWRBcmNoaXZlcgAIABEAFgAfACgAMgA1ADoAPABFAEsAUgBdAGUAbABvAHEAcwB2AHgAegB8AIYAkwCYAKACJAImAisCNAI/AkMCUQJYAmECkAKVApgCpQKqAAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAArw=},
Bdsk-Url-1 = {http://www.combinatorics.org/Volume_13/Abstracts/v13i1r69.html}}
```

[BibTeX] [Abstract]

A directed star forest is a forest all of whose components are stars with arcs emanating from the center to the leaves. The acircuitic directed star arboricity of an oriented graph $G$ (that is a digraph with no opposite arcs) is the minimum number of arc-disjoint directed star forests whose union covers all arcs of $G$ and such that the union of any two such forests is acircuitic. We show that every subcubic graph has acircuitic directed star arboricity at most four.

```
@article{ps06b,
Abstract = {A directed star forest is a forest all of whose components are stars with arcs emanating from the center to the leaves. The acircuitic directed star arboricity of an oriented graph $G$ (that is a digraph with no opposite arcs) is the minimum number of arc-disjoint directed star forests whose union covers all arcs of $G$ and such that the union of any two such forests is acircuitic. We show that every subcubic graph has acircuitic directed star arboricity at most four.},
Author = {Pinlou, A. and Sopena, {É}.},
Committee = {Yes},
Journal = {Discrete Mathematics},
Keywords = {acircuitic directed star arboricity, cubic graphs, star arboricity, arboricity},
Number = {24},
Pages = {3281--3289},
Pdf = {ps06b.pdf},
Title = {The acircuitic directed star arboricity of subcubic graphs is at most four},
Url = {http://dx.doi.org/10.1016/j.disc.2006.06.007},
Volume = {306},
Year = {2006},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.disc.2006.06.007}}
```

### International conferences and workshops with program committee

[BibTeX] [Abstract]

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 \frac23-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 $\frac83 łe M < 3$ and $d \ge \frac13-M$, if a graph has maximum average degree less than $M$ then it has an $(\cal I,\cal F_d)$-partition.

```
@inproceedings{dmp16c,
abstract = {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.},
Audience = {International},
author = {Dross, F. and Montassier, M. and Pinlou, A.},
Booktitle = {4th Bordeaux Graph Workshop},
Committee = {Yes},
Dateconf = {7-10 november 2016},
Lieuconf = {Bordeaux, France},
Pdf = {dmp16c.pdf},
Title = {Partitioning sparse graphs into an independent set and a forest of bounded degree},
URL = {http://bgw.labri.fr/2016/},
Year = {2016}}
```

[BibTeX]

```
@inproceedings{lmops16,
abstract = {},
Audience = {International},
author = {Lužar, B. and Mockovčiaková, M. and Ochem, P. and Pinlou, A. and Soták, R.},
Booktitle = {4th Bordeaux Graph Workshop},
Committee = {Yes},
Dateconf = {7-10 november 2016},
Lieuconf = {Bordeaux, France},
Pdf = {lmops16.pdf},
Title = {On a conjecture on k-Thue sequences},
URL = {http://bgw.labri.fr/2016/},
Year = {2016}}
```

[BibTeX] [Abstract]

We prove that any triange-free planar graph can have its set of vertices partitioned into two sets, one inducing a forest and the other a forest with maximum degree at most 5. We also show that if for some , there is a triangle-free planar graph that cannot be partitioned into two sets, one inducing a forest and the other a forest with maximum degree at most , then it is an NP-complete problem to decide if a triangle-free planar graph admits such a partition.

```
@inproceedings{dmp15b,
Abstract = {We prove that any triange-free planar graph can have its set of vertices partitioned into two sets, one inducing a forest and the other a forest with maximum degree at most 5. We also show that if for some , there is a triangle-free planar graph that cannot be partitioned into two sets, one inducing a forest and the other a forest with maximum degree at most , then it is an NP-complete problem to decide if a triangle-free planar graph admits such a partition.},
Audience = {International},
Author = {Dross, F. and Montassier, M. and Pinlou, A.},
Booktitle = {European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015},
Committee = {Yes},
Dateconf = {August 31 — September 4 2015},
Lieuconf = {Bergen, Norway},
Series = {Elect. Notes in Discrete Math.},
Title = {Partitioning a triangle-free planar graph into a forest and a forest of bounded degree},
Volume = {49},
Pages = {269-275},
Year = {2015},
Pdf = {dmp15b.pdf},
DOI = {10.1016/j.endm.2015.06.037},
}
```

[BibTeX] [Abstract]

We propose a general framework based on the entropy compression

method, inspired by the one of Esperet and Parreau, to

prove upper bounds for some chromatic numbers. From this method, in

particular, we derive that every graph with maximum degree

has an acyclic vertex-coloring using at most

colors, and a non-repetitive

vertex-coloring using at most colors.

```
@inproceedings{gmp14,
Abstract = {We propose a general framework based on the entropy compression
method, inspired by the one of Esperet and Parreau, to
prove upper bounds for some chromatic numbers. From this method, in
particular, we derive that every graph with maximum degree
has an acyclic vertex-coloring using at most
colors, and a non-repetitive
vertex-coloring using at most colors.},
Audience = {International},
Author = {Gonçalves, D. and Montassier, M. and Pinlou, A.},
Booktitle = {9th International colloquium on graph theory and combinatorics},
Committee = {Yes},
Dateconf = {30 june-04 july 2014},
Lieuconf = {Grenoble, France},
Pdf = {gmp14.pdf},
URL = {http://oc.inpg.fr/conf/icgt2014/},
Title = {Entropy compression method applied to graph colorings},
Year = {2014}}
```

[BibTeX] [Abstract]

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 are list 2-distance ()-colorable when

(Borodin and Ivanova (2009)) and 2-distance ()-colorable when (Borodin

and Ivanova (2009)). We prove here that suffices in both cases. More generally, we

show that graphs with maximum average degree less than 3 and are list 2-distance

()-colorable. The proof can be transposed to list injective ()-coloring.

```
@inproceedings{blp12b,
abstract = {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 are list 2-distance ()-colorable when
(Borodin and Ivanova (2009)) and 2-distance ()-colorable when (Borodin
and Ivanova (2009)). We prove here that suffices in both cases. More generally, we
show that graphs with maximum average degree less than 3 and are list 2-distance
()-colorable. The proof can be transposed to list injective ()-coloring.},
Audience = {International},
author = {Bonamy, M. and Lévêque, B. and Pinlou, A.},
Booktitle = {2nd Bordeaux Graph Workshop},
Committee = {Yes},
Dateconf = {21-24 november 2012},
Lieuconf = {Bordeaux, France},
Pdf = {blp12b.pdf},
Title = {Graphs with mad<3 and Delta>=17 are list 2-distance (Delta+2)-colorable},
URL = {http://bgw.labri.fr/2012/},
Year = {2012}}
```

[BibTeX] [Abstract]

A contact representation by triangles of a graph is a set of triangles in the plane such that two triangles intersect on at most one point, each triangle represents a vertex of the graph and two triangles intersects if and only if their corresponding vertices are adjacent. de Fraysseix, Ossona de Mendez and Rosenstiehl proved that every planar graph admits a contact representation by triangles. We strengthen this in terms of a simultaneous contact representation by triangles of a planar map and of its dual. A primal-dual contact representation by triangles of a planar map is a contact representation by triangles of the primal and a contact representation by triangles of the dual such that for every edge uv, bordering faces f and g, the intersection between the triangles corresponding to u and v is the same point as the intersection between the triangles corresponding to f and g. We prove that every 3-connected planar map admits a primal-dual contact representation by triangles. Moreover, the interiors of the triangles form a tiling of the triangle corresponding to the outer face and each contact point is a node of exactly three triangles. Then we show that these representations are in one-to-one correspondence with generalized Schnyder woods defined by Felsner for 3-connected planar maps.

```
@inproceedings{glp11,
Abstract = {A contact representation by triangles of a graph is a set of triangles in the plane such that two triangles intersect on at most one point, each triangle represents a vertex of the graph and two triangles intersects if and only if their corresponding vertices are adjacent. de Fraysseix, Ossona de Mendez and Rosenstiehl proved that every planar graph admits a contact representation by triangles. We strengthen this in terms of a simultaneous contact representation by triangles of a planar map and of its dual. A primal-dual contact representation by triangles of a planar map is a contact representation by triangles of the primal and a contact representation by triangles of the dual such that for every edge uv, bordering faces f and g, the intersection between the triangles corresponding to u and v is the same point as the intersection between the triangles corresponding to f and g. We prove that every 3-connected planar map admits a primal-dual contact representation by triangles. Moreover, the interiors of the triangles form a tiling of the triangle corresponding to the outer face and each contact point is a node of exactly three triangles. Then we show that these representations are in one-to-one correspondence with generalized Schnyder woods defined by Felsner for 3-connected planar maps.},
Address = {Berlin, Heidelberg},
Author = {Goncalves, Daniel and L{\'e}v{\^e}que, Benjamin and Pinlou, Alexandre},
Booktitle = {Proceedings of the 18th international conference on Graph drawing},
Committee = {Yes},
Dateconf = {September 21-24, 2010},
Isbn = {978-3-642-18468-0},
Lieuconf = {Konstanz, Germany},
Pages = {262--273},
Pdf = {glp11.pdf},
Publisher = {Springer-Verlag},
Series = {{GD'10}},
Title = {Triangle contact representations and duality},
Url = {http://www.springerlink.com/content/978-3-642-18468-0},
Urldate = {2013-01-04},
Year = {2011},
Bdsk-Url-1 = {http://www.springerlink.com/content/978-3-642-18468-0}}
```

[BibTeX] [Abstract]

A 2-distance coloring of a graph is a coloring of the vertices in such a way that two vertices at distance at most 2 receive distinct colors. We prove that every graph with maximum degree Delta at least 4 and maximum average degree less that 7/3 admits a 2-distance (Delta+1)-coloring. This result is tight. This improves previous known results of Dolama et al.

```
@inproceedings{blp11,
Abstract = {A 2-distance coloring of a graph is a coloring of the vertices in such a way that two vertices at distance at most 2 receive distinct colors. We prove that every graph with maximum degree Delta at least 4 and maximum average degree less that 7/3 admits a 2-distance (Delta+1)-coloring. This result is tight. This improves previous known results of Dolama et al.},
Audience = {International},
Author = {Bonamy, M. and Lév{\^e}que, B. and Pinlou, A.},
Booktitle = {European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2011},
Committee = {Yes},
Dateconf = {29 september - 02 october 2011},
Lieuconf = {Budapest, Hongrie},
Series = {Elect. Notes in Discrete Math.},
Title = {2-distance coloring of sparse graphs},
Volume = {to appear},
Year = {2011}}
```

[BibTeX] [Abstract]

A graph is planar if it can be embedded on the plane without edge-crossing. A graph is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the external face is outerplanar (i.e. with all its vertices on the external face). An oriented k-coloring of an oriented graph G is a homomorphism from G to an oriented graph H of order k. We prove that every oriented triangle-free planar graph has an oriented chromatic number at most 40, that improves the previous known bound of 47 due to Borodin and Ivanova [Borodin, O. V. and Ivanova, A. O., An oriented colouring of planar graphs with girth at least 4, Sib. Electron. Math. Reports, vol. 2, 239-249, 2005]. We also prove that every oriented 2-outerplanar graph has an oriented chromatic number at most 40, that improves the previous known bound of 67 due to Esperet and Ochem [Esperet, L. and Ochem, P. Oriented colouring of 2-outerplanar graphs, Inform. Process. Lett., vol. 101(5), 215-219, 2005].

```
@inproceedings{op11,
Abstract = {{A} graph is planar if it can be embedded on the plane without edge-crossing. {A} graph is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the external face is outerplanar (i.e. with all its vertices on the external face). {A}n oriented k-coloring of an oriented graph {G} is a homomorphism from {G} to an oriented graph {H} of order k. {W}e prove that every oriented triangle-free planar graph has an oriented chromatic number at most 40, that improves the previous known bound of 47 due to {B}orodin and {I}vanova [{B}orodin, {O}. {V}. and {I}vanova, {A}. {O}., {A}n oriented colouring of planar graphs with girth at least 4, {S}ib. {E}lectron. {M}ath. {R}eports, vol. 2, 239-249, 2005]. {W}e also prove that every oriented 2-outerplanar graph has an oriented chromatic number at most 40, that improves the previous known bound of 67 due to {E}speret and {O}chem [{E}speret, {L}. and {O}chem, {P}. {O}riented colouring of 2-outerplanar graphs, {I}nform. {P}rocess. {L}ett., vol. 101(5), 215-219, 2005].},
Author = {Ochem, P. and Pinlou, A.},
Booktitle = {VI Latin-American Algorithms, Graphs and Optimization Symposium},
Committee = {Yes},
Dateconf = {28 march - 01 april 2011},
Keywords = {{O}riented coloring; {P}lanar graph; {G}irth; 2-outerplanar graph; {D}ischarging procedure.},
Lieuconf = {Bariloche, Argentina},
Pages = {123--128},
Pdf = {op11.pdf},
Series = {Elect. Notes in Discrete Math.},
Title = {{O}riented {C}oloring of {T}riangle-{F}ree {P}lanar {G}raphs and 2-{O}uterplanar {G}raphs},
Url = {http://dx.doi.org/10.1016/j.endm.2011.05.022},
Volume = {37},
Year = {2011},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.endm.2011.05.022}}
```

[BibTeX] [Abstract]

A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph $G$ is defined as the smallest order of a colored mixed graph $H$ such that there exists a (arc-color preserving) homomorphism from $G$ to $H$. We study in this paper the colored mixed chromatic number of planar graphs, partial 2-trees and outerplanar graphs with given girth.

```
@inproceedings{mprs09,
Abstract = {A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph $G$ is defined as the smallest order of a colored mixed graph $H$ such that there exists a (arc-color preserving) homomorphism from $G$ to $H$. We study in this paper the colored mixed chromatic number of planar graphs, partial 2-trees and outerplanar graphs with given girth.},
Audience = {International},
Author = {Montejano, A. and Pinlou, A. and Raspaud, A. and Sopena, {É}.},
Booktitle = {European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2009},
Committee = {Yes},
Dateconf = {7-11 september 2009},
Doi = {10.1016/j.endm.2009.07.060},
Lieuconf = {Bordeaux, France},
Pages = {363-367},
Series = {Elect. Notes in Discrete Math.},
Title = {Chromatic number of sparse colored mixed planar graphs},
Url = {http://dx.doi.org/10.1016/j.endm.2009.07.060},
Volume = {34},
Year = {2009},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RFFpOUy5vYmplY3RzV05TLmtleXNWJGNsYXNzog8QgASABqISE4ACgAOAB1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgNGRpXTlMuZGF0YU8RAYQAAAAAAYQAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMkCXXlIKwAAAAnPtAptcHJzMDkucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACdAQxteeqlBERiBDQVJPAAUAAwAACSAAAAAAAAAAAAAAAAAAAAANYmlibGlvZ3JhcGhpZQAAEAAIAADJAk9pAAAAEQAIAADG14KKAAAAAQAQAAnPtAAJyZMACEyrAACTJwACADZNYWNpbnRvc2ggSEQ6VXNlcnM6YWxleDpUaGVzZTpiaWJsaW9ncmFwaGllOm1wcnMwOS5wZGYADgAWAAoAbQBwAHIAcwAwADkALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASAClVc2Vycy9hbGV4L1RoZXNlL2JpYmxpb2dyYXBoaWUvbXByczA5LnBkZgAAEwABLwAAFQACAAv//wAAgAXSHB0eH1gkY2xhc3Nlc1okY2xhc3NuYW1lox8gIV1OU011dGFibGVEYXRhVk5TRGF0YVhOU09iamVjdF8QLS4uLy4uLy4uLy4uLy4uL1RoZXNlL2JpYmxpb2dyYXBoaWUvbXByczA5LnBkZtIcHSQloiUhXE5TRGljdGlvbmFyeRIAAYagXxAPTlNLZXllZEFyY2hpdmVyAAgAEQAWAB8AKAAyADUAOgA8AEUASwBSAF0AZQBsAG8AcQBzAHYAeAB6AHwAhgCTAJgAoAIoAioCLwI4AkMCRwJVAlwCZQKVApoCnQKqAq8AAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAACwQ==}}
```

[BibTeX] [Abstract]

A star is an arborescence in which the root dominates all the other vertices. A galaxy is a evertex-disjoint union of stars. The directed star arboricity of a digraph $D$, denoted by $dst(D)$, is the minimum number of galaxies needed to cover $A(D)$. In this paper, we show that $dst(D)łeq \Delta(D)+1$ and that if $D$ is acyclic then $dst(D)łeq \Delta(D)$. These results are proved by considering the existence of spanning galaxies in digraphs. Thus, we study the problem of deciding whether a digraph $D$ has a spanning galaxy or not. We show that it is NP-complete (even when restricted to acyclic digraphs) but that it becomes polynomial-time solvable when restricted to strongly connected digraphs.

```
@inproceedings{ghpt09,
Abstract = {A star is an arborescence in which the root dominates all the other vertices. A galaxy is a evertex-disjoint union of stars. The directed star arboricity of a digraph $D$, denoted by $dst(D)$, is the minimum number of galaxies needed to cover $A(D)$. In this paper, we show that $dst(D)\leq \Delta(D)+1$ and that if $D$ is acyclic then $dst(D)\leq \Delta(D)$. These results are proved by considering the existence of spanning galaxies in digraphs. Thus, we study the problem of deciding whether a digraph $D$ has a spanning galaxy or not. We show that it is NP-complete (even when restricted to acyclic digraphs) but that it becomes polynomial-time solvable when restricted to strongly connected digraphs.},
Audience = {International},
Author = {Goncalves, D. and Havet, F. and Pinlou, A. and Thomass{É}, S.},
Booktitle = {European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2009},
Committee = {Yes},
Dateconf = {7-11 september 2009},
Doi = {10.1016/j.endm.2009.07.023},
Lieuconf = {Bordeaux, France},
Pages = {134-137},
Series = {Elect. Notes in Discrete Math.},
Title = {Spanning galaxies in digraphs},
Url = {http://dx.doi.org/10.1016/j.endm.2009.07.023},
Volume = {34},
Year = {2009},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RFFpOUy5vYmplY3RzV05TLmtleXNWJGNsYXNzog8QgASABqISE4ACgAOAB1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgNGRpXTlMuZGF0YU8RAYQAAAAAAYQAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMkCXXlIKwAAAAnPtApnaHB0MDkucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACc/sxteexVBERiBDQVJPAAUAAwAACSAAAAAAAAAAAAAAAAAAAAANYmlibGlvZ3JhcGhpZQAAEAAIAADJAk9pAAAAEQAIAADG14KlAAAAAQAQAAnPtAAJyZMACEyrAACTJwACADZNYWNpbnRvc2ggSEQ6VXNlcnM6YWxleDpUaGVzZTpiaWJsaW9ncmFwaGllOmdocHQwOS5wZGYADgAWAAoAZwBoAHAAdAAwADkALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASAClVc2Vycy9hbGV4L1RoZXNlL2JpYmxpb2dyYXBoaWUvZ2hwdDA5LnBkZgAAEwABLwAAFQACAAv//wAAgAXSHB0eH1gkY2xhc3Nlc1okY2xhc3NuYW1lox8gIV1OU011dGFibGVEYXRhVk5TRGF0YVhOU09iamVjdF8QLS4uLy4uLy4uLy4uLy4uL1RoZXNlL2JpYmxpb2dyYXBoaWUvZ2hwdDA5LnBkZtIcHSQloiUhXE5TRGljdGlvbmFyeRIAAYagXxAPTlNLZXllZEFyY2hpdmVyAAgAEQAWAB8AKAAyADUAOgA8AEUASwBSAF0AZQBsAG8AcQBzAHYAeAB6AHwAhgCTAJgAoAIoAioCLwI4AkMCRwJVAlwCZQKVApoCnQKqAq8AAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAACwQ==},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.endm.2009.07.023}}
```

[BibTeX] [Abstract]

In this paper, we study homomorphisms of 2-edge-colored graphs, that is graphs with edges colored with two colors. We consider various graph classes (outerplanar graphs, partial 2-trees, partial 3-trees, planar graphs) and the problem is to find, for each class, the smallest number of vertices of a 2-edge-colored graph $H$ such that each graph of the considered class admits a homomorphism to $H$.

```
@inproceedings{moprs08,
Abstract = {In this paper, we study homomorphisms of 2-edge-colored graphs, that is graphs with edges colored with two colors. We consider various graph classes (outerplanar graphs, partial 2-trees, partial 3-trees, planar graphs) and the problem is to find, for each class, the smallest number of vertices of a 2-edge-colored graph $H$ such that each graph of the considered class admits a homomorphism to $H$.},
Author = {Montejano, A. and Ochem, P. and Pinlou, A. and Raspaud, A. and Sopena, {É}.},
Booktitle = {IV Latin-American Algorithms, Graphs and Optimization Symposium},
Committee = {Yes},
Dateconf = {25-29 november 2007},
Lieuconf = {Puerto Varas, Chili},
Pages = {33--38},
Series = {Elect. Notes in Discrete Math.},
Title = {Homomorphisms of 2-edge-colored graphs},
Url = {http://dx.doi.org/10.1016/j.endm.2008.01.007},
Volume = {30},
Year = {2008},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RFFpOUy5vYmplY3RzV05TLmtleXNWJGNsYXNzog8QgASABqISE4ACgAOAB1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgNGRpXTlMuZGF0YU8RAYgAAAAAAYgAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMkCXXlIKwAAAAnPtAttb3ByczA4LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACdANw+JYSlBERiBDQVJPAAUAAwAACSAAAAAAAAAAAAAAAAAAAAANYmlibGlvZ3JhcGhpZQAAEAAIAADJAk9pAAAAEQAIAADD4ko6AAAAAQAQAAnPtAAJyZMACEyrAACTJwACADdNYWNpbnRvc2ggSEQ6VXNlcnM6YWxleDpUaGVzZTpiaWJsaW9ncmFwaGllOm1vcHJzMDgucGRmAAAOABgACwBtAG8AcAByAHMAMAA4AC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgAqVXNlcnMvYWxleC9UaGVzZS9iaWJsaW9ncmFwaGllL21vcHJzMDgucGRmABMAAS8AABUAAgAL//8AAIAF0hwdHh9YJGNsYXNzZXNaJGNsYXNzbmFtZaMfICFdTlNNdXRhYmxlRGF0YVZOU0RhdGFYTlNPYmplY3RfEC4uLi8uLi8uLi8uLi8uLi9UaGVzZS9iaWJsaW9ncmFwaGllL21vcHJzMDgucGRm0hwdJCWiJSFcTlNEaWN0aW9uYXJ5EgABhqBfEA9OU0tleWVkQXJjaGl2ZXIACAARABYAHwAoADIANQA6ADwARQBLAFIAXQBlAGwAbwBxAHMAdgB4AHoAfACGAJMAmACgAiwCLgIzAjwCRwJLAlkCYAJpApoCnwKiAq8CtAAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAALG},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.endm.2008.01.007}}
```

[BibTeX] [Abstract]

A strong oriented $k$-coloring of an oriented graph G is a homomorphism $\phi$ from $G$ to $H$ having $k$ vertices labelled by the $k$ elements of an abelian additive group $M$, such that for any pairs of arcs $øverrightarrowuv$ and $øverrightarrowzt$ of $G$, we have $\phi(v) - \phi(u) \neq - (\phi(t) - \phi(z))$.

The strong oriented chromatic number $\chi_s(G)$ is the smallest $k$ such that $G$ admits a strong oriented $k$-coloring. In this paper, we consider the following problem: Let $i\ge $4 be an integer. Let $G$ be an oriented planar graph without cycles of lengths 4 to $i$. What is the strong oriented chromatic number of $G$?

```
@inproceedings{mop08b,
Abstract = {A strong oriented $k$-coloring of an oriented graph G is a homomorphism $\phi$ from $G$ to $H$ having $k$ vertices labelled by the $k$ elements of an abelian additive group $M$, such that for any pairs of arcs $\overrightarrow{uv}$ and $\overrightarrow{zt}$ of $G$, we have $\phi(v) - \phi(u) \neq - (\phi(t) - \phi(z))$.
The strong oriented chromatic number $\chi_s(G)$ is the smallest $k$ such that $G$ admits a strong oriented $k$-coloring. In this paper, we consider the following problem: Let $i\ge $4 be an integer. Let $G$ be an oriented planar graph without cycles of lengths 4 to $i$. What is the strong oriented chromatic number of $G$?},
Author = {Montassier, M. and Ochem, P. and Pinlou, A.},
Booktitle = {IV Latin-American Algorithms, Graphs and Optimization Symposium},
Committee = {Yes},
Dateconf = {25-29 november 2007},
Lieuconf = {Puerto Varas, Chili},
Pages = {27--32},
Pdf = {mop08b},
Series = {Elect. Notes in Discrete Math.},
Title = {Strong oriented chromatic number of planar graphs without cycles of specifics lengths},
Url = {http://dx.doi.org/10.1016/j.endm.2008.01.006},
Volume = {30},
Year = {2008},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RFFpOUy5vYmplY3RzV05TLmtleXNWJGNsYXNzog8QgASABqISE4ACgAOAB1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgNGRpXTlMuZGF0YU8RAYQAAAAAAYQAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMkCXXlIKwAAAAnPtAptb3AwOGIucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACdAMw+JYN1BERiBDQVJPAAUAAwAACSAAAAAAAAAAAAAAAAAAAAANYmlibGlvZ3JhcGhpZQAAEAAIAADJAk9pAAAAEQAIAADD4konAAAAAQAQAAnPtAAJyZMACEyrAACTJwACADZNYWNpbnRvc2ggSEQ6VXNlcnM6YWxleDpUaGVzZTpiaWJsaW9ncmFwaGllOm1vcDA4Yi5wZGYADgAWAAoAbQBvAHAAMAA4AGIALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASAClVc2Vycy9hbGV4L1RoZXNlL2JpYmxpb2dyYXBoaWUvbW9wMDhiLnBkZgAAEwABLwAAFQACAAv//wAAgAXSHB0eH1gkY2xhc3Nlc1okY2xhc3NuYW1lox8gIV1OU011dGFibGVEYXRhVk5TRGF0YVhOU09iamVjdF8QLS4uLy4uLy4uLy4uLy4uL1RoZXNlL2JpYmxpb2dyYXBoaWUvbW9wMDhiLnBkZtIcHSQloiUhXE5TRGljdGlvbmFyeRIAAYagXxAPTlNLZXllZEFyY2hpdmVyAAgAEQAWAB8AKAAyADUAOgA8AEUASwBSAF0AZQBsAG8AcQBzAHYAeAB6AHwAhgCTAJgAoAIoAioCLwI4AkMCRwJVAlwCZQKVApoCnQKqAq8AAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAACwQ==},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.endm.2008.01.006}}
```

[BibTeX] [Abstract]

We consider improper colorings (sometimes called generalized, defective or relaxed colorings) in which every color class has a bounded degree. We propose a natural extension of improper colorings: acyclic improper choosability. We prove that subcubic graphs are acyclically $(3,1)^*$-choosable (i.e. they are acyclically $3$-choosable with color classes of maximum degree one). Using a linear time algorithm, we also prove that outerplanar graphs are acyclically $(2,5)^*$-choosable (i.e. they are acyclically $2$-choosable with color classes of maximum degree five). Both results are optimal. We finally prove that acyclic choosability and acyclic improper choosability of planar graphs are equivalent notions.

```
@inproceedings{ep07,
Abstract = {We consider improper colorings (sometimes called generalized, defective or relaxed colorings) in which every color class has a bounded degree. We propose a natural extension of improper colorings: acyclic improper choosability. We prove that subcubic graphs are acyclically $(3,1)^{*}$-choosable (i.e. they are acyclically $3$-choosable with color classes of maximum degree one). Using a linear time algorithm, we also prove that outerplanar graphs are acyclically $(2,5)^{*}$-choosable (i.e. they are acyclically $2$-choosable with color classes of maximum degree five). Both results are optimal. We finally prove that acyclic choosability and acyclic improper choosability of planar graphs are equivalent notions.},
Audience = {International},
Author = {Esperet, L. and Pinlou, A.},
Booktitle = {Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications},
Committee = {Yes},
Dateconf = {10-15 juillet 2006},
Lieuconf = {Prague, Czech Republic},
Pages = {251--258},
Pdf = {ep07.pdf},
Series = {Elect. Notes in Discrete Math.},
Title = {Acyclic improper choosability of graphs},
Url = {http://dx.doi.org/10.1016/j.endm.2007.01.037},
Volume = {28},
Year = {2007},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RFFpOUy5vYmplY3RzV05TLmtleXNWJGNsYXNzog8QgASABqISE4ACgAOAB1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgNGRpXTlMuZGF0YU8RAYAAAAAAAYAAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMkCXXlIKwAAAAnPtAllcDA2Yi5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACc/kw9cg/FBERiBDQVJPAAUAAwAACSAAAAAAAAAAAAAAAAAAAAANYmlibGlvZ3JhcGhpZQAAEAAIAADJAk9pAAAAEQAIAADD1xLsAAAAAQAQAAnPtAAJyZMACEyrAACTJwACADVNYWNpbnRvc2ggSEQ6VXNlcnM6YWxleDpUaGVzZTpiaWJsaW9ncmFwaGllOmVwMDZiLnBkZgAADgAUAAkAZQBwADAANgBiAC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgAoVXNlcnMvYWxleC9UaGVzZS9iaWJsaW9ncmFwaGllL2VwMDZiLnBkZgATAAEvAAAVAAIAC///AACABdIcHR4fWCRjbGFzc2VzWiRjbGFzc25hbWWjHyAhXU5TTXV0YWJsZURhdGFWTlNEYXRhWE5TT2JqZWN0XxAsLi4vLi4vLi4vLi4vLi4vVGhlc2UvYmlibGlvZ3JhcGhpZS9lcDA2Yi5wZGbSHB0kJaIlIVxOU0RpY3Rpb25hcnkSAAGGoF8QD05TS2V5ZWRBcmNoaXZlcgAIABEAFgAfACgAMgA1ADoAPABFAEsAUgBdAGUAbABvAHEAcwB2AHgAegB8AIYAkwCYAKACJAImAisCNAI/AkMCUQJYAmECkAKVApgCpQKqAAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAArw=},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.endm.2007.01.037}}
```

[BibTeX]

```
@inproceedings{op07,
Author = {Ochem, P. and Pinlou, A.},
Booktitle = {European Conference on Combinatorics, Graph Theory and Applications (EuroComb '07)},
Committee = {Yes},
Dateconf = {11-15 september 2007},
Lieuconf = {S{É}villa, Spain},
Pages = {195--199},
Series = {Elect. Notes in Discrete Math.},
Title = {Oriented vertex and arc colorings of partial 2-trees},
Url = {http://dx.doi.org/10.1016/j.endm.2007.07.034},
Volume = {29},
Year = {2007},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RFFpOUy5vYmplY3RzV05TLmtleXNWJGNsYXNzog8QgASABqISE4ACgAOAB1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgNGRpXTlMuZGF0YU8RAXwAAAAAAXwAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMkCXXlIKwAAAAnPtAhvcDA3LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACdAew6gjF1BERiBDQVJPAAUAAwAACSAAAAAAAAAAAAAAAAAAAAANYmlibGlvZ3JhcGhpZQAAEAAIAADJAk9pAAAAEQAIAADDqBUHAAAAAQAQAAnPtAAJyZMACEyrAACTJwACADRNYWNpbnRvc2ggSEQ6VXNlcnM6YWxleDpUaGVzZTpiaWJsaW9ncmFwaGllOm9wMDcucGRmAA4AEgAIAG8AcAAwADcALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASACdVc2Vycy9hbGV4L1RoZXNlL2JpYmxpb2dyYXBoaWUvb3AwNy5wZGYAABMAAS8AABUAAgAL//8AAIAF0hwdHh9YJGNsYXNzZXNaJGNsYXNzbmFtZaMfICFdTlNNdXRhYmxlRGF0YVZOU0RhdGFYTlNPYmplY3RfECsuLi8uLi8uLi8uLi8uLi9UaGVzZS9iaWJsaW9ncmFwaGllL29wMDcucGRm0hwdJCWiJSFcTlNEaWN0aW9uYXJ5EgABhqBfEA9OU0tleWVkQXJjaGl2ZXIACAARABYAHwAoADIANQA6ADwARQBLAFIAXQBlAGwAbwBxAHMAdgB4AHoAfACGAJMAmACgAiACIgInAjACOwI/Ak0CVAJdAosCkAKTAqACpQAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAAK3},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.endm.2007.07.034}}
```

### Submitted articles

[BibTeX] [Abstract]

The \emphrepetition threshold is the smallest real

number $\alpha$ such that there exists an infinite word over a

$k$-letter alphabet that avoids repetition of exponent strictly

greater than $\alpha$. This notion can be generalized to graph

classes. In this paper, we completely determine the repetition

thresholds for caterpillars and caterpillars of maximum degree

$3$. Additionally, we present bounds for the repetition thresholds

of trees with bounded maximum degrees.

```
@techreport{lop17,
title = {On repetition thresholds of caterpillars and trees of bounded degree},
abstract = {The \emph{repetition threshold} is the smallest real
number $\alpha$ such that there exists an infinite word over a
$k$-letter alphabet that avoids repetition of exponent strictly
greater than $\alpha$. This notion can be generalized to graph
classes. In this paper, we completely determine the repetition
thresholds for caterpillars and caterpillars of maximum degree
$3$. Additionally, we present bounds for the repetition thresholds
of trees with bounded maximum degrees.},
author = {Lužar, B. and Ochem, P. and Pinlou, A.},
year = {2017},
Arxiv = {1702.01058},
Note = {Submitted},
Type = {Research Report},
Pdf = {lop17.pdf},
}
```

[BibTeX] [Abstract]

We prove that every triangle-free planar graph of order $n$ and size $m$ has an induced linear forest with at least $\frac9n - 2m11$ vertices, and thus at least $\frac5n + 811$ vertices. Furthermore, we show that there are triangle-free planar graphs on $n$ vertices whose largest induced linear forest has order $łceil \fracn2 \rceil + 1$.

```
@techreport{dmp17b,
title = {A lower bound on the order of the largest induced linear forest in triangle-free planar graphs},
abstract = { We prove that every triangle-free planar graph of order $n$ and size $m$ has an induced linear forest with at least $\frac{9n - 2m}{11}$ vertices, and thus at least $\frac{5n + 8}{11}$ vertices. Furthermore, we show that there are triangle-free planar graphs on $n$ vertices whose largest induced linear forest has order $\lceil \frac{n}{2} \rceil + 1$.},
author = {Dross, F. and Montassier, M. and Pinlou, A.},
year = {2017},
Note = {Submitted},
Type = {Research Report},
Pdf = {dmp17b.pdf},
}
```

[BibTeX] [Abstract]

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 \frac23-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 $\frac83 łe M < 3$ and $d \ge \frac13-M$, if a graph has maximum average degree less than $M$ then it has an $(\cal I,\cal F_d)$-partition.

```
@techreport{dmp16b,
title = {Partitioning sparse graphs into an independent set and a forest of bounded degree},
abstract = {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.},
journal = {arXiv:1606.04394 [cs.DM]},
author = {Dross, F. and Montassier, M. and Pinlou, A.},
year = {2016},
Arxiv = {1606.04394},
Note = {Submitted},
Type = {Research Report},
Pdf = {dmp16b.pdf},
}
```

[BibTeX] [Abstract]

Based on the algorithmic proof of Lovász local lemma due to Moser and Tardos, 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 \emphentropy 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 , and a non-repetitive chromatic number at most . Also every planar graph with maximum degree has a facial Thue choice number at most and facial Thue chromatic index at most .

```
@techreport{gmp14b,
Abstract = {Based on the algorithmic proof of Lov\'asz local lemma due to Moser and Tardos, 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 , and a non-repetitive chromatic number at most . Also every planar graph with maximum degree has a facial Thue choice number at most and facial Thue chromatic index at most . },
Arxiv = {1406.4380},
Author = {Gonçalves, D. and Montassier, M. and Pinlou, A.},
Note = {Submitted},
Pdf = {gmp14b.pdf},
Title = {Entropy compression method applied to graph colorings},
Type = {Research Report},
Year = {2014}}
```

[BibTeX] [Abstract]

We give here some new lower bounds on the order of a largest induced forest in planar graphs with girth and . In particular we prove that a triangle-free planar graph of order admits an induced forest of order at least , 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 and girth at least admits an induced forest of order at least .

```
@techreport{dmp14,
Abstract = {We give here some new lower bounds on the order of a largest induced forest in planar graphs with girth and . In particular we prove that a triangle-free planar graph of order admits an induced forest of order at least , 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 and girth at least admits an induced forest of order at least .},
Arxiv = {1409.1348},
Author = {Dross, F. and Montassier, M. and Pinlou, A.},
Note = {Submitted},
Pdf = {dmp14.pdf},
Title = {Large induced forests in planar graphs with girth 4 or 5},
Type = {Research Report},
Year = {2014}}
```

### Thesis

[BibTeX]

```
@habilitationthesis{pin14,
Author = {Pinlou, Alexandre},
Keywords = {graph homomorphism, entropy compression method, square coloring},
Institution = {Université Montpellier 2},
Title = {Some Problems in Graph Coloring: Methods, Extensions, and Results},
Year = {2014},
}
```

[BibTeX]

```
@phdthesis{pin06b,
Author = {Pinlou, Alexandre},
Date-Modified = {2013-04-22 12:02:09 +0200},
Keywords = {oriented chromatic number; oriented chromatic index; planar graph; outerplanar graph; partial 2-tree; acircuitic directed star arboricity; directed star arboricity},
Pdf = {pin06b.pdf},
Institution = {Université Bordeaux 1},
Title = {Arc-coloration et sommet-coloration orientées},
Year = {2006},
}
```

[BibTeX]

```
@mastersthesis{pin03,
Author = {Pinlou, A.},
Keywords = {oriented coloring, oriented graphs, oriented chromatic index},
Month = {Jun},
Institution = {Université Bordeaux 1},
Title = {Arc-coloration orientée de graphes orientés},
Year = {2003},
Pdf = {Pin03},
}
```