Lucas Pastor
Laboratoire G-SCOP, bureau B521
46 avenue Félix Viallet
38031 Grenoble Cedex 1
France
Telephone: +33 (0) 4 56 52 98 22
Mail: lucas.pastor@g-scop.grenoble-inp.fr
I'm a second year PhD student in the Combinatorial Optimization team of G-SCOP. My advisors are Frédéric Maffray (G-SCOP) and Sylvain Gravier (Institut Fourier).
I'm working on graph theory. I am interested in about everything in this field even though my main works are about graph coloring and structural graph theory.
A graph $G$ is called normal if there exist two coverings, $\mathbb{C}$ and $\mathbb{S}$ of its vertex set such that every member of $\mathbb{C}$ induces a clique in $G$, every member of $\mathbb{S}$ induces an independent set in $G$ and $C \cap S \neq \emptyset$ for every $C \in \mathbb{C}$ and $S \in \mathbb{S}$. It has been conjectured by De Simone and Körner in 1999 that a graph $G$ is normal if $G$ does not contain $C_5$, $C_7$ and $\overline{C_7}$ as an induced subgraph. We disprove this conjecture.
We present a polynomial-time algorithm that finds a maximum weight stable set in a graph that does not contain as an induced subgraph an induced path on six vertices or a bull (the graph with vertices $a, b, c, d, e$ and edges $ab, bc, cd, be, ce$).
It has been conjectured that for every claw-free graph $G$ the choice number of $G$ is equal to its chromatic number. We focus on the special case of this conjecture where $G$ is perfect. Claw-free perfect graphs can be decomposed via clique-cutset into two special classes called elementary graphs and peculiar graphs. Based on this decomposition we prove that the conjecture holds true for every claw-free perfect graph with maximum clique size at most $4$.
We present a polynomial-time algorithm that determines whether a graph that contains no induced path on six vertices and no bull (the graph with vertices $a,b,c,d,e$ and edges $ab,bc,cd,be,ce$) is $4$-colorable. We also show that for any fixed $k$ the $k$-coloring problem can be solved in polynomial time in the class of $(P_6,\mbox{bull},\mbox{gem})$-free graphs.
Séminaire LaBRI, équipe Graphes et Optimisation (Bordeaux, France) March 4 2016 The coloring problem in graphs with structural restrictions.
Séminaire G-SCOP (Grenoble, France) October 1st 2015 Coloration par liste dans les graphes parfaits sans griffe.
Third STINT meeting (Autrans, France) June 30 2015 List-coloring in claw-free perfect graphs.
2015-2016 Introduction à UNIX et à la programmation en langage C (introduction to UNIX and C programming), L1, TD/TP, Université Joseph Fourier, Grenoble.