Cover Image

Upper bounds on minimum size of feedback arc set of directed multigraphs with bounded degree

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gutin, Gregory, Lei, Hui, Yeo, Anders, Zhou, Yacong
Format:	Preprint
Published:	2024
Subjects:	Combinatorics Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Number of Subgraphs and Their Converses in Tournaments and New Digraph Polynomials
by: Ai, Jiangdong, et al.
Published: (2024)

Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees
by: Gerke, Stefanie, et al.
Published: (2024)

Feedback Arc Sets and Feedback Arc Set Decompositions in Weighted and Unweighted Oriented Graphs
by: Gutin, Gregory, et al.
Published: (2025)

Lower Bounds for Maximum Weighted Cut
by: Gutin, Gregory, et al.
Published: (2021)

Oriented discrepancy of Hamilton cycles in oriented graphs satisfying Ore-type condition
by: Ai, Jiangdong, et al.
Published: (2025)

Generalizations of Ferber-Krivelevich and Gallai Theorems on parity of degrees in induced subgraphs
by: Ai, Jiangdong, et al.
Published: (2025)

Increasing arc-connectivity by bounded- and fixed-size inversions
by: Hörsch, Florian, et al.
Published: (2026)

Feedback vertex sets of digraphs with bounded maximum degree
by: Ai, Jiangdong, et al.
Published: (2025)

Elimination distance to bounded degree on planar graphs
by: Lindermayr, Alexander, et al.
Published: (2020)

On the minimum number of arcs in $4$-dicritical oriented graphs
by: Havet, Frédéric, et al.
Published: (2023)

On expectations and variances in the hard-core model on bounded degree graphs
by: Davies, Ewan, et al.
Published: (2025)

Fractional domatic number and minimum degree
by: Chuet, Quentin, et al.
Published: (2025)

Backward Arcs in Hamilton Oriented Cycles and Paths in Directed Graphs with Independence Number Two
by: Gerke, S., et al.
Published: (2026)

On the minimum number of inversions to make a digraph $k$-(arc-)strong
by: Duron, Julien, et al.
Published: (2023)

Upper bounds on the average edit distance between two random strings
by: Rosenfeld, Matthieu
Published: (2024)

Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
by: Kelly, Tom, et al.
Published: (2018)

Immersions of large cliques in graphs with independence number 2 and bounded maximum degree
by: Botler, Fábio, et al.
Published: (2025)

A binomial random multigraph
by: Pelekis, Christos
Published: (2023)

Counting the minimum number of arcs in an oriented graph having weak diameter 2
by: Das, Sandip, et al.
Published: (2023)

Upper bounds on the average number of colors in the non-equivalent colorings of a graph
by: Hertz, Alain, et al.
Published: (2021)

Improved lower bounds on the maximum size of graphs with girth 5
by: Goedgebeur, Jan, et al.
Published: (2025)

Bounds on the price of feedback for mistake-bounded online learning
by: Geneson, Jesse, et al.
Published: (2024)

Clique-free t-matchings in degree-bounded graphs
by: Paluch, Katarzyna, et al.
Published: (2024)

Clustered independence and bounded treewidth
by: Knauer, Kolja, et al.
Published: (2023)

Acyclic dichromatic number of oriented graphs
by: Bang-Jensen, Jørgen, et al.
Published: (2025)

An explicit condition for boundedly supermultiplicative subshifts
by: Bui, Vuong, et al.
Published: (2024)

An improvement on the bound for the acyclic chromatic index
by: Kirousis, Lefteris, et al.
Published: (2026)

A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number
by: Pilipczuk, Marcin, et al.
Published: (2023)

Translating between the representations of an acyclic convex geometry of bounded degree
by: Defrain, Oscar, et al.
Published: (2025)

Long induced paths and forbidden patterns: Polylogarithmic bounds
by: Duron, Julien, et al.
Published: (2024)

Tight bound for the Erdős-Pósa property of tree minors
by: Dujmović, Vida, et al.
Published: (2024)

Strong odd colorings in graph classes of bounded expansion
by: Pilipczuk, Michał
Published: (2025)

Cops and robber in graphs with bounded vertex cover number
by: Bose, Prosenjit, et al.
Published: (2026)

New bounds for proper $h$-conflict-free colourings
by: Chuet, Quentin, et al.
Published: (2025)

Bounded twin-width graphs are polynomially $χ$-bounded
by: Bourneuf, Romain, et al.
Published: (2023)

Tight bound on treedepth in terms of pathwidth and longest path
by: Hatzel, Meike, et al.
Published: (2023)

On powers of circular arc graphs
by: Das, Ashok Kumar, et al.
Published: (2022)

A Caro-Wei bound for induced linear forests in graphs
by: Joret, Gwenaël, et al.
Published: (2024)

A polynomial bound for the minimal excluded minors for a surface
by: Houdaigoui, Sarah, et al.
Published: (2026)

On minimum Venn diagrams
by: Brenner, Sofia, et al.
Published: (2025)