Christophe Picouleau
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
Christophe Picouleau has a total of 34 co-authors. Here are the top co-authors by number of shared publications:
- Bernard Ries
Department of Informatics, University of Fribourg, Fribourg, Switzerland
12 shared publications - Daniël Paulusma
Durham University, Durham, UK
6 shared publications - Dominique de Werra
École Polytechnique Fédérale de Lausanne
5 shared publications - Marie-Christine Costa
CEDRIC-CNAM, 292 Rue Saint-Martin, 75141 Paris Cedex 03, France
5 shared publications - François Delbot
CNRS, LIP6, Sorbonne Université, Paris, France
4 shared publications - Andrea Frosini
University of Florence
3 shared publications
Latest Publications
- 7 May 2025
- Published by Springer Nature in Annals of Operations Research
- p. 1-12
Partition of graphs with maximum degree ratio
- 7 May 2025
- Published by Springer Nature in Annals of Operations Research
- p. 1-12
Partition of graphs with maximum degree ratio
- Open Access
- 18 May 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 355, 232-246
The complexity of 2-intersection graphs of 3-hypergraphs recognition for claw-free graphs and triangulated claw-free graphs
- 18 May 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 355, 232-246
Open AccessThe complexity of 2-intersection graphs of 3-hypergraphs recognition for claw-free graphs and triangulated claw-free graphs
- Open Access
The Complexity of 2-Intersection Graphs of 3-Hypergraphs Recognition for Claw-free Graphs and triangulated Claw-free Graphs
Given a 3-uniform hypergraph H, its 2-intersection graph G has for vertex set the hyperedges of H and ee' is an edge of G whenever e and e' have exactly two common vertices in H. Di Marco et al. prove that deciding wether a graph G is the 2-intersection graph of a 3-uniform hypergraph is NP-complete. The main problems we study concern the class of claw-free graphs. We show that the recognition problem remains NP-complete when G is claw-free graphs but becomes polynomial if in addition G is triangulated.
Open AccessThe Complexity of 2-Intersection Graphs of 3-Hypergraphs Recognition for Claw-free Graphs and triangulated Claw-free Graphs
Given a 3-uniform hypergraph H, its 2-intersection graph G has for vertex set the hyperedges of H and ee' is an edge of G whenever e and e' have exactly two common vertices in H. Di Marco et al. prove that deciding wether a graph G is the 2-intersection graph of a 3-uniform hypergraph is NP-complete. The main problems we study concern the class of claw-free graphs. We show that the recognition problem remains NP-complete when G is claw-free graphs but becomes polynomial if in addition G is triangulated.
- Open Access
On the complexity of Dominating Set for graphs with fixed diameter
A set $S\subseteq V$ of a graph $G=(V,E)$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$. Dominating Set is the problem of deciding, given a graph $G$ and an integer $k\geq 1$, if $G$ has a dominating set of size at most $k$. It is well known that this problem is $\mathsf{NP}$-complete even for claw-free graphs. We give a complexity dichotomy for Dominating Set for the class of claw-free graphs with diameter $d$. We show that the problem is $\mathsf{NP}$-complete for every fixed $d\ge 3$ and polynomial time solvable for $d\le 2$. To prove the case $d=2$, we show that Minimum Maximal Matching can be solved in polynomial time for $2K_2$-free graphs.Open AccessOn the complexity of Dominating Set for graphs with fixed diameter
A set $S\subseteq V$ of a graph $G=(V,E)$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$. Dominating Set is the problem of deciding, given a graph $G$ and an integer $k\geq 1$, if $G$ has a dominating set of size at most $k$. It is well known that this problem is $\mathsf{NP}$-complete even for claw-free graphs. We give a complexity dichotomy for Dominating Set for the class of claw-free graphs with diameter $d$. We show that the problem is $\mathsf{NP}$-complete for every fixed $d\ge 3$ and polynomial time solvable for $d\le 2$. To prove the case $d=2$, we show that Minimum Maximal Matching can be solved in polynomial time for $2K_2$-free graphs. - Open Access
Partition of graphs with maximum degree ratio
Given a graph $G$ and a non trivial partition $(V_1,V_2)$ of its vertex-set, the satisfaction of a vertex $v\in V_i$ is the ratio between the size of it's closed neighborhood in $V_i$ and the size of its closed neighborhood in $G$. The worst ratio over all the vertices defines the quality of the partition. We define $q(G)$ the degree ratio of a graph as the maximum of the worst ratio over all the non trivial partitions. We give bounds and exact values of $q(G)$ for some classes of graphs. We also show some complexity results for the associated optimization or decision problems.Open AccessPartition of graphs with maximum degree ratio
Given a graph $G$ and a non trivial partition $(V_1,V_2)$ of its vertex-set, the satisfaction of a vertex $v\in V_i$ is the ratio between the size of it's closed neighborhood in $V_i$ and the size of its closed neighborhood in $G$. The worst ratio over all the vertices defines the quality of the partition. We define $q(G)$ the degree ratio of a graph as the maximum of the worst ratio over all the non trivial partitions. We give bounds and exact values of $q(G)$ for some classes of graphs. We also show some complexity results for the associated optimization or decision problems. - Open Access
The complexity of the Perfect Matching-Cut problem
Perfect Matching-Cut is the problem of deciding whether a graph has a perfect matching that contains an edge-cut. We show that this problem is NP-complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five-regular graphs, for graphs of diameter three and for bipartite graphs of diameter four. We show that there exist polynomial time algorithms for the following classes of graphs: claw-free, $P_5$-free, diameter two, bipartite with diameter three and graphs with bounded tree-width.
Open AccessThe complexity of the Perfect Matching-Cut problem
Perfect Matching-Cut is the problem of deciding whether a graph has a perfect matching that contains an edge-cut. We show that this problem is NP-complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five-regular graphs, for graphs of diameter three and for bipartite graphs of diameter four. We show that there exist polynomial time algorithms for the following classes of graphs: claw-free, $P_5$-free, diameter two, bipartite with diameter three and graphs with bounded tree-width.
- Open Access
The Minimum Dominating Set problem is polynomial for (claw, P8)-free graphs
We prove that the Minimum Dominating Set problem is polynomial for the class of (claw, P8)-free graphs.
Open AccessThe Minimum Dominating Set problem is polynomial for (claw, P8)-free graphs
We prove that the Minimum Dominating Set problem is polynomial for the class of (claw, P8)-free graphs.
- 16 April 2021
- Published by Elsevier in Theoretical Computer Science
- Vol. 868, 97-111
New sufficient conditions on the degree sequences of uniform hypergraphs
- 16 April 2021
- Published by Elsevier in Theoretical Computer Science
- Vol. 868, 97-111
New sufficient conditions on the degree sequences of uniform hypergraphs
- Open Access
On Minimum Dominating Sets in cubic and (claw,H)-free graphs
Given a graph $G=(V,E)$, $S\subseteq V$ is a dominating set if every $v\in V\setminus S$ is adjacent to an element of $S$. The Minimum Dominating Set problem asks for a dominating set with minimum cardinality. It is well known that its decision version is $NP$-complete even when $G$ is a claw-free graph. We give a complexity dichotomy for the Minimum Dominating Set problem for the class of $(claw, H)$-free graphs when $H$ has at most six vertices. In an intermediate step we show that the Minimum Dominating Set problem is $NP$-complete for cubic graphs.Open AccessOn Minimum Dominating Sets in cubic and (claw,H)-free graphs
Given a graph $G=(V,E)$, $S\subseteq V$ is a dominating set if every $v\in V\setminus S$ is adjacent to an element of $S$. The Minimum Dominating Set problem asks for a dominating set with minimum cardinality. It is well known that its decision version is $NP$-complete even when $G$ is a claw-free graph. We give a complexity dichotomy for the Minimum Dominating Set problem for the class of $(claw, H)$-free graphs when $H$ has at most six vertices. In an intermediate step we show that the Minimum Dominating Set problem is $NP$-complete for cubic graphs. - 28 December 2019
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 282, 65-79
Minimal graphs for 2-factor extension
- 28 December 2019
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 282, 65-79
Minimal graphs for 2-factor extension