Carl Feghali

I am a CNRS researcher at LIP in the MC2 team.

A short CV (in french)

Research interests: Graph Theory, Combinatorics and Algorithms.

1. (with F. Lucke) A (simple) proof of the rna conjecture on powers of cycles, no intent to publish
2. (with M. Marin, R. Watrigant) Beyond recognizing well-covered graphs, in preparation for a journal version
3. (with E. Bonnet, T. Nguyen, A. Scott, P. Seymour, S. Thomassé, N. Trotignon) Graphs without a 3-connected subgraph are 4-colorable, submitted.
4. (with F. Lucke, D. Paulusma and B. Ries) Matching Cuts in Graphs of High Girth and H-Free Graphs submitted.
5. (with D. Chakraborty, R. Mahmoud) Kempe equivalent list colorings revisited,
   Journal of Graph Theory, accepted.
6. (with D. W. Cranston) Kempe classes and almost bipartite graphs,
   Discrete Applied Mathematics (2024) 357 94-98.
7. (with Z. Dvorak) Solution to a problem of Grunbaum on the edge density of 4-critical planar graphs,
   Combinatorica (2024) 44 897-907.
8. (with M. Marin) Three remarks on W_2 graphs,
   Theoretical Computer Science (2024) 114403.
9. (with P. Borg and R. Pellerin) Solution to a problem of Katona on counting cliques for weighted graphs,
   Discrete Applied Mathematics 345 (2024) 147-155.
10. Dirac's theorem on chordal graphs implies Brooks' theorem,
    Discrete Mathematics 347 (2024) 11379.
11. (with R. Samal) Decomposing a triangle-free planar graph into a forest and a subcubic forest,
    European Journal of Combinatorics 116 (2024) 103878.
12. Another proof of Euler's circuit theorem
    American Mathematical Monthly (2023).
13. (with T. Corsini, Q. Deschamps, D. Goncalves, H. Langlois, A. Talon) Partitioning into degenerate graphs in linear time ,
    European Journal of Combinatorics 114 (2023) 103771.
14. (with P. Bergé, A. Busson and R. Watrigant) 1-extendability of independent sets ,
    Algorithmica (2023) 1-25.
15. (with V. Bartier, N. Bousquet, M. Heinrich, B. Moore and T. Pierron) Recolouring planar graphs of girth at least five,
    SIAM Journal on Discrete Mathematics, 37 (2023), 332-350.
16. Kempe equivalence of 4-critical planar graphs
    Journal of Graph Theory, 103 (2023) 139-147.
17. (with Q. Deschamps, F. Kardos, C. Legrand-Duschene and T. Pierron) Strengthening a theorem of Meyniel,
    SIAM Journal on Discrete Mathematics, 37 (2023) 604-611.
18. (with P. Borg) The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem,
    Discussiones Mathematicae Graph Theory, 43 (2023) 277-286.
19. (with O. Merkel) Mixing colourings in 2K2-free graphs,
    Discrete Mathematics, 345 (2022) 113108.
20. (with P. Borg) The maximum sum of sizes of cross-intersecting families of subsets of a set,
    Discrete Mathematics, 345 (2022), 112981.
21. A note on Matching-Cut in Pt-free graphs,
    Information Processing Letters, (2022) 106294.
22. (with P. Borg) A short proof of Talbot's theorem for intersecting separated sets,
    European Journal of Combinatorics, 101 (2022) 103471.
23. (with M. Bonamy, K. Dabrowski, M. Johnson and D. Paulusma) Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ,
    Journal of Graph Theory, 98 (2021), no. 1, 81-109.
24. (with Z. Dvorak) A Thomassen-type method for planar graph recoloring ,
    European Journal of Combinatorics, 95 (2021) 103319.
25. Reconfiguring colorings of graphs with bounded maximum average degree,
    Journal of Combinatorial Theory Series B 147 (2021) 133-138
26. (with Z. Dvorak) An update on reconfiguring 10-colorings of planar graphs,
    The Electronic Journal of Combinatorics 27 (2020) P4.51.
27. (with G. Hurlbert, V. Kamat) An Erdos-Ko-Rado Theorem for unions of length 2 paths,
    Discrete Mathematics, 12 (2020) 112121.
28. Reconfiguring 10-colourings of planar graphs,
    Graphs and Combinatorics 36 (2020) 1815-1818.
29. (with K. Dabrowski, M. Johnson, G. Paesani, D. Paulusma, P. Rzazewski) On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest,
    Algorithmica 82 (2020) 2841-2866.
30. (with E. Eiben), Towards Cereceda's conjecture for planar graphs.,
    Journal of Graph Theory, 94 (2020), 267-277.
31. Intersecting families, signed sets, and injection
    The Australasian Journal of Combinatorics, 76 (2020) 226-231.
32. (with J. Fiala) Reconfiguration graph for vertex colourings of weakly chordal graphs,
    Discrete Mathematics, 343 (2020) 111733, 6 pp.
33. (with F. N. Abu-Khzam and P. Heggernes), Partitioning a graph into degenerate subgraphs,
    European Journal of Combinatorics, 23 (2020) 103015.
34. (with J. Asplund and P. Charbit), Enclosings of decompositions of complete multigraphs in 2-edge-connected r-factorizations,
    Discrete Mathematics 342 (2019) 2195-2203.
35. (with M. Bonamy, K. Dabrowski, M. Johnson and D. Paulusma) Independent feedback vertex set for P5-free graphs,
    Algorithmica 81 (2019) 1342-1369.
36. Paths between colourings of graphs with bounded tree-width
    Information Processing Letters 144 (2019) 37-38.
37. (with M. Bonamy, N. Bousquet and M. Johnson) On a conjecture of Mohar concerning Kempe equivalence of regular graphs,
    Journal of Combinatorial Theory Series B 135 (2019) 179-199.
38. Paths between colourings of sparse graphs,
    European Journal of Combinatorics 75 (2019), 169-171. doi
39. (with M. Johnson) Enclosings of decompositions of complete multigraphs in 2-factorizations,
    Journal of Combinatorial Designs 26 (2018), 205-218. doi
40. (with M. Johnson and D. Thomas) Erdos-Ko-Rado theorems for a family of trees,
    Discrete Applied Mathematics 236 (2018), 464-471. doi
41. (with M. Bonamy, K. Dabrowski, M. Johnson and D. Paulusma) Independent feedback vertex sets for graphs of bounded diameter,
    Information Processing Letters 131 (2018), 26-32.doi
42. (with M. Johnson and D. Paulusma) Kempe equivalence of colourings of cubic graphs,
    European Journal of Combinatorics 59 (2017), 1-10. doi
43. (with M. Johnson and D. Paulusma) A reconfigurations analogue of Brooks' theorem and its consequences,
    Journal of Graph Theory 83 (2016), 340-358. doi
44. (with F. N. Abu-Khzam and H. Muller) Partitioning a graph into disjoint cliques and a triangle-free graph,
    Discrete Applied Mathematics 190-191 (2015), 1-12. doi

1. (with M. Marin, R. Watrigant) Beyond recognizing well-covered graphs,
   WG 2024, accepted.
2. (with F. Lucke, D. Paulusma and B. Ries) Matching Cuts in Graphs of High Girth and H-Free Graphs
   ISAAC 2023 Best paper award.
3. (with T. Corsini, Q. Deschamps, D. Goncalves, H. Langlois, A. Talon) Partiioning into degenerate graphs in linear time,
   ICGT 2022.
4. (with A. Busson, P. Berge, R. Watrigant) 1-extendability of Independent sets,
   IWOCA 2022.
5. (with C. Crespelle, P. A. Golovach) Cyclability in graph classes,
   Proceedings of ISAAC 2019.
6. (with J. Fiala),
   Reconfiguration graph for vertex colourings of weakly chordal graphs,
   Proceedings of EuroComb 2019.
7. (with M. Johnson, G. Paesani, D. Paulusma),
   On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest,
   Proceedings of FCT 2019.
8. (with M. Bonamy, K. Dabrowski, M. Johnson and D. Paulusma),
   Independent feedback vertex set for P5-free graphs,
   Proceedings of ISAAC 2017, LIPIcs.

9. (with M. Bonamy, K. Dabrowski, M. Johnson and D. Paulusma),
   Recognizing graphs close to bipartite graphs,
   Proceedings of MFCS 2017, LIPIcs.

10. (with M. Johnson and D. Paulusma),
    Kempe equivalence of colourings of cubic graphs,
    Proceedings of EuroComb 2015, ENDM.

11. (with M. Johnson and D. Paulusma),
    A reconfigurations analogue of Brooks' theorem,
    Proceedings of MFCS 2014, LNCS.

• Graphs without a k-connected subgraph, Grenoble INP, 2024
• Lower bound on the density of 4-critical planar graphs, Lyon graph meetings, 2023
• Around the matching-cut problem, Journées Graphes et Algorithmes (JGA) 2022
• Graph theory meets extremal set theory, Illinois State University, 2022.
• Kempe equivalence of 4-critical planar graphs, Journées Graphes et Algorithmes (JGA) 2021.
• Colorings and decompositions of planar graphs, CANADAM 2021.
• Colorings and decompositions of planar graphs, LaBRi, Université de Bordeaux, June 2021.
• Colorings and decompositions of planar graphs, Virginia Commonwealth University, March 2021.
• Planar graph recoloring: two proofs, 55th Czech-Slovak Conference on Graph Theory 2020, Brno, Czech Republic, August 2020
• Revisiting a theorem of Talbot, Midsummer Combinatorial workshop, Prague, Czech Republic, August 2020.
• Graph theory meets extremal set theory, Charles University of Prague, Czech Republic, November 2019.
• Kempe equivalence of regular graphs, Bogazici University, 2019
• Kempe equivalence of regular graphs, University of Malta, June 2019.
• Reconfiguring colourings of graphs with bounded maximum average degree, Combinatorial Reconfiguration Workshop, France 2019.
• Erdos--Ko--Rado theorems for a family of trees, Alfred Renyi Institute of Mathematics, Hungary, April 2018.
• Partitioning a graph into degenerate subgraphs, Algorithms group, The University of Bergen, Norway, January 2018.
• Problems and Results in Kempe equivalence of colourings, Society of Industrial and Applied Mathematics, USA, June 2016.
• A reconfigurations analogue of Brooks' theorem, British Conference on Theoretical Computer Science, UK, March 2015.
• A reconfigurations analogue of Brooks' theorem, Mathematical Foundations of Computer Science, Hungary, July 2014.

• TP LIFASR3 (2021) - Université Claude Bernard Lyon
• TD Combinatorics and graph theory II (2020) - Charles University in Prague
• TD Theory of Computation (2014-2015) - Durham University
• TD Mathematics for Computer Science (2014-2015) - Durham University

co-supervising Ali Momeni with Edouard Bonnet (M2, ENS Lyon, 2023)

WG 2023, PC member