7 papers · 1 filter
Feedback vertex sets of digraphs with bounded maximum degree
Jiangdong Ai, Gregory Gutin, Xiangzhou Liu +2
A digraph is an oriented graph if does not have a pair of opposite arcs. The degree of a vertex of is the sum of the in-degree and out-degree of Let b…
Odd Induced Subgraphs in Graphs of Maximum Degree Four
Jiangdong Ai, Qiwen Guo, Gregory Gutin +2
A graph is called odd if all of its vertex degrees are odd. A long-standing conjecture asked whether there exists a positive constant such that every -vertex graph without i…
Note on Long Directed Cycles in Eulerian Digraphs
Jiangdong Ai, Gregory Gutin, Fankang He +1
Huang, Ma, Shapira, Sudakov and Yuster (Comb. Prob. Comput. 2013) proved that every Eulerian digraph of average out-degree has a directed cycle of length at least W…
Large induced subgraphs with prescribed degree parity
Jiangdong Ai, Qiwen Guo, Gregory Gutin +2
A long-standing conjecture of Caro (Discrete Math, 1994), confirmed by Ferber and Krivelevich (Adv Math, 2022), states that every -vertex graph without isolated vertices con…
Judicious Partitions in Edge-Weighted Graphs with Bounded Maximum Weighted Degree
G. Gutin, M. A. Nielsen, A. Yeo +1
In this paper, we investigate bounds for the following judicious -partitioning problem: Given an edge-weighted graph , find a -partition of s…
Feedback Arc Sets and Feedback Arc Set Decompositions in Weighted and Unweighted Oriented Graphs
Gregory Gutin, Mads Anker Nielsen, Anders Yeo +1
Let be a digraph with at least one directed cycle. A set of arcs is a feedback arc set (FAS) if has no directed cycle. The FAS decomposition number ${\rm…
Oriented discrepancy of Hamilton cycles in oriented graphs satisfying Ore-type condition
Jiangdong Ai, Qiwen Guo, Gregory Gutin +4
Erd{\H o}s (1963) initiated extensive graph discrepancy research on 2-edge-colored graphs. Gishboliner, Krivelevich, and Michaeli (2023) launched similar research on oriented graph…