Carl Feghali

activity

20232026

collaborators

3 papers

cs.DS2026

Faster Parameterized Broadcasting

Édouard Bonnet, Carl Feghali, Manolis Vasilakis

Given a connected graph $G$ and a source $s \in V (G)$ , what is the smallest number of rounds necessary for all vertices of $G$ to receive a message initially only held by $s$ , wher…

math.CO2024

Graphs without a 3-connected subgraph are 4-colorable

Édouard Bonnet, Carl Feghali, Tung Nguyen +4

In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colorable}. We show that the number 5 of colors can be replaced by 4, which is best…

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.

Faster Parameterized Broadcasting

Graphs without a 3-connected subgraph are 4-colorable

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