Yannis Manoussakis
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Yannis Manoussakis has a total of 33 co-authors. Here are the top co-authors by number of shared publications:
- Leandro Montero
Laboratoire de Recherche en Informatique Université Paris-Sud 91405 Orsay CEDEX France
3 shared publications - A. El Maftouhi
Université Paris-Sud, L.R.I Bât. 650 91405 Orsay Cedex France
2 shared publications - Carlos Martinhon
Fluminense Fed Univ, Inst Computat, BR-24210240 Niteroi, RJ, Brazil
2 shared publications - Hong Phong Pham
University Paris-Saclay
2 shared publications - Johan Thapper
Universite Paris-Est Marne-la-Vallee France
2 shared publications - Marek Karpinski
Univ Bonn, Dept Comp Sci, Bonn, Germany
2 shared publications
Latest Publications
- 1 August 2019
- Published by Elsevier in European Journal of Combinatorics
- Vol. 80, 296-310
Maximum colored trees in edge-colored graphs
- 1 August 2019
- Published by Elsevier in European Journal of Combinatorics
- Vol. 80, 296-310
Maximum colored trees in edge-colored graphs
- 17 July 2018
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 68, 251-256
Maximum colorful independent sets in vertex-colored graphs
- 17 July 2018
- Published by Elsevier in Electronic Notes in Discrete Mathematics
- Vol. 68, 251-256
Maximum colorful independent sets in vertex-colored graphs
- Open Access
On the number of vertex-disjoint cycles in digraphs
Let $k$ be a positive integer. Bermond and Thomassen conjectured in 1981 that every digraph with minimum outdegree at least $2k-1$ contains $k$ vertex-disjoint cycles. It is famous as one of the one hundred unsolved problems selected in [Bondy, Murty, Graph Theory, Springer-Verlag London, 2008]. Lichiardopol, Por and Sereni proved in [SIAM J. Discrete Math. 23 (2) (2009) 979-992] that the above conjecture holds for $k=3$. Let $g$ be the girth, i.e., the length of the shortest cycle, of a given digraph. Bang-Jensen, Bessy and Thomass\'{e} conjectured in [J. Graph Theory 75 (3) (2014) 284-302] that every digraph with girth $g$ and minimum outdegree at least $\frac{g}{g-1}k$ contains $k$ vertex-disjoint cycles. Thomass\'{e} conjectured around 2005 that every oriented graph (a digraph without 2-cycles) with girth $g$ and minimum outdegree at least $h$ contains a path of length $h(g-1)$, where $h$ is a positive integer. In this note, we first present a new shorter proof of the Bermond-Thomassen conjecture for the case of $k=3$, and then we disprove the conjecture proposed by Bang-Jensen, Bessy and Thomass\'{e}. Finally, we disprove the even girth case of the conjecture proposed by Thomass\'{e}.Open AccessOn the number of vertex-disjoint cycles in digraphs
Let $k$ be a positive integer. Bermond and Thomassen conjectured in 1981 that every digraph with minimum outdegree at least $2k-1$ contains $k$ vertex-disjoint cycles. It is famous as one of the one hundred unsolved problems selected in [Bondy, Murty, Graph Theory, Springer-Verlag London, 2008]. Lichiardopol, Por and Sereni proved in [SIAM J. Discrete Math. 23 (2) (2009) 979-992] that the above conjecture holds for $k=3$. Let $g$ be the girth, i.e., the length of the shortest cycle, of a given digraph. Bang-Jensen, Bessy and Thomass\'{e} conjectured in [J. Graph Theory 75 (3) (2014) 284-302] that every digraph with girth $g$ and minimum outdegree at least $\frac{g}{g-1}k$ contains $k$ vertex-disjoint cycles. Thomass\'{e} conjectured around 2005 that every oriented graph (a digraph without 2-cycles) with girth $g$ and minimum outdegree at least $h$ contains a path of length $h(g-1)$, where $h$ is a positive integer. In this note, we first present a new shorter proof of the Bermond-Thomassen conjecture for the case of $k=3$, and then we disprove the conjecture proposed by Bang-Jensen, Bessy and Thomass\'{e}. Finally, we disprove the even girth case of the conjecture proposed by Thomass\'{e}. - Open Access
Proper Hamiltonian Cycles in Edge-Colored Multigraphs
A $c$-edge-colored multigraph has each edge colored with one of the $c$ available colors and no two parallel edges have the same color. A proper Hamiltonian cycle is a cycle containing all the vertices of the multigraph such that no two adjacent edges have the same color. In this work we establish sufficient conditions for a multigraph to have a proper Hamiltonian cycle, depending on several parameters such as the number of edges and the rainbow degree.Open AccessProper Hamiltonian Cycles in Edge-Colored Multigraphs
A $c$-edge-colored multigraph has each edge colored with one of the $c$ available colors and no two parallel edges have the same color. A proper Hamiltonian cycle is a cycle containing all the vertices of the multigraph such that no two adjacent edges have the same color. In this work we establish sufficient conditions for a multigraph to have a proper Hamiltonian cycle, depending on several parameters such as the number of edges and the rainbow degree. - Open Access
Tropical Dominating Sets in Vertex-Coloured Graphs
Given a vertex-coloured graph, a dominating set is said to be tropical if every colour of the graph appears at least once in the set. Here, we study minimum tropical dominating sets from structural and algorithmic points of view. First, we prove that the tropical dominating set problem is NP-complete even when restricted to a simple path. Then, we establish upper bounds related to various parameters of the graph such as minimum degree and number of edges. We also give upper bounds for random graphs. Last, we give approximability and inapproximability results for general and restricted classes of graphs, and establish a FPT algorithm for interval graphs.
Open AccessTropical Dominating Sets in Vertex-Coloured Graphs
Given a vertex-coloured graph, a dominating set is said to be tropical if every colour of the graph appears at least once in the set. Here, we study minimum tropical dominating sets from structural and algorithmic points of view. First, we prove that the tropical dominating set problem is NP-complete even when restricted to a simple path. Then, we establish upper bounds related to various parameters of the graph such as minimum degree and number of edges. We also give upper bounds for random graphs. Last, we give approximability and inapproximability results for general and restricted classes of graphs, and establish a FPT algorithm for interval graphs.
- 1 January 2016
- Published by Springer Nature
- p. 17-27
Tropical Dominating Sets in Vertex-Coloured Graphs
- 1 January 2016
- Published by Springer Nature
- p. 17-27
Tropical Dominating Sets in Vertex-Coloured Graphs
- Open Access
Proper Hamiltonian Paths in Edge-Coloured Multigraphs
Given a $c$-edge-coloured multigraph, a proper Hamiltonian path is a path that contains all the vertices of the multigraph such that no two adjacent edges have the same colour. In this work we establish sufficient conditions for an edge-coloured multigraph to guarantee the existence of a proper Hamiltonian path, involving various parameters as the number of edges, the number of colours, the rainbow degree and the connectivity.
Open AccessProper Hamiltonian Paths in Edge-Coloured Multigraphs
Given a $c$-edge-coloured multigraph, a proper Hamiltonian path is a path that contains all the vertices of the multigraph such that no two adjacent edges have the same colour. In this work we establish sufficient conditions for an edge-coloured multigraph to guarantee the existence of a proper Hamiltonian path, involving various parameters as the number of edges, the number of colours, the rainbow degree and the connectivity.
- Open Access
- 4 December 2012
- Published by Internet Mathematics in Internet Mathematics
- Vol. 8 (4) , 364-380
Balance in Random Signed Graphs
By O. Megalakaki, Y. Manoussakis & 1 more. By extending Heider’s and Cartwright–Harary’s theory of balance in deterministic social structures, we study the problem of balance in social structures...
- 4 December 2012
- Published by Internet Mathematics in Internet Mathematics
- Vol. 8 (4) , 364-380
Open AccessBalance in Random Signed Graphs
By O. Megalakaki, Y. Manoussakis & 1 more. By extending Heider’s and Cartwright–Harary’s theory of balance in deterministic social structures, we study the problem of balance in social structures...
- 28 February 2010
- Published by Elsevier in European Journal of Combinatorics
- Vol. 31 (2) , 419-422
Preface
- 28 February 2010
- Published by Elsevier in European Journal of Combinatorics
- Vol. 31 (2) , 419-422
Preface
- 20 October 2009
- Published by Wiley in Journal of Graph Theory
- Vol. 64 (1) , 63-86
Cycles and paths in edge‐colored graphs with given degrees
Sufficient degree conditions for the existence of properly edge‐colored cycles and paths in edge‐colored graphs, multigraphs and random graphs are investigated. In particular, we prove that an edge‐colored multigraph of order n on at least three colors and with minimum colored degree greater than or equal to ⌈(n+1)/2⌉ has properly edge‐colored cycles of all possible lengths, including hamiltonian cycles. Longest properly edge‐colored paths and hamiltonian paths between given vertices are considered as well. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 63–86, 2010
- 20 October 2009
- Published by Wiley in Journal of Graph Theory
- Vol. 64 (1) , 63-86
Cycles and paths in edge‐colored graphs with given degrees
Sufficient degree conditions for the existence of properly edge‐colored cycles and paths in edge‐colored graphs, multigraphs and random graphs are investigated. In particular, we prove that an edge‐colored multigraph of order n on at least three colors and with minimum colored degree greater than or equal to ⌈(n+1)/2⌉ has properly edge‐colored cycles of all possible lengths, including hamiltonian cycles. Longest properly edge‐colored paths and hamiltonian paths between given vertices are considered as well. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 63–86, 2010