Lucas Pastor
Bureau D105, LIMOS (bât. ISIMA)
Campus des Cézeaux
1 rue de la Chebarde
63170 Aubière
France
Telephone: +33 (0) 4 73 40 53 59
Mail: firstname.lastname@uca.fr

Lucas Pastor

Since the 1st of September 2018 I am associate professor at the Institut d'Informatique of Université Clermont Auvergne, LIMOS.
From December 2017 to August 2018 I was a postdoc researcher at University of Warsaw, Faculty of Mathematics, Informatics and Mechanics, under the supervision of Marcin Pilipczuk. I was supported by his ERC Starting Grant CUTACOMBS. I did my PhD from October 2014 to October 2017 in the Combinatorial Optimization team of G-SCOP. My advisors were Frédéric Maffray (G-SCOP) and Sylvain Gravier (Institut Fourier). Here you can find my PhD manuscript and my PhD defense slides.

I'm working on graph theory. I am interested in about everything in this field even though my main works are about graph coloring, maximum weight stable set and structural graph theory.

I am currently co-supervising one PhD student: Caroline Brosse (2019- ...), co-supervised with Aurélie Lagoutte and Vincent Limouzy.

Publications

Submitted

Efficient enumeration of maximal split subgraphs and sub-cographs and related classes


with Caroline Brosse, Aurélie Lagoutte, Vincent Limouzy, Arnaud Mary
arXiv:2007.01031

In this paper, we are interested in algorithms that take in input an arbitrary graph $G$, and that enumerate in output all the (inclusion-wise) maximal "subgraphs" of $G$ which fulfil a given property $\Pi$. All over this paper, we study several different properties $\Pi$, and the notion of subgraph under consideration (induced or not) will vary from a result to another. More precisely, we present efficient algorithms to list all maximal split subgraphs, sub-cographs and some subclasses of cographs of a given input graph. All the algorithms presented here run in polynomial delay, and moreover for split graphs it only requires polynomial space. In order to develop an algorithm for maximal split (edge-)subgraphs, we establish a bijection between the maximal split subgraphs and the maximal independent sets of an auxiliary graph. For cographs and some subclasses , the algorithms rely on a framework recently introduced by Conte $\&$ Uno called Proximity Search. Finally we consider the extension problem, which consists in deciding if there exists a maximal induced subgraph satisfying a property $\Pi$ that contains a set of prescribed vertices and that avoids another set of vertices. We show that this problem is NP-complete for every "interesting" hereditary property $\Pi$. We extend the hardness result to some specific edge version of the extension problem.

2020

Revisiting a theorem by Folkman on graph colouring


with Marthe Bonamy, Pierre Charbit, Oscar Defrain, Gwenaël Joret, Aurélie Lagoutte, Vincent Limouzy, Jean-Sébastien Sereni
arXiv:1709.07712 $-$ https://doi.org/10.37236/8899
The Electronic Journal of Combinatorics 27:1 (2020), P1.56

We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most 2 plus the maximum over all subgraphs of the difference between half the number of vertices and the independence number.


Disproving the normal graph conjecture


with Ararat Harutyunyan and Stéphan Thomassé
arXiv:1508.05487 $-$ doi.org/10.1016/j.jctb.2020.04.001
Journal of Combinatorial Theory, Series B $-$ In Press.

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.

2019

Polynomial Cases for the Vertex Coloring Problem


with T. Karthick and Frédéric Maffray
arXiv:1709.07712 $-$ doi.org/10.1007/s00453-018-0457-y
Algorithmica 81 (2019), 1053-1074.

The computational complexity of the Vertex Coloring problem is known for all hereditary classes of graphs defined by forbidding two connected five-vertex induced subgraphs, except for seven cases. We prove the polynomial-time solvability of four of these problems: for ($P_5$, dart)-free graphs, ($P_5$, banner)-free graphs, ($P_5$, bull)-free graphs, and (fork, bull)-free graphs.

2018

Maximum Weight Stable Set in ($P_7$, bull)-free graphs and ($S_{1,2,3}$, bull)-free graphs


with Frédéric Maffray
arXiv:1611.09663 $-$ doi.org/10.1016/j.disc.2017.10.004
Discrete Mathematics 341:5 (2018), 1449-1458

We give a polynomial time algorithm that finds the maximum weight stable set in a graph that does not contain an induced path on seven vertices or a bull (the graph with vertices $a$, $b$, $c$, $d$, $e$ and edges $ab$, $bc$, $cd$, $be$, $ce$). With the same arguments with also give a polynomial algorithm for any graph that does not contain $S_{1,2,3}$ or a bull.


Decomposition techniques applied to the Clique-Stable set Separation problem


with Nicolas Bousquet, Aurélie Lagoutte and Frédéric Maffray
arXiv:1703.07106 $-$ doi.org/10.1016/j.disc.2017.10.014
Discrete Mathematics, 341:5 (2018) 1492-1501.

In a graph, a Clique-Stable Set separator (CS-separator) is a family $\mathcal{C}$ of cuts (bipartitions of the vertex set) such that for every clique $K$ and every stable set $S$ with $K \cap S = \emptyset$, there exists a cut $( W,W')$ in $\mathcal{C}$ such that $K \subseteq W$ and $S \subseteq W'$. Starting from a question concerning extended formulations of the Stable Set polytope and a related complexity communication problem, Yannakakis [17] asked in 1991 the following questions: does every graph admit a polynomial-size CS-separator? If not, does every perfect graph do? Several positive and negative results related to this question were given recently. Here we show how graph decomposition can be used to prove that a class of graphs admits a polynomial CS-separator. We apply this method to apple-free graphs and cap-free graphs.

2017

Colouring squares of claw-free graphs


with Rémi de Joannis de Verclos and Ross J. Kang
arXiv:1609.08645 $-$ doi.org/10.4153/CJM-2017-029-9
Canadian Journal of Mathematics 61 (2017), 663-669

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.


$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 231 (2017), 198-210

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.

2016

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 32:6 (2016), 2393-2413

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


Talks

  • A Tribute to Frédéric Maffray, G-SCOP (Grenoble, France) September 2 2019. A PhD thesis I would like to do again. Slides.

  • Journées Combinatoire Graphes Algo, (ENS Lyon, France) December 11 2018. Anciens et nouveaux résultats de coloration. Slides.

  • Seminar of Department of Discrete Mathematics, University of Poznań (Poznań, Poland) April 17 2018. Colouring squares of claw-free graphs. Slides.

  • Seminar of Algorithms Group, University of Warsaw Faculty of Mathematics, Informatics and Mechanics (Warsaw, Poland) February 8 2018. Disproving the normal graph conjecture. Slides.

  • Présentation JGA, LaBRI (Bordeaux, France) November 15 2017. Coloring squares of claw-free graphs. Slides.

  • Séminaire Graphes@Lyon, LIRIS (Lyon, France) November 10 2017. Coloring squares of claw-free graphs. Slides.

  • Présentation AGIR, UFR IM2AG (Grenoble, France) November 24 2016. Coloration dans les graphes structurés. Slides.

  • Présentation JGA, Université Paris-Dauphine (Paris, France) November 16 2016. Indépendant de poids maximum dans les ($P_6$, bull)-free. Slides.

  • Séminaire LIMOS, (Clermont-Ferrand, France) October 12 2016. Disproving the normal graph conjecture. Slides.

  • Séminaire LaBRI, équipe Graphes et Optimisation (Bordeaux, France) March 4 2016. The coloring problem in graphs with structural restrictions. Slides.

  • Séminaire G-SCOP (Grenoble, France) October 1st 2015. Coloration par liste dans les graphes parfaits sans griffe. Slides.

  • Présentation JGA, (Orléans, France) November 4 2015. Coloration par liste dans les graphes parfaits sans griffe. Slides.

  • Third STINT meeting (Autrans, France) June 30 2015. List-coloring in claw-free perfect graphs. Slides.

  • Présentation Journées G-SCOP, (Loriol, France) June 4 2015. Coloration par liste. Slides.

Teaching

  • 2018-present Programmation C, L1, CM/TD/TP - Bases de données, L2, CM/TD/TP - Bases de données et Web, L3, CM/TD/TP, Université Clermont Auvergne.

  • 2016-2017 Modélisation des structures informatiques (Modelisation of computer science structures), L2, TD/TP, Université Joseph Fourier, Grenoble.

  • 2016-2017 Base de données et Bases de Connaissances, L3, TD/TP, UFR Informatique, Mathématiques, Mathématiques Appliquées, Grenoble.

  • 2015-2016 Introduction à UNIX et à la programmation en langage C (introduction to UNIX and C programming), L1, TD/TP, Université Joseph Fourier, Grenoble.

  • 2014-2015 Informatique instrumentale et multimédia (introduction to algorithm, programming and HTML/CSS), L1, TD/TP, Université Joseph Fourier, Grenoble.

Other

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:
  • ESA (European Symposium on Algorithms).
  • Graphs and Combinatorics.
  • Information Processing Letters.
  • Journal of Combinatorial Theory, Series B.
  • Journal of Graph Theory.
  • RAIRO - Operations Research.
  • WG (International Workshop on Graph-Theoretic Concepts in Computer Science).
Science popularization:

Links

My co-authors:

Last modifications: 07/07/2020