Carl Feghali

activity

20142026

most citedOn the Hilton-Spencer intersection theorems for unions of cycles

5 citations · 17 across the 27 of their papers we have counts for

collaborators

Showing 2022Show all

6 papers · 1 filter

math.CO2022★ 2 cited

Matching Cuts in Graphs of High Girth and H-Free Graphs

Carl Feghali, Felicia Lucke, Daniel Paulusma +1

The (Perfect) Matching Cut problem is to decide if a connected graph has a (perfect) matching that is also an edge cut. The Disconnected Perfect Matching problem is to decide if a…

math.CO2022

Kempe Equivalent List Colorings Revisited

Dibyayan Chakraborty, Carl Feghali, Reem Mahmoud

A \emph{Kempe chain} on colors $a$ and $b$ is a component of the subgraph induced by colors $a$ and $b$ . A \emph{Kempe change} is the operation of interchanging the colors of some…

math.CO2022

Solution to a problem of Katona on counting cliques of weighted graphs

Peter Borg, Carl Feghali, Rémi Pellerin

A subset $I$ of the vertex set $V (G)$ of a graph $G$ is called a $k$ -clique independent set of $G$ if no $k$ vertices in $I$ form a $k$ -clique of $G$ . An independent set is a $2$ -c…

cs.CC2022

1-Extendability of independent sets

Pierre Bergé, Anthony Busson, Carl Feghali +1

In the 70s, Berge introduced 1-extendable graphs (also called B-graphs), which are graphs where every vertex belongs to a maximum independent set. Motivated by an application in th…

math.CO2022

Partitioning into degenerate graphs in linear time

Timothée Corsini, Quentin Deschamps, Carl Feghali +3

Let $G$ be a connected graph with maximum degree $Δ \geq 3$ distinct from $K_{Δ + 1}$ . Generalizing Brooks' Theorem, Borodin, Kostochka and Toft proved that if $p_{1}, \dots, p_{s}$ are…

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…