Carl Feghali

activity

20142024

most citedNP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph

4 citations · 4 across the 3 of their papers we have counts for

collaborators

Showing math.COShow all

2 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

Solution to a problem of Grünbaum on the edge density of $4$ -critical planar graphs

Zdeněk Dvořák, Carl Feghali

We show that $lim sup ∣ E (G) ∣/∣ V (G) ∣ = 2.5$ over all $4$ -critical planar graphs $G$ , answering a question of Grünbaum from 1988.

Beyond recognizing well-covered graphs

Solution to a problem of Grünbaum on the edge density of 4-critical planar graphs

Solution to a problem of Grünbaum on the edge density of $4$ -critical planar graphs