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 math.COShow all

29 papers · 1 filter

math.CO2026

Greedy Coloring and Simple Exponential Strengthenings of Brooks-Type Theorems

Alex Crane, Carl Feghali, Felicia Lucke +2

Brooks' Theorem is a foundational result in graph coloring: if a graph is connected, not a clique, and has maximum degree $Δ \geq 3$ , then it admits a proper $Δ$ -coloring. In this p…

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.CO2023

Kempe Classes and Almost Bipartite Graphs

Daniel W. Cranston, Carl Feghali

Let $G$ be a graph and $k$ be a positive integer, and let $K c (G, k)$ denote the number of Kempe equivalence classes for the $k$ -colorings of $G$ . In 2006, Mohar noted that $Kc(G, k…

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…

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…

math.CO2021

A note on Matching-Cut in $P_{t}$ -free Graphs

Carl Feghali

A matching-cut of a graph is an edge cut that is a matching. The problem Matching-Cut is that of recognizing graphs with a matching-cut and is NP-complete, even if the graph belong…

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 $…

math.CO2021

Kempe equivalence of $4$ -critical planar graphs

Carl Feghali

Answering a question of Mohar from 2007, we show that for every $4$ -critical planar graph, its set of $4$ -colorings is a Kempe class.

math.CO2020★ 2 cited

Decomposing a triangle-free planar graph into a forest and a subcubic forest

Carl Feghali, Robert Šámal

We strengthen a result of Dross, Montassier and Pinlou (2017) that the vertex set of every triangle-free planar graph can be decomposed into a set that induces a forest and a set t…

math.CO2020

A simple proof of Talbot's theorem for intersecting separated sets

Peter Borg, Carl Feghali

A subset $A$ of $[n] = {1, \dots, n}$ is $k$ -separated if, when the elements of $[n]$ are considered on a circle, between any two elements of $A$ there are at least $k$ elements…

math.CO2020

A Thomassen-type method for planar graph recoloring

Zdeněk Dvořák, Carl Feghali

The reconfiguration graph $R_{k} (G)$ for the $k$ -colorings of a graph $G$ has as vertices all possible $k$ -colorings of $G$ and two colorings are adjacent if they differ in the color…

math.CO2020

An update on reconfiguring $10$ -colorings of planar graphs

Zdeněk Dvořák, Carl Feghali

The reconfiguration graph $R_{k} (G)$ for the $k$ -colorings of a graph $G$ has as vertex set the set of all possible proper $k$ -colorings of $G$ and two colorings are adjacent if they…

math.CO2019

Intersecting families, signed sets, and injection

Carl Feghali

Let $k, r, n \geq 1$ be integers, and let $§_{n, k, r}$ be the family of $r$ -signed $k$ -sets on $[n] = {1, \dots, n}$ given by $$ \mathcal{S}_{n, k, r} = \Big\{\{(x_1, a_1), \dot…

math.CO2019

An Erdős-Ko-Rado Theorem for unions of length 2 paths

Carl Feghali, Glenn Hurlbert, Vikram Kamat

A family of sets is intersecting if any two sets in the family intersect. Given a graph $G$ and an integer $r \geq 1$ , let $I^{(r)} (G)$ denote the family of independent se…

math.CO2019★ 5 cited

On the Hilton-Spencer intersection theorems for unions of cycles

Peter Borg, Carl Feghali

A family $A$ of sets is said to be intersecting if every two sets in $A$ intersect. An intersecting family is said to be \emph{trivial} it its sets have a commo…

math.CO2019

Reconfiguring colorings of graphs with bounded maximum average degree

Carl Feghali

The reconfiguration graph $R_{k} (G)$ for the $k$ -colorings of a graph $G$ has as vertex set the set of all possible $k$ -colorings of $G$ and two colorings are adjacent if they differ…

math.CO2019

Reconfiguring 10-colourings of planar graphs

Carl Feghali

Let $k \geq 1$ be an integer. The reconfiguration graph $R_{k} (G)$ of the $k$ -colourings of a graph~ $G$ has as vertex set the set of all possible $k$ -colourings of $G$ and two colour…

math.CO2019

Reconfiguration Graph for Vertex Colourings of Weakly Chordal Graphs

Carl Feghali, Jiří Fiala

The reconfiguration graph $R_{k} (G)$ of the $k$ -colourings of a graph $G$ contains as its vertex set the $k$ -colourings of $G$ and two colourings are joined by an edge if they differ…

Greedy Coloring and Simple Exponential Strengthenings of Brooks-Type Theorems

Beyond recognizing well-covered graphs

Three remarks on W2​ graphs

Dirac's theorem on chordal graphs implies Brooks' theorem

Kempe Classes and Almost Bipartite Graphs

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

Kempe Equivalent List Colorings Revisited

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

Partitioning into degenerate graphs in linear time

Strengthening a theorem of Meyniel

A note on Matching-Cut in Pt​-free Graphs

Mixing colourings in 2K2​-free graphs

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

Kempe equivalence of 4-critical planar graphs

Decomposing a triangle-free planar graph into a forest and a subcubic forest

A simple proof of Talbot's theorem for intersecting separated sets

A Thomassen-type method for planar graph recoloring

An update on reconfiguring 10-colorings of planar graphs

Intersecting families, signed sets, and injection

An Erdős-Ko-Rado Theorem for unions of length 2 paths

On the Hilton-Spencer intersection theorems for unions of cycles

Reconfiguring colorings of graphs with bounded maximum average degree

Reconfiguring 10-colourings of planar graphs

Reconfiguration Graph for Vertex Colourings of Weakly Chordal Graphs

Three remarks on $W_{2}$ graphs

A note on Matching-Cut in $P_{t}$ -free Graphs

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

Kempe equivalence of $4$ -critical planar graphs

An update on reconfiguring $10$ -colorings of planar graphs