Carl Feghali
Hello and welcome to my homepage!
I am a CNRS researcher at LIP in the MC2 team.
A short CV (in french)
Research interests: Graph Theory, Combinatorics and Algorithms.
Contact info : carl.feghali@ens-lyon.fr
Papers
- (with F. Lucke) A (simple) proof of the rna conjecture on powers of cycles, no intent to publish
- (with M. Marin, R. Watrigant) Beyond recognizing well-covered graphs, in preparation for a journal version
- (with E. Bonnet, T. Nguyen, A. Scott, P. Seymour, S. Thomassé, N. Trotignon) Graphs without a 3-connected subgraph are 4-colorable, submitted.
- (with F. Lucke, D. Paulusma and B. Ries) Matching Cuts in Graphs of High Girth and H-Free Graphs submitted.
- (with D. Chakraborty, R. Mahmoud) Kempe equivalent list colorings revisited,
Journal of Graph Theory, accepted.
- (with D. W. Cranston) Kempe classes and almost bipartite graphs,
Discrete Applied Mathematics (2024) 357 94-98.
- (with Z. Dvorak) Solution to a problem of Grunbaum on the edge density of 4-critical planar graphs,
Combinatorica (2024) 44 897-907.
- (with M. Marin) Three remarks on W_2 graphs,
Theoretical Computer Science (2024) 114403.
- (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.
- Dirac's theorem on chordal graphs implies Brooks' theorem,
Discrete Mathematics 347 (2024) 11379.
- (with R. Samal) Decomposing a triangle-free planar graph into a forest and a subcubic forest,
European Journal of Combinatorics 116 (2024) 103878.
- Another proof of Euler's circuit theorem
American Mathematical Monthly (2023).
- (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.
- (with P. Bergé, A. Busson and R. Watrigant) 1-extendability of independent sets ,
Algorithmica (2023) 1-25.
- (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.
- Kempe equivalence of 4-critical planar graphs
Journal of Graph Theory, 103 (2023) 139-147.
- (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.
- (with P. Borg) The Hilton-Spencer cycle theorems via Katona's shadow intersection theorem,
Discussiones Mathematicae Graph Theory, 43 (2023) 277-286.
- (with O. Merkel) Mixing colourings in 2K2-free graphs,
Discrete Mathematics, 345 (2022) 113108.
- (with P. Borg) The maximum sum of sizes of cross-intersecting families of subsets of a set,
Discrete Mathematics, 345 (2022), 112981.
- A note on Matching-Cut in Pt-free graphs,
Information Processing Letters, (2022) 106294.
- (with P. Borg) A short proof of Talbot's theorem for intersecting separated sets,
European Journal of Combinatorics, 101 (2022) 103471.
- (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.
- (with Z. Dvorak) A Thomassen-type method for planar graph recoloring ,
European Journal of Combinatorics, 95 (2021) 103319.
- Reconfiguring colorings of graphs with bounded maximum average degree,
Journal of Combinatorial Theory Series B 147 (2021) 133-138
- (with Z. Dvorak) An update on reconfiguring 10-colorings of planar graphs,
The Electronic Journal of Combinatorics 27 (2020) P4.51.
- (with G. Hurlbert, V. Kamat) An Erdos-Ko-Rado Theorem for unions of length 2 paths,
Discrete Mathematics, 12 (2020) 112121.
- Reconfiguring 10-colourings of planar graphs,
Graphs and Combinatorics 36 (2020) 1815-1818.
- (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.
- (with E. Eiben), Towards Cereceda's conjecture for planar graphs.,
Journal of Graph Theory, 94 (2020), 267-277.
- Intersecting families, signed sets, and injection
The Australasian Journal of Combinatorics, 76 (2020) 226-231.
- (with J. Fiala) Reconfiguration graph for vertex colourings of weakly chordal graphs,
Discrete Mathematics, 343 (2020) 111733, 6 pp.
- (with F. N. Abu-Khzam and P. Heggernes),
Partitioning a graph into degenerate subgraphs,
European Journal of Combinatorics, 23 (2020) 103015.
- (with J. Asplund and P. Charbit),
Enclosings of decompositions of complete multigraphs in 2-edge-connected r-factorizations,
Discrete Mathematics 342 (2019) 2195-2203.
- (with M. Bonamy, K. Dabrowski, M. Johnson and D. Paulusma)
Independent feedback vertex set for P5-free graphs,
Algorithmica 81 (2019) 1342-1369.
- Paths between colourings of graphs with bounded tree-width
Information Processing Letters 144 (2019) 37-38.
- (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.
- Paths between colourings of sparse graphs,
European Journal of Combinatorics 75 (2019), 169-171.
doi
- (with M. Johnson)
Enclosings of decompositions of complete multigraphs in 2-factorizations,
Journal of Combinatorial Designs 26 (2018), 205-218.
doi
- (with M. Johnson and D. Thomas)
Erdos-Ko-Rado theorems for a family of trees,
Discrete Applied Mathematics 236 (2018), 464-471.
doi
- (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
- (with M. Johnson and D. Paulusma)
Kempe equivalence of colourings of cubic graphs,
European Journal of Combinatorics 59 (2017), 1-10.
doi
- (with M. Johnson and D. Paulusma)
A reconfigurations analogue of Brooks' theorem and its consequences,
Journal of Graph Theory 83 (2016), 340-358.
doi
- (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
- (with M. Marin, R. Watrigant) Beyond recognizing well-covered graphs,
WG 2024, accepted.
- (with F. Lucke, D. Paulusma and B. Ries) Matching Cuts in Graphs of High Girth and H-Free Graphs
ISAAC 2023 Best paper award.
- (with T. Corsini, Q. Deschamps, D. Goncalves, H. Langlois, A. Talon) Partiioning into degenerate graphs in linear time,
ICGT 2022.
- (with A. Busson, P. Berge, R. Watrigant) 1-extendability of Independent sets,
IWOCA 2022.
- (with C. Crespelle, P. A. Golovach) Cyclability in graph classes,
Proceedings of ISAAC 2019.
- (with J. Fiala),
Reconfiguration graph for vertex colourings of weakly chordal graphs,
Proceedings of EuroComb 2019.
- (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.
- (with M. Bonamy, K. Dabrowski, M. Johnson and D. Paulusma),
Independent feedback vertex set for P5-free graphs,
Proceedings of ISAAC 2017, LIPIcs.
- (with M. Bonamy, K. Dabrowski, M. Johnson and D. Paulusma),
Recognizing graphs close to bipartite graphs,
Proceedings of MFCS 2017, LIPIcs.
- (with M. Johnson and D. Paulusma),
Kempe equivalence of colourings of cubic graphs,
Proceedings of EuroComb 2015, ENDM.
- (with M. Johnson and D. Paulusma),
A reconfigurations analogue of Brooks' theorem,
Proceedings of MFCS 2014, LNCS.
Talks
- 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.
Teaching
- 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
Student supervision
co-supervising Ali Momeni with Edouard Bonnet (M2, ENS Lyon, 2023)
Conference activities