S. Jahanbekam

activity

20112026

most citedThe chromatic number of the square of subcubic planar graphs

24 citations · 31 across the 10 of their papers we have counts for

collaborators

12 papers

cs.DS2026

Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7

Sogol Jahanbekam

We give a polynomial-time algorithm that constructs, in every connected $n$ -vertex graph of minimum degree at least $7$ , a spanning tree with at least $\frac{25200}{46189}n>0.5455\…

math.CO2023

Triangle-degree and triangle-distinct graphs

Zhanar Berikkyzy, Beth Bjorkman, Heather Smith Blake +5

Let $G$ be a simple graph and $v$ be a vertex of $G$ . The triangle-degree of $v$ in $G$ is the number of triangles that contain $v$ . While every graph has at least two vertices wit…

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★ 24 cited

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…

math.CO2015★ 1 cited

List-antimagic labeling of vertex-weighted graphs

Zhanar Berikkyzy, Axel Brandt, Sogol Jahanbekam +2

A graph $G$ is $k$ - $w e i g h t e d - l i s t - an t ima g i c$ if for any vertex weighting $ω : V (G) \to R$ and any list assignment $L : E (G) \to 2^{R}$ with $|L(e)|\geq |E(G)|…

math.CO2015★ 4 cited

On the Strong Chromatic Index of Sparse Graphs

Philip DeOrsey, Jennifer Diemunsch, Michael Ferrara +7

The strong chromatic index of a graph $G$ , denoted $χ_{s}^{'} (G)$ , is the least number of colors needed to edge-color $G$ so that edges at distance at most two receive distinct colors.…

math.CO2013

1,2,3-Conjecture and 1,2-Conjecture for Sparse Graphs

Daniel W. Cranston, Sogol Jahanbekam, Douglas B. West

We apply the Discharging Method to prove the 1,2,3-Conjecture and the 1,2-Conjecture for graphs with maximum average degree less than 8/3. Stronger results on these conjectures hav…

math.CO2011★ 2 cited

Large chromatic number and Ramsey graphs

Csaba Biró, Zoltán Füredi, Sogol Jahanbekam

Let Q(n,c) denote the minimum clique size an n-vertex graph can have if its chromatic number is c. Using Ramsey graphs we give an exact, albeit implicit, formula for the case c is…