BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Sogol Jahanbekam appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
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.
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.
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.
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.
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.