Carl Feghali

activity

20172025

collaborators

Showing math.COShow all

18 papers · 1 filter

math.CO2024

Beyond recognizing well-covered graphs

Carl Feghali, Malory Marin, Rémi Watrigant

We prove a number of results related to the computational complexity of recognizing well-covered graphs. Let $k$ and $s$ be positive integers and let $G$ be a graph. Then $G$ is sa…

math.CO2023

Three remarks on $W_{2}$ graphs

Carl Feghali, Malory Marin

Let $k \geq 1$ . A graph $G$ is $W_{k}$ if for any $k$ pairwise disjoint independent vertex subsets $A_{1}, \dots, A_{k}$ in $G$ , there exist $k$ pairwise disjoint maximum indepe…

math.CO2023

Dirac's theorem on chordal graphs implies Brooks' theorem

Carl Feghali

We give yet another proof of the list-color version of Brooks' theorem that is due, independently, to Vizing and to Erdős, Rubin and Taylor, via a famous theorem of Dirac on chorda…

math.CO2022

Strengthening a theorem of Meyniel

Quentin Deschamps, Carl Feghali, František Kardoš +2

For an integer $k \geq 1$ and a graph $G$ , let $K_{k} (G)$ be the graph that has vertex set all proper $k$ -colorings of $G$ , and an edge between two vertices $α$ and~ $β$ whe…

math.CO2021

Mixing colourings in $2 K_{2}$ -free graphs

Carl Feghali, Owen Merkel

The reconfiguration graph for the $k$ -colourings of a graph $G$ , denoted $R_{k} (G)$ , is the graph whose vertices are the $k$ -colourings of $G$ and two colourings are joined by an e…

math.CO2021

The maximum sum of sizes of cross-intersecting families of subsets of a set

Peter Borg, Carl Feghali

A set of sets is called a family. Two families $A$ and $B$ of sets are said to be cross-intersecting if each member of $A$ intersects each member of $…