spe proceedings cdspe是什么抗生素意思
点击联系发帖人
时间：2014-11-11 03:16
SPE外文翻译_图文_百度文库
赠送免券下载特权
10W篇文档免费专享
部分付费文档8折起
每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
SPE外文翻译
阅读已结束，下载本文需要
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，同时保存到云知识，更方便管理
加入VIP
还剩9页未读，
定制HR最喜欢的简历
你可能喜欢Alexandre Pinlou - Home Page – Publications
Publications
International journals with program committee
B. Lu?ar, P. Ochem, and A. Pinlou. “On repetition thresholds of caterpillars and trees of bounded degree”, Electronic Journal of Combinatorics, vol. 25(1), pp. 1-10, 2018.
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.
@article{lop18,
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.},
journal = {Electronic Journal of Combinatorics},
year = {2018},
Pdf = {lop18.pdf},
URL = {http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p61/pdf},
pages = {1--10},
volume = {25},
number = {1}
F. Dross, M. Montassier, and A. Pinlou. “Partitioning sparse graphs into an independent set and a forest of bounded degree”, Electronic Journal of Combinatorics, vol. 25(1), pp. 1-13, 2018.
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.
@article{dmp18,
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 = {Electronic Journal of Combinatorics},
author = {Dross, F. and Montassier, M. and Pinlou, A.},
year = {2018},
Pdf = {dmp18.pdf},
URL = {http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p45},
pages = {1--13},
volume = {25},
number = {1}
F. Dross, M. Montassier, and A. Pinlou. "Partitioning a triangle-free planar graph into a forest and a forest of bounded degree", European Journal of Combinatorics, vol. 66, pp. 81-94, 2017.
An -partition of a graph is a vertex-partition into two sets
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
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 = {},
committee = {Yes},
journal = {European Journal of Combinatorics},
volume = {66},
pages = {81-94},
Pdf = {dmp17.pdf},
DOI = {10.1016/j.ejc.}
P. Ochem, A. Pinlou, and S. Sen. "Homomorphisms of 2-edge-colored triangle-free planar graphs", Journal of Graph Theory, vol. 85(1), pp. 258-277, 2017.
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 = {},
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%8},
Year = {2017},
DOI = {10.1002/jgt.22059},
M. Bonamy, M. Knor, B. Lu?ar, A. Pinlou, and R. ?krekovski. "On the difference between the Szeged and Wiener index", Applied Mathematics and Computation, vol. 312, pp. 202-213, 2017.
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
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
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 = {},
Pdf = {bklps17.pdf},
DOI = {10.1016/j.amc.},
URL = {http://www.sciencedirect.com/science/article/pii/S348X}
F. Dross, M. Montassier, and A. Pinlou. "A lower bound on the order of the largest induced forest in planar graphs with high girth", Discrete Applied Mathematics, vol. 214, pp. 99-107, 2016.
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
has a feedback vertex set of size at most , improving the trivial bound of . We also prove that every -connected graph with maximum degree
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
has a feedback vertex set of size at most , improving the trivial bound of . We also prove that every -connected graph with maximum degree
has a feedback vertex set of size at most .},
author = {Dross, F. and Montassier, M. and Pinlou, A.},
year = {2016},
%% Arxiv = {},
Committee = {Yes},
Journal = {Discrete Applied Mathematics},
Volume = {214},
Pages = {99-107},
DOI = {10.1016/j.dam.},
Pdf = {dmp16d.pdf},
M. Bonamy, B. Lévêque, and A. Pinlou. "Planar graphs with
and no triangle adjacent to a
are minimally edge- and total-choosable", Discrete Mathematics and Theoretical Computer Science, vol. 17(3), 2016.
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
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
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
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
and no triangle adjacent to a
are minimally
edge and total choosable.},
%% Arxiv = {},
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},
M. Bonamy, B. Lévêque, and A. Pinlou. "Graphs with maximum degree
and maximum average degree less than 3 are list 2-distance ()-colorable", Discrete Mathematics, vol. 317, pp. 19-32, 2014.
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.},
Title = {Graphs with maximum degree
and maximum average degree less than 3 are list 2-distance ()-colorable},
Year = {2014}}
M. Bonamy, B. Lévêque, and A. Pinlou. "2-distance coloring of sparse graphs", Journal of Graph Theory, vol. 77(3), pp. 190-218, 2014.
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
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
(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
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
remains open. We prove also that any graph with maximum average degree <img src='http://l.wordpress.com/latex.php?latex=m%20%3C%204&bg=EEEEEE&fg=8;s=0' title='m < 4' style='vertical-align:1%' class='tex' alt='m
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
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
(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
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
remains open. We prove also that any graph with maximum average degree <img src='http://l.wordpress.com/latex.php?latex=m%20%3C%204&bg=EEEEEE&fg=8;s=0' title='m < 4' style='vertical-align:1%' class='tex' alt='m
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}}
P. Ochem and A. Pinlou. "Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs", Graphs and Combinatorics, vol. 30(2), pp. 439-453, 2014.
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.-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}}
M. Bonamy, B. Lévêque, and A. Pinlou. "List coloring the square of sparse graphs with large degree", European Journal of Combinatorics, vol. 41, pp. 128-137, 2014.
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 <img src='http://l.wordpress.com/latex.php?latex=%5Cfrac145%20%3C%203&bg=EEEEEE&fg=8;s=0' title='\frac145 < 3' style='vertical-align:1%' class='tex' alt='\frac145 .
We strengthen their result and prove that there exists a function f such that the square of
any graph with maximum average degreem <img src='http://l.wordpress.com/latex.php?latex=m%3C%203&bg=EEEEEE&fg=8;s=0' title='m< 3' style='vertical-align:1%' class='tex' alt='m and maximum degree
f(m)' style='vertical-align:1%' class='tex' alt='\Delta > f(m)' /> 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.
@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 <img src='http://l.wordpress.com/latex.php?latex=%5Cfrac%7B14%7D%7B5%7D%20%3C%203&bg=EEEEEE&fg=8;s=0' title='\frac{14}{5} < 3' style='vertical-align:1%' class='tex' alt='\frac{14}{5} .
We strengthen their result and prove that there exists a function f such that the square of
any graph with maximum average degreem <img src='http://l.wordpress.com/latex.php?latex=m%3C%203&bg=EEEEEE&fg=8;s=0' title='m< 3' style='vertical-align:1%' class='tex' alt='m and maximum degree
f(m)' style='vertical-align:1%' class='tex' alt='\Delta > f(m)' /> 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.},
Title = {List coloring the square of sparse graphs with large degree},
Year = {2014}}
P. Ochem and A. Pinlou. "Application of entropy compression in pattern avoidance", The Electronic Journal of Combinatorics, vol. 21(2), pp. 1-12, 2014.
In combinatorics on words, a word
over an alphabet
is said to avoid a pattern
over an alphabet
if there is no factor
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
) 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
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
) is 3-avoidable (resp. 2-avoidable). This improves previous bounds due to Bell and Goh, and Rampersad.},
%% Arxiv = {},
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}}
L. Esperet, M. Montassier, P. Ochem, and A. Pinlou. "A complexity dichotomy for the coloring of sparse graphs", Journal of Graph Theory, vol. 73(1), pp. 85-102, 2013.
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
has a homomorphism to , but deciding whether a graph of girth
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
has a homomorphism to , but deciding whether a graph of girth
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}}
D. Goncalves, A. Parreau, and A. Pinlou. "Locally identifying coloring in bounded expansion classes of graphs", Discrete Applied Mathematics, vol. 161(18), pp. , 2013.
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 = {},
Author = {Goncalves, D. and Parreau, A. and Pinlou, A.},
Committee = {Yes},
Journal = {Discrete Applied Mathematics},
Volume = {161},
Number = {18},
Pages = {},
DOI = {10.1016/j.dam.},
Pdf = {gpp13.pdf},
Title = {Locally identifying coloring in bounded expansion classes of graphs},
Year = {2013}}
D. Goncalves, B. Lévêque, and A. Pinlou. "Triangle contact representations and duality", Discrete and Computational Geometry, vol. 48(1), pp. 239-254, 2012.
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.-012-9400-1},
Volume = {48},
Year = {2012},
Bdsk-Url-1 = {http://dx.doi.org/10.-012-9400-1}}
D. Goncalves, F. Havet, A. Pinlou, and S. Thomassé. "On spanning galaxies in digraphs", Discrete Applied Mathematics, vol. 160(6), pp. 744-754, 2012.
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
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.},
Volume = {160},
Year = {2012},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.dam.}}
D. Goncalves, A. Pinlou, M. Rao, and S. Thomassé. "The Domination Number of Grids", SIAM Journal of Discrete Mathematics, vol. 25, pp. , 2011.
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 = {},
Pdf = {gprt11.pdf},
Title = {The Domination Number of Grids},
Url = {http://dx.doi.org/10.4},
Volume = {25},
Year = {2011},
Bdsk-Url-1 = {http://dx.doi.org/10.4}}
A. Montejano, P. Ochem, A. Pinlou, A. Raspaud, and ?. Sopena. "Homomorphisms of 2-edge-colored graphs", Discrete Applied Mathematics, vol. 158(12), pp. , 2010.
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.},
Issn = {X},
Journal = {Discrete Applied Mathematics},
Keywords = {G Ma H O Partial $k$- P G Discharging procedure},
Number = {12},
Pages = {},
Pdf = {moprs10.pdf},
Title = {Homomorphisms of 2-edge-colored graphs},
Url = {http://www.sciencedirect.com/science/article/B6TYW-4XNVT7P-1/2/ee58db4cf8d97f07fd4467d},
Volume = {158},
Year = {2010},
Bdsk-Url-1 = {http://www.sciencedirect.com/science/article/B6TYW-4XNVT7P-1/2/ee58db4cf8d97f07fd4467d},
Bdsk-Url-2 = {http://dx.doi.org/10.1016/j.dam.}}
L. Addario-Berry, L. Esperet, R. J. Kang, C. J. H. McDiarmid, and A. Pinlou. "Acyclic improper colourings of graphs with bounded maximum degree", Discrete Mathematics, vol. 310(2), pp. 223-229, 2010.
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) (8] and Fertin, Raspaud and Reed [G. Fertin, A. Raspaud, B. Reed, Star coloring of graphs, J. Graph Theory 47 (3) (2].
@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) (8] and Fertin, Raspaud and Reed [G. Fertin, A. Raspaud, B. Reed, Star coloring of graphs, J. Graph Theory 47 (3) (2].},
Author = {Addario-Berry, L. and Esperet, L. and Kang, R.J. and McDiarmid, C.J.H and Pinlou, A.},
Doi = {10.1016/j.disc.},
Issn = {X},
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/627ca3c99541bedc1b3cd2},
Volume = {310},
Year = {2010},
Bdsk-Url-1 = {http://www.sciencedirect.com/science/article/B6V00-4THS3KV-2/2/627ca3c99541bedc1b3cd2},
Bdsk-Url-2 = {http://dx.doi.org/10.1016/j.disc.}}
A. Pinlou. "An oriented coloring of planar graphs with girth at least five", Discrete Mathematics, vol. 309(8), pp. , 2009.
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 (].
@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 (].},
Author = {Pinlou, A.},
Committee = {Yes},
Doi = {10.1016/j.disc.},
Issn = {X},
Journal = {Discrete Mathematics},
Keywords = { d 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.},
Volume = {309},
Year = {2009},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.disc.}}
P. Ochem and A. Pinlou. "Oriented colorings of partial 2-trees", Information Processing Letters, vol. 108, pp. 82-86, 2008.
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.},
Volume = {108},
Year = {2008},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RFFpOUy5vYmplY3RzV05TLmtleXNWJGNsYXNzog8QgASABqISE4ACgAOAB1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgNGRpXTlMuZGF0YU8RAXwAAAAAAXwAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMkCXXlIKwAAAAnPtAhvcDA4LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACdAgxRLyKgAAAAAAAAAAAAUAAwAACSAAAAAAAAAAAAAAAAAAAAANYmlibGlvZ3JhcGhpZQAAEAAIAADJAk9pAAAAEQAIAADFEtYKAAAAAQAQAAnPtAAJyZMACEyrAACTJwACADRNYWNpbnRvc2ggSEQ6VXNlcnM6YWxleDpUaGVzZTpiaWJsaW9ncmFwaGllOm9wMDgucGRmAA4AEgAIAG8AcAAwADgALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASACdVc2Vycy9hbGV4L1RoZXNlL2JpYmxpb2dyYXBoaWUvb3AwOC5wZGYAABMAAS8AABUAAgAL//8AAIAF0hwdHh9YJGNsYXNzZXNaJGNsYXNzbmFtZaMfICFdTlNNdXRhYmxlRGF0YVZOU0RhdGFYTlNPYmplY3RfECsuLi8uLi8uLi8uLi8uLi9UaGVzZS9iaWJsaW9ncmFwaGllL29wMDgucGRm0hwdJCWiJSFcTlNEaWN0aW9uYXJ5EgABhqBfEA9OU0tleWVkQXJjaGl2ZXIACAARABYAHwAoADIANQA6ADwARQBLAFIAXQBlAGwAbwBxAHMAdgB4AHoAfACGAJMAmACgAiACIgInAjACOwI/Ak0CVAJdAosCkAKTAqACpQAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAAK3},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.ipl.}}
M. Montassier, P. Ochem, and A. Pinlou. "Strong oriented chromatic number of planar graphs without short cycles", Discrete Mathematics and Theoretical Computer Science, vol. 10(1), pp. 1-24, 2008.
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}}
P. Ochem, A. Pinlou, and ?. Sopena. "On the oriented chromatic index of oriented graphs", Journal of Graph Theory, vol. 57(4), pp. 313-332, 2008.
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}}
A. Pinlou. "On oriented arc-coloring of subcubic graphs", Electronic Journal of Combinatorics, vol. 13(1), pp. 1-13, 2006.
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}}
A. Pinlou and ?. Sopena. "Oriented vertex and arc colorings of outerplanar graphs", Information Processing Letters, vol. 100(3), pp. 97-104, 2006.
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.},
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.}}
A. Pinlou and ?. Sopena. "The acircuitic directed star arboricity of subcubic graphs is at most four", Discrete Mathematics, vol. 306(24), pp. , 2006.
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 = {},
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.},
Volume = {306},
Year = {2006},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.disc.}}
International conferences and workshops with program committee
F. Dross, M. Montassier, and A. Pinlou. <>, in 4th Bordeaux Graph Workshop,
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}}
B. Lu?ar, M. Mockov?iaková, P. Ochem, A. Pinlou, and R. Soták. <>, in 4th Bordeaux Graph Workshop,
@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}}
F. Dross, M. Montassier, and A. Pinlou. <>, in European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015,
2015, pp. 269-275.
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.},
D. Gon?alves, M. Montassier, and A. Pinlou. <>, in 9th International colloquium on graph theory and combinatorics,
We propose a general framework bas}
赠送免券下载特权
10W篇文档免费专享
部分付费文档8折起
每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
SPE外文翻译
阅读已结束，下载本文需要
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，同时保存到云知识，更方便管理
加入VIP
还剩9页未读，
定制HR最喜欢的简历
你可能喜欢Alexandre Pinlou - Home Page – Publications
Publications
International journals with program committee
B. Lu?ar, P. Ochem, and A. Pinlou. “On repetition thresholds of caterpillars and trees of bounded degree”, Electronic Journal of Combinatorics, vol. 25(1), pp. 1-10, 2018.
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.
@article{lop18,
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.},
journal = {Electronic Journal of Combinatorics},
year = {2018},
Pdf = {lop18.pdf},
URL = {http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p61/pdf},
pages = {1--10},
volume = {25},
number = {1}
F. Dross, M. Montassier, and A. Pinlou. “Partitioning sparse graphs into an independent set and a forest of bounded degree”, Electronic Journal of Combinatorics, vol. 25(1), pp. 1-13, 2018.
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.
@article{dmp18,
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 = {Electronic Journal of Combinatorics},
author = {Dross, F. and Montassier, M. and Pinlou, A.},
year = {2018},
Pdf = {dmp18.pdf},
URL = {http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p45},
pages = {1--13},
volume = {25},
number = {1}
F. Dross, M. Montassier, and A. Pinlou. "Partitioning a triangle-free planar graph into a forest and a forest of bounded degree", European Journal of Combinatorics, vol. 66, pp. 81-94, 2017.
An -partition of a graph is a vertex-partition into two sets
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
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 = {},
committee = {Yes},
journal = {European Journal of Combinatorics},
volume = {66},
pages = {81-94},
Pdf = {dmp17.pdf},
DOI = {10.1016/j.ejc.}
P. Ochem, A. Pinlou, and S. Sen. "Homomorphisms of 2-edge-colored triangle-free planar graphs", Journal of Graph Theory, vol. 85(1), pp. 258-277, 2017.
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 = {},
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%8},
Year = {2017},
DOI = {10.1002/jgt.22059},
M. Bonamy, M. Knor, B. Lu?ar, A. Pinlou, and R. ?krekovski. "On the difference between the Szeged and Wiener index", Applied Mathematics and Computation, vol. 312, pp. 202-213, 2017.
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
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
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 = {},
Pdf = {bklps17.pdf},
DOI = {10.1016/j.amc.},
URL = {http://www.sciencedirect.com/science/article/pii/S348X}
F. Dross, M. Montassier, and A. Pinlou. "A lower bound on the order of the largest induced forest in planar graphs with high girth", Discrete Applied Mathematics, vol. 214, pp. 99-107, 2016.
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
has a feedback vertex set of size at most , improving the trivial bound of . We also prove that every -connected graph with maximum degree
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
has a feedback vertex set of size at most , improving the trivial bound of . We also prove that every -connected graph with maximum degree
has a feedback vertex set of size at most .},
author = {Dross, F. and Montassier, M. and Pinlou, A.},
year = {2016},
%% Arxiv = {},
Committee = {Yes},
Journal = {Discrete Applied Mathematics},
Volume = {214},
Pages = {99-107},
DOI = {10.1016/j.dam.},
Pdf = {dmp16d.pdf},
M. Bonamy, B. Lévêque, and A. Pinlou. "Planar graphs with
and no triangle adjacent to a
are minimally edge- and total-choosable", Discrete Mathematics and Theoretical Computer Science, vol. 17(3), 2016.
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
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
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
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
and no triangle adjacent to a
are minimally
edge and total choosable.},
%% Arxiv = {},
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},
M. Bonamy, B. Lévêque, and A. Pinlou. "Graphs with maximum degree
and maximum average degree less than 3 are list 2-distance ()-colorable", Discrete Mathematics, vol. 317, pp. 19-32, 2014.
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.},
Title = {Graphs with maximum degree
and maximum average degree less than 3 are list 2-distance ()-colorable},
Year = {2014}}
M. Bonamy, B. Lévêque, and A. Pinlou. "2-distance coloring of sparse graphs", Journal of Graph Theory, vol. 77(3), pp. 190-218, 2014.
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
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
(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
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
remains open. We prove also that any graph with maximum average degree <img src='http://l.wordpress.com/latex.php?latex=m%20%3C%204&bg=EEEEEE&fg=8;s=0' title='m < 4' style='vertical-align:1%' class='tex' alt='m
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
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
(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
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
remains open. We prove also that any graph with maximum average degree <img src='http://l.wordpress.com/latex.php?latex=m%20%3C%204&bg=EEEEEE&fg=8;s=0' title='m < 4' style='vertical-align:1%' class='tex' alt='m
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}}
P. Ochem and A. Pinlou. "Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs", Graphs and Combinatorics, vol. 30(2), pp. 439-453, 2014.
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.-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}}
M. Bonamy, B. Lévêque, and A. Pinlou. "List coloring the square of sparse graphs with large degree", European Journal of Combinatorics, vol. 41, pp. 128-137, 2014.
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 <img src='http://l.wordpress.com/latex.php?latex=%5Cfrac145%20%3C%203&bg=EEEEEE&fg=8;s=0' title='\frac145 < 3' style='vertical-align:1%' class='tex' alt='\frac145 .
We strengthen their result and prove that there exists a function f such that the square of
any graph with maximum average degreem <img src='http://l.wordpress.com/latex.php?latex=m%3C%203&bg=EEEEEE&fg=8;s=0' title='m< 3' style='vertical-align:1%' class='tex' alt='m and maximum degree
f(m)' style='vertical-align:1%' class='tex' alt='\Delta > f(m)' /> 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.
@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 <img src='http://l.wordpress.com/latex.php?latex=%5Cfrac%7B14%7D%7B5%7D%20%3C%203&bg=EEEEEE&fg=8;s=0' title='\frac{14}{5} < 3' style='vertical-align:1%' class='tex' alt='\frac{14}{5} .
We strengthen their result and prove that there exists a function f such that the square of
any graph with maximum average degreem <img src='http://l.wordpress.com/latex.php?latex=m%3C%203&bg=EEEEEE&fg=8;s=0' title='m< 3' style='vertical-align:1%' class='tex' alt='m and maximum degree
f(m)' style='vertical-align:1%' class='tex' alt='\Delta > f(m)' /> 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.},
Title = {List coloring the square of sparse graphs with large degree},
Year = {2014}}
P. Ochem and A. Pinlou. "Application of entropy compression in pattern avoidance", The Electronic Journal of Combinatorics, vol. 21(2), pp. 1-12, 2014.
In combinatorics on words, a word
over an alphabet
is said to avoid a pattern
over an alphabet
if there is no factor
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
) 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
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
) is 3-avoidable (resp. 2-avoidable). This improves previous bounds due to Bell and Goh, and Rampersad.},
%% Arxiv = {},
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}}
L. Esperet, M. Montassier, P. Ochem, and A. Pinlou. "A complexity dichotomy for the coloring of sparse graphs", Journal of Graph Theory, vol. 73(1), pp. 85-102, 2013.
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
has a homomorphism to , but deciding whether a graph of girth
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
has a homomorphism to , but deciding whether a graph of girth
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}}
D. Goncalves, A. Parreau, and A. Pinlou. "Locally identifying coloring in bounded expansion classes of graphs", Discrete Applied Mathematics, vol. 161(18), pp. , 2013.
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 = {},
Author = {Goncalves, D. and Parreau, A. and Pinlou, A.},
Committee = {Yes},
Journal = {Discrete Applied Mathematics},
Volume = {161},
Number = {18},
Pages = {},
DOI = {10.1016/j.dam.},
Pdf = {gpp13.pdf},
Title = {Locally identifying coloring in bounded expansion classes of graphs},
Year = {2013}}
D. Goncalves, B. Lévêque, and A. Pinlou. "Triangle contact representations and duality", Discrete and Computational Geometry, vol. 48(1), pp. 239-254, 2012.
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.-012-9400-1},
Volume = {48},
Year = {2012},
Bdsk-Url-1 = {http://dx.doi.org/10.-012-9400-1}}
D. Goncalves, F. Havet, A. Pinlou, and S. Thomassé. "On spanning galaxies in digraphs", Discrete Applied Mathematics, vol. 160(6), pp. 744-754, 2012.
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
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.},
Volume = {160},
Year = {2012},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.dam.}}
D. Goncalves, A. Pinlou, M. Rao, and S. Thomassé. "The Domination Number of Grids", SIAM Journal of Discrete Mathematics, vol. 25, pp. , 2011.
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 = {},
Pdf = {gprt11.pdf},
Title = {The Domination Number of Grids},
Url = {http://dx.doi.org/10.4},
Volume = {25},
Year = {2011},
Bdsk-Url-1 = {http://dx.doi.org/10.4}}
A. Montejano, P. Ochem, A. Pinlou, A. Raspaud, and ?. Sopena. "Homomorphisms of 2-edge-colored graphs", Discrete Applied Mathematics, vol. 158(12), pp. , 2010.
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.},
Issn = {X},
Journal = {Discrete Applied Mathematics},
Keywords = {G Ma H O Partial $k$- P G Discharging procedure},
Number = {12},
Pages = {},
Pdf = {moprs10.pdf},
Title = {Homomorphisms of 2-edge-colored graphs},
Url = {http://www.sciencedirect.com/science/article/B6TYW-4XNVT7P-1/2/ee58db4cf8d97f07fd4467d},
Volume = {158},
Year = {2010},
Bdsk-Url-1 = {http://www.sciencedirect.com/science/article/B6TYW-4XNVT7P-1/2/ee58db4cf8d97f07fd4467d},
Bdsk-Url-2 = {http://dx.doi.org/10.1016/j.dam.}}
L. Addario-Berry, L. Esperet, R. J. Kang, C. J. H. McDiarmid, and A. Pinlou. "Acyclic improper colourings of graphs with bounded maximum degree", Discrete Mathematics, vol. 310(2), pp. 223-229, 2010.
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) (8] and Fertin, Raspaud and Reed [G. Fertin, A. Raspaud, B. Reed, Star coloring of graphs, J. Graph Theory 47 (3) (2].
@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) (8] and Fertin, Raspaud and Reed [G. Fertin, A. Raspaud, B. Reed, Star coloring of graphs, J. Graph Theory 47 (3) (2].},
Author = {Addario-Berry, L. and Esperet, L. and Kang, R.J. and McDiarmid, C.J.H and Pinlou, A.},
Doi = {10.1016/j.disc.},
Issn = {X},
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/627ca3c99541bedc1b3cd2},
Volume = {310},
Year = {2010},
Bdsk-Url-1 = {http://www.sciencedirect.com/science/article/B6V00-4THS3KV-2/2/627ca3c99541bedc1b3cd2},
Bdsk-Url-2 = {http://dx.doi.org/10.1016/j.disc.}}
A. Pinlou. "An oriented coloring of planar graphs with girth at least five", Discrete Mathematics, vol. 309(8), pp. , 2009.
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 (].
@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 (].},
Author = {Pinlou, A.},
Committee = {Yes},
Doi = {10.1016/j.disc.},
Issn = {X},
Journal = {Discrete Mathematics},
Keywords = { d 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.},
Volume = {309},
Year = {2009},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.disc.}}
P. Ochem and A. Pinlou. "Oriented colorings of partial 2-trees", Information Processing Letters, vol. 108, pp. 82-86, 2008.
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.},
Volume = {108},
Year = {2008},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RFFpOUy5vYmplY3RzV05TLmtleXNWJGNsYXNzog8QgASABqISE4ACgAOAB1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgNGRpXTlMuZGF0YU8RAXwAAAAAAXwAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMkCXXlIKwAAAAnPtAhvcDA4LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACdAgxRLyKgAAAAAAAAAAAAUAAwAACSAAAAAAAAAAAAAAAAAAAAANYmlibGlvZ3JhcGhpZQAAEAAIAADJAk9pAAAAEQAIAADFEtYKAAAAAQAQAAnPtAAJyZMACEyrAACTJwACADRNYWNpbnRvc2ggSEQ6VXNlcnM6YWxleDpUaGVzZTpiaWJsaW9ncmFwaGllOm9wMDgucGRmAA4AEgAIAG8AcAAwADgALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASACdVc2Vycy9hbGV4L1RoZXNlL2JpYmxpb2dyYXBoaWUvb3AwOC5wZGYAABMAAS8AABUAAgAL//8AAIAF0hwdHh9YJGNsYXNzZXNaJGNsYXNzbmFtZaMfICFdTlNNdXRhYmxlRGF0YVZOU0RhdGFYTlNPYmplY3RfECsuLi8uLi8uLi8uLi8uLi9UaGVzZS9iaWJsaW9ncmFwaGllL29wMDgucGRm0hwdJCWiJSFcTlNEaWN0aW9uYXJ5EgABhqBfEA9OU0tleWVkQXJjaGl2ZXIACAARABYAHwAoADIANQA6ADwARQBLAFIAXQBlAGwAbwBxAHMAdgB4AHoAfACGAJMAmACgAiACIgInAjACOwI/Ak0CVAJdAosCkAKTAqACpQAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAAK3},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.ipl.}}
M. Montassier, P. Ochem, and A. Pinlou. "Strong oriented chromatic number of planar graphs without short cycles", Discrete Mathematics and Theoretical Computer Science, vol. 10(1), pp. 1-24, 2008.
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}}
P. Ochem, A. Pinlou, and ?. Sopena. "On the oriented chromatic index of oriented graphs", Journal of Graph Theory, vol. 57(4), pp. 313-332, 2008.
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}}
A. Pinlou. "On oriented arc-coloring of subcubic graphs", Electronic Journal of Combinatorics, vol. 13(1), pp. 1-13, 2006.
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}}
A. Pinlou and ?. Sopena. "Oriented vertex and arc colorings of outerplanar graphs", Information Processing Letters, vol. 100(3), pp. 97-104, 2006.
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.},
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.}}
A. Pinlou and ?. Sopena. "The acircuitic directed star arboricity of subcubic graphs is at most four", Discrete Mathematics, vol. 306(24), pp. , 2006.
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 = {},
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.},
Volume = {306},
Year = {2006},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.disc.}}
International conferences and workshops with program committee
F. Dross, M. Montassier, and A. Pinlou. <>, in 4th Bordeaux Graph Workshop,
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}}
B. Lu?ar, M. Mockov?iaková, P. Ochem, A. Pinlou, and R. Soták. <>, in 4th Bordeaux Graph Workshop,
@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}}
F. Dross, M. Montassier, and A. Pinlou. <>, in European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015,
2015, pp. 269-275.
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.},
D. Gon?alves, M. Montassier, and A. Pinlou. <>, in 9th International colloquium on graph theory and combinatorics,
We propose a general framework bas}
我要回帖
更多关于 spe是什么 的文章
更多推荐
- ·EXCEL复制可以但粘贴不了的东西为什么不能粘贴到word中？
- ·日本的宗教信仰中，神道教、佛教和基督教和佛教冲突吗各占了多少比例？
- ·马国柱全国统一的阿訇资格证马国柱
- ·想问问cad打开图纸不显示图形是什么原因为什么会这样？
- ·几年前看过的小说，男主和魔物娘勇者的正经游戏不知道怎么样就可以用她的能力之后可以随便用？
- ·AG亚游守望先锋亚服怎么注册册
- ·刀塔传奇战队经验2有厉害的战队收人吗？求组队
- ·求一款rpg网页单机游戏rpg游戏
- ·有没有和我一样的，光棍节撸一天游戏的？
- ·剑魂神思者刷图带什么武器器，高强的话
- ·这ps颜色配置文件默认值值不值得这价格。玩LOL DNF能流畅不
- ·谁有dnf手机版的dnf加点模拟器器要标准的。
- ·我要在我的简历上如何写简历技能特长长呢？有经验的帮帮忙给点意见
- ·魔兽世界发邮件找不到账号里的游戏角色找不到了
- ·游戏王假面 关于假面变色龙的问题
- ·吞噬苍穹ol游戏音乐 天幻克制什么职业
- ·自然奇迹the namirnamir 雪玫瑰花水怎么样
- ·疾风之刃二级密码解除可解除绑定次数是什么意思
- ·怎么查s4是那个版
- ·spe proceedings cdspe是什么抗生素意思
- ·刚打了怒之煞掉落坐骑，拿到掉落但是不让我摸尸体怎么办
- ·手机版我的世界船怎么做怎么做船 图
- ·天天酷跑神秘海域2成就成就怎么完成
- ·手机我的世界遗迹种子手机版都有哪些遗际
- ·世界OL修真全加易骗体质第一话的话怎么拿剑，不会得吃药吧?
- ·普痛最新扑克感应分析仪分析仪是骗人的吗
- ·lollols8奥巴马出装主什么
- ·口袋妖怪xy忍蛙后花园谁后花园有火狐狸
- ·请问有什么小的网络游戏适合和梦见和小女孩一起玩玩的
- ·灵魂回响官网为什么我60级了公会里看才59级呀
- ·为什么我玩射击游戏头晕会头晕 腹部还有一种空虚感
- ·天天地铁酷跑小游戏解锁魔法城堡怎么成就不够怎么解锁
- ·浙江日发精机机 3级保密资质有什么作用
- ·求一个Cf，带坑字的游戏名名，要看起来很坑队友的样子，但是名字要好听点的，
- ·谁是一个我就是传奇主要人物的人物呢？
