G. Gutin

collaborators

7 papers

math.CO2026

Sharp lower bounds for bisections of graphs with bounded maximum degree

Qiwen Guo, Gregory Gutin

A bisection of a graph is a partition of its vertex set into two parts whose sizes differ by at most one. We prove that every graph with $m$ edges and maximum degree at most $k$ ha…

math.CO2026

Note on near-spanning balanced antidirected trees missing from regular tournaments

Gregory Gutin, Yiming Hao

We construct near-spanning balanced antidirected trees that fail to embed in highly symmetric tournaments despite the conjectured semidegree condition being satisfied. More precise…

math.CO2026

An $O (k lo g (n / k))$ Bound on Spanning Bipartite Connectivity

G. Gutin, Y. Hao, Y. Zhou

For integers $1 \leq k \leq n /2$ , let $f (k, n)$ be the least integer $s$ such that every $s$ -connected graph on $n$ vertices contains a spanning bipartite $k$ -connected subgraph. Thomas…

math.CO2026

A linear bound for nested cycles without geometric crossings

Jiangdong Ai, Gregory Gutin, Yiming Hao

Cycles $C_{1}, \dots, C_{k}$ in a graph are called nested without geometric crossings if they are pairwise edge-disjoint, $V (C_{k}) \subseteq \dots \subseteq V (C_{1})$ , and each pair of conse…

math.CO2026

Bounds on Odd and Odd-Even Induced Subgraphs

Qiwen Guo, Gregory Gutin, Yiming Hao +3

Let $G$ be an $n$ -vertex graph and let $ℓ : V (G) \to F_{2}$ prescribe degree parities. A set $S \subseteq V (G)$ is $ℓ$ -admissible if every $v \in S$ has degree congruent to…

math.CO2026

Backward Arcs in Hamilton Oriented Cycles and Paths in Directed Graphs with Independence Number Two

S. Gerke, Q. Guo, G. Gutin +3

In a digraph $D = (V, A)$ , an oriented path is a sequence $P = x_{1} x_{2} \dots x_{p}$ of distinct vertices such that either $x_{i} x_{i + 1} \in A$ or $x_{i + 1} x_{i} \in A$ or both for every $i\in [p…

cs.CG2025

FPT Constant Approximation Algorithms for Colorful Sum of Radii

Shuilian Liu, Gregory Gutin, Yicheng Xu +1

We study the colorful sum of radii problem, where the input is a point set $P$ partitioned into classes $P_{1}, P_{2}, \dots, P_{ω}$ , along with per-class outlier bounds $m_1, m_2, \dots…

Sharp lower bounds for bisections of graphs with bounded maximum degree

Note on near-spanning balanced antidirected trees missing from regular tournaments

An O(klog(n/k)) Bound on Spanning Bipartite Connectivity

A linear bound for nested cycles without geometric crossings

Bounds on Odd and Odd-Even Induced Subgraphs

Backward Arcs in Hamilton Oriented Cycles and Paths in Directed Graphs with Independence Number Two

FPT Constant Approximation Algorithms for Colorful Sum of Radii

An $O (k lo g (n / k))$ Bound on Spanning Bipartite Connectivity