S. Jahanbekam

activity

20162021

collaborators

6 papers

math.CO2021

3-colorability of graphs with minimum degree at least 6

Nicholas Crawford, Sogol Jahanbekam

Let $G$ be an $n$ -vertex graph and let $L : V (G) \to P ({1, 2, 3})$ be a list assignment over the vertices of $G$ , where each vertex with list of size 3 and of degree at most 5…

math.CO2021

Characterization of Graphs with Villainy 2

Sogol Jahanbekam, Meng-Ru Lin

Let $f$ be an optimal proper coloring of a graph $G$ and let $c$ be a coloring of the vertices of $G$ obtained by permuting the colors on vertices in the proper coloring $f$ . The v…

math.CO2020

Improved algorithm to determine 3-colorability of graphs with the minimum degree at least 7

Nicholas Crawford, Sogol Jahanbekam, Katerina Potika

Let $G$ be an $n$ -vertex graph with the maximum degree $Δ$ and the minimum degree $δ$ . We give algorithms with complexity $O (1.315 8^{n - 0.7 Δ (G)})$ and $O (1.3 2^{n - 0.73 Δ (G)})$ that…

math.CO2018

Weak Dynamic Coloring of Planar Graphs

Caroline Accurso, Vitaliy Chernyshov, Leaha Hand +2

The \textit{ $k$ -weak-dynamic number} of a graph $G$ is the smallest number of colors we need to color the vertices of $G$ in such a way that each vertex $v$ of degree $d (v)$ sees a…

math.CO2017

List-Distinguishing Cartesian Products of Cliques

Michael Ferrara, Zoltan Furedi, Sogol Jahanbekam +1

The distinguishing number of a graph $G$ , denoted $D (G)$ , is the minimum number of colors needed to produce a coloring of the vertices of $G$ so that every nontrivial isomorphism i…

math.CO2016

The chromatic number of the square of subcubic planar graphs

Stephen G. Hartke, Sogol Jahanbekam, Brent Thomas

Wegner conjectured in 1977 that the square of every planar graph with maximum degree at most $3$ is $7$ -colorable. We prove this conjecture using the discharging method and computa…