56 citations · 76 across the 13 of their papers we have counts for
13 papers
Three-Bit Flows and Cycle Covers. Part I
Shiva Kintali
We study the relationship between nowhere-zero three-bit flows, labeled triangles, and cycle double covers of bridgeless multigraphs. Using the flow theorems of Seymour and Tutte,…
On the Harborth Conjecture. Part I
Shiva Kintali
Harborth's conjecture states that every planar graph has a crossing-free straight-line drawing in which every edge has an integer length. Kleber's strengthening asks for the vertic…
Directed Minors III. Directed Linked Decompositions
Shiva Kintali
Thomas proved that every undirected graph admits a linked tree decomposition of width equal to its treewidth. In this paper, we generalize Thomas's theorem to digraphs. We prove th…
Directed Width Parameters and Circumference of Digraphs
Shiva Kintali
We prove that the directed treewidth, DAG-width and Kelly-width of a digraph are bounded above by its circumference plus one.
Forbidden Directed Minors and Kelly-width
Shiva Kintali, Qiuyi Zhang
Partial 1-trees are undirected graphs of treewidth at most one. Similarly, partial 1-DAGs are directed graphs of KellyWidth at most two. It is well-known that an undirected graph i…
A Note on the Balanced ST-Connectivity
Shiva Kintali, Asaf Shapira
We prove that every YES instance of Balanced ST-Connectivity has a balanced path of polynomial length.