Carl Feghali

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

I obtained my Ph.D from Durham University in 2017 under the supervision of Matthew Johnson and Daniel Paulusma. Before coming to Lyon, I was a postdoc at Charles University in Prague (2019-2021) working with Zdeněk Dvořák and Robert Šámal, the University of Bergen (2017-2019) and Université Paris Diderot (2016-2017) working with Pierre Charbit.

My research interests include colorings and decompositions of graphs, combinatorial reconfiguration, theoretical computer science and extremal set theory.

Contact info :


Co-authors Faisal N. Abu-Khzam John Asplund Valentin Bartier Marthe Bonamy Peter Borg Nicolas Bousquet Pierre Charbit Christophe Crespelle Konrad Dabrowski Zdenek Dvorak Eduard Eiben Jiri Fiala Petr Golovach Pinar Heggernes Marc Heinrich Glenn Hurlbert Matthew Johnson Vikram Kamat Owen Merkel Benjamin Moore Haiko Muller Giacomo Paesani Daniel Paulusma Théo Pierron Pawel Rzazewski Robert Samal Daniel Thomas

  1. (with T. Corsini, Q. Deschamps, D. Goncalves, H. Langlois, A. Talon) Partiioning into degenerate graphs in linear time , manuscript.
  2. (with P. Bergé, A. Busson and R. Watrigant) 1-extendability of independent sets , manuscript.
  3. (with Q. Deschamps, F. Kardos, C. Legrand-Duschene and T. Pierron) Strengthening a theorem of Meyniel, submitted.
  4. (with V. Bartier, N. Bousquet, M. Heinrich, B. Moore and T. Pierron) Recolouring planar graphs of girth at least five, submitted.
  5. (with O. Merkel) Mixing colourings in 2K2-free graphs, submitted.
  6. Kempe equivalence of 4-critical planar graphs
    Journal of Graph Theory, under revision.
  7. (with R. Samal) Decomposing a triangle-free planar graph into a forest and a subcubic forest,
    European Journal of Combinatorics, under revision.
  8. A note on Matching-Cut in Pt-free graphs,
    Information Processing Letters, under revision.
  9. (with P. Borg) The maximum sum of sizes of cross-intersecting families of subsets of a set,
    Discrete Mathematics, to appear.
  10. (with P. Borg) A short proof of Talbot's theorem for intersecting separated sets,
    European Journal of Combinatorics, 101 (2022) 103471.
  11. (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.
  12. (with Z. Dvorak) A Thomassen-type method for planar graph recoloring ,
    European Journal of Combinatorics, 95 (2021) 103319.
  13. Reconfiguring colorings of graphs with bounded maximum average degree,
    Journal of Combinatorial Theory Series B 147 (2021) 133-138
  14. (with Z. Dvorak) An update on reconfiguring 10-colorings of planar graphs,
    The Electronic Journal of Combinatorics 27 (2020) P4.51.
  15. (with P. Borg) The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem,
    Discussiones Mathematicae Graph Theory, in press.
  16. (with G. Hurlbert, V. Kamat) An Erdos-Ko-Rado Theorem for unions of length 2 paths,
    Discrete Mathematics, 12 (2020) 112121.
  17. Reconfiguring 10-colourings of planar graphs,
    Graphs and Combinatorics 36 (2020) 1815-1818.
  18. (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.
  19. (with E. Eiben), Towards Cereceda's conjecture for planar graphs.,
    Journal of Graph Theory, 94 (2020), 267-277.
  20. Intersecting families, signed sets, and injection
    The Australasian Journal of Combinatorics, 76 (2020) 226-231.
  21. (with J. Fiala) Reconfiguration graph for vertex colourings of weakly chordal graphs,
    Discrete Mathematics, 343 (2020) 111733, 6 pp.
  22. (with F. N. Abu-Khzam and P. Heggernes), Partitioning a graph into degenerate subgraphs,
    European Journal of Combinatorics, 23 (2020) 103015.
  23. (with J. Asplund and P. Charbit), Enclosings of decompositions of complete multigraphs in 2-edge-connected r-factorizations,
    Discrete Mathematics 342 (2019) 2195-2203.
  24. (with M. Bonamy, K. Dabrowski, M. Johnson and D. Paulusma) Independent feedback vertex set for P5-free graphs,
    Algorithmica 81 (2019) 1342-1369.
  25. Paths between colourings of graphs with bounded tree-width
    Information Processing Letters 144 (2019) 37-38.
  26. (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.
  27. Paths between colourings of sparse graphs,
    European Journal of Combinatorics 75 (2019), 169-171. doi
  28. (with M. Johnson) Enclosings of decompositions of complete multigraphs in 2-factorizations,
    Journal of Combinatorial Designs 26 (2018), 205-218. doi
  29. (with M. Johnson and D. Thomas) Erdos-Ko-Rado theorems for a family of trees,
    Discrete Applied Mathematics 236 (2018), 464-471. doi
  30. (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
  31. (with M. Johnson and D. Paulusma) A reconfigurations analogue of Brooks' theorem and its consequences,
    Journal of Graph Theory 83 (2016), 340-358. doi
  32. (with M. Johnson and D. Paulusma) Kempe equivalence of colourings of cubic graphs,
    European Journal of Combinatorics 59 (2017), 1-10. doi
  33. (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

Conference proceedings