Source author record

Sogol Jahanbekam

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

5works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

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

Let $G$ be an $n$ -vertex graph with the maximum degree $Δ$ and the minimum degree $δ$ . We give algorithms with complexity $O(1.3158^{n-0.7~Δ(G)})$ and $O(1.32^{n-0.73~Δ(G)})$ that determines if $G$ is 3-colorable, when $δ(G)\geq 8$ and $δ(G)\geq 7$ , respectively.

preprint2016arXiv

The chromatic number of the square of subcubic planar graphs

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 computational techniques to verify reducible configurations.

preprint2015arXiv

On the Strong Chromatic Index of Sparse Graphs

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. The strong list chromatic index, denoted $χ_{s,\ell}'(G)$ , is the least integer $k$ such that if arbitrary lists of size $k$ are assigned to each edge then $G$ can be edge-colored from those lists where edges at distance at most two receive distinct colors. We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if $G$ is a subcubic planar graph with $\operatorname{girth}(G) \geq 41$ then $χ_{s,\ell}'(G) \leq 5$ , answering a question of Borodin and Ivanova [Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory, 33(4), (2014) 759--770]. We further show that if $G$ is a subcubic planar graph and $\operatorname{girth}(G) \geq 30$ , then $χ_s'(G) \leq 5$ , improving a bound from the same paper. Finally, if $G$ is a planar graph with maximum degree at most four and $\operatorname{girth}(G) \geq 28$ , then $χ_s'(G) \leq 7$ , improving a more general bound of Wang and Zhao from [Odd graphs and its application on the strong edge coloring, arXiv:1412.8358] in this case.

preprint2013arXiv

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

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 have been proved, but this is the first application of discharging to them, and the structure theorems and reducibility results are of independent interest.

preprint2012arXiv

Large chromatic number and Ramsey graphs

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 at least (n+3)/2.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.