6 papers
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…
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…
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…
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…