Lucas Pastor
Laboratoire G-SCOP, bureau B521
46 avenue Félix Viallet
38031 Grenoble Cedex 1

Telephone: +33 (0) 4 56 52 98 22

Lucas Pastor

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.



Colouring squares of claw-free graphs

(with Rémi de Joannis de Verclos and Ross J. Kang)

Is there some absolute $\varepsilon > 0$ such that for any claw-free graph $G$, the chromatic number of the square of $G$ satisfies $\chi(G^2) \le (2-\varepsilon) \omega(G)^2$, where $\omega(G)$ is the clique number of $G$? Erdős and Nešetřil asked this question for the specific case of $G$ the line graph of a simple graph and this was answered in the affirmative by Molloy and Reed. We show that the answer to the more general question is also yes, and moreover that it essentially reduces to the original question of Erdős and Nešetřil.

Disproving the normal graph conjecture

(with A. Harutyunyan and S. Thomassé)

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.


The maximum weight stable set problem in ($P_6$, bull)-free graphs

(with Frédéric Maffray)
arXiv:1602.06817 $-$ doi:10.1007/978-3-662-53536-3_8 $-$ WG 2016
Lecture Notes in Computer Science 9941 (2016), 85-96

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$).

On the choosability of claw-free perfect graphs

(with Sylvain Gravier and Frédéric Maffray)
arXiv:1506.02576 $-$ doi:10.1007/s00373-016-1732-9
Graphs and Combinatorics (2016) $-$ To appear

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

$4$-coloring ($P_6$, bull)-free graphs

(with Frédéric Maffray)
arXiv:1511.08911 $-$ doi:10.1016/j.dam.2016.03.011
Discrete Applied Mathematics (2016) $-$ To appear

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.



Upcoming event:
Where you might have seen me:
Research visits:
Research projects:
  • I'm a member of the ANR project STINT.
Reviewer for the following journals and conferences:
Science popularization: