BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Using computational techniques we provide a framework for proving results on subclasses of planar graphs via discharging method. The aim of this paper is to apply these techniques to study the 2-distance coloring of planar subcubic graphs. Applying these techniques we show that every subcubic planar graph G of girth at least 8 has 2-distance chromatic number at most 6.
We study the minimum size f of a feedback vertex set in directed and undirected n-vertex graphs of given degeneracy or treewidth. In the undirected setting the bound k+1k−1n is known to be tight for graphs with bounded treewidth k or bounded odd degeneracy k. We show that neither of the easy upper and lower bounds k+1k−1n and k+2kn can be exact for the case of even degeneracy. More precisely, for even degeneracy k we prove that f<k+2kn and for every ε>0, there exists a k-degenerate graph for which f≥3k+43k−2n−ε. For directed graphs of bounded degeneracy k, we prove that f≤k+1k−1n and that this inequality is strict when k is odd. For directed graphs of bounded treewidth k≥2, we show that f≤k+3kn and for every ε>0, there exists a k-degenerate graph for which f≥k+1k−2⌊log2(k)⌋n−ε. Further, we provide several constructions of low degeneracy or treewidth and large f.
The Grötzsch Theorem states that every triangle-free planar graph admits a proper 3-coloring. Among many of its generalizations, the one of Grünbaum and Aksenov, giving 3-colorability of planar graphs with at most three triangles, is perhaps the most known. A lot of attention was also given to extending 3-colorings of subgraphs to the whole graph. In this paper, we consider 3-colorings of planar graphs with at most one triangle. Particularly, we show that precoloring of any two non-adjacent vertices and precoloring of a face of length at most 4 can be extended to a 3-coloring of the graph. Additionally, we show that for every vertex of degree at most 3, a precoloring of its neighborhood with the same color extends to a 3-coloring of the graph. The latter result implies an affirmative answer to a conjecture on adynamic coloring. All the presented results are tight.
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.