Reem Mahmoud

activity

20212026

most citedKempe Equivalent List Colorings

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

collaborators

11 papers

math.CO2026

Obstructions for Minor-Closed Classes of limiting Densities Below 3/2

Antonios Kominatos, Reem Mahmoud, Dimitrios M. Thilikos

Given a graph class $G$ , the limiting density of $G$ is defined as $δ (G) = lim_{n \to \infty} ex (G, n) / n$ where $\mathsf{ex}(\mathcal{G…

math.CO2025

Equitably Coloring Planar and Outerplanar Graphs

Daniel W. Cranston, Reem Mahmoud

A proper $s$ -coloring of an $n$ -vertex graph is \emph{equitable} if every color class has size $⌊ n / s ⌋$ or $⌈ n / s ⌉$ . A necessary condition to have an equita…

q-bio.GN2024

Pairwise Rearrangement is Fixed-Parameter Tractable in the Single Cut-and-Join Model

Lora Bailey, Heather Smith Blake, Garner Cochran +6

Genome rearrangement is a common model for molecular evolution. In this paper, we consider the Pairwise Rearrangement problem, which takes as input two genomes and asks for the num…

math.CO2023★ 1 cited

Equitable Coloring in 1-Planar Graphs

Daniel Cranston, Reem Mahmoud

For every $r \geq 13$ , we show every 1-planar graph $G$ with $Δ (G) \leq r$ has an equitable $r$ -coloring.

cs.CC2023

Minimum Separator Reconfiguration

Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud +4

We study the problem of reconfiguring one minimum $s$ - $t$ -separator $A$ into another minimum $s$ - $t$ -separator $B$ in some $n$ -vertex graph $G$ containing two non-adjacent vertices…

q-bio.GN2023★ 1 cited

Complexity and Enumeration in Models of Genome Rearrangement

Lora Bailey, Heather Smith Blake, Garner Cochran +8

In this paper, we examine the computational complexity of enumeration in certain genome rearrangement models. We first show that the Pairwise Rearrangement problem in the Single Cu…

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

Reconstruction and Edge Reconstruction of Triangle-free Graphs

Alexander Clifton, Xiaonan Liu, Reem Mahmoud +1

The Reconstruction Conjecture due to Kelly and Ulam states that every graph with at least 3 vertices is uniquely determined by its multiset of subgraphs ${G - v : v \in V (G)}$ . Let $…

math.CO2022★ 3 cited

5-Coloring Reconfiguration of Planar Graphs with No Short Odd Cycles

Daniel W. Cranston, Reem Mahmoud

The coloring reconfiguration graph $C_{k} (G)$ has as its vertex set all the proper $k$ -colorings of $G$ , and two vertices in $C_{k} (G)$ are adjacent if their corres…

math.CO2021★ 4 cited

Kempe Equivalent List Colorings

Daniel W. Cranston, Reem Mahmoud

An $α, β$ -Kempe swap in a properly colored graph interchanges the colors on some component of the subgraph induced by colors $α$ and $β$ . Two $k$ -colorings of a graph are $k$ -Kempe…

math.CO2021

In Most 6-regular Toroidal Graphs All 5-colorings are Kempe Equivalent

Daniel W. Cranston, Reem Mahmoud

A Kempe swap in a proper coloring interchanges the colors on some maximal connected 2-colored subgraph. Two $k$ -colorings are $k$ -equivalent if we can transform one into the other…