feedback edge set

Relations

Other	Relation from	Relation to
acyclic chromatic number	exclusion	upper bound
arboricity	exclusion	upper bound
average degree	exclusion	upper bound
average distance	exclusion	exclusion
bandwidth	exclusion	exclusion
bipartite	unbounded	unknown to HOPS
bipartite number	exclusion	unknown to HOPS
bisection bandwidth	exclusion	exclusion
block	unbounded	unknown to HOPS
book thickness	exclusion	upper bound
boolean width	exclusion	upper bound
bounded components	exclusion	exclusion
boxicity	exclusion	upper bound
branch width	exclusion	upper bound
c-closure	exclusion	upper bound
carving-width	exclusion	exclusion
chordal	unbounded	unknown to HOPS
chordality	exclusion	upper bound
chromatic number	exclusion	upper bound
clique cover number	exclusion	exclusion
clique-tree-width	exclusion	upper bound
clique-width	exclusion	upper bound
cluster	unbounded	exclusion
co-cluster	unbounded	exclusion
cograph	unbounded	exclusion
complete	unbounded	exclusion
connected	unbounded	unknown to HOPS
cutwidth	exclusion	exclusion
cycle	constant	exclusion
cycles	unbounded	exclusion
d-path-free	exclusion	exclusion
degeneracy	exclusion	upper bound
degree treewidth	exclusion	exclusion
diameter	exclusion	exclusion
diameter+max degree	exclusion	exclusion
disjoint cycles	unbounded	exclusion
distance to bipartite	exclusion	upper bound
distance to block	exclusion	upper bound
distance to bounded components	exclusion	exclusion
distance to chordal	exclusion	upper bound
distance to cluster	exclusion	exclusion
distance to co-cluster	exclusion	exclusion
distance to cograph	exclusion	exclusion
distance to complete	exclusion	exclusion
distance to edgeless	exclusion	exclusion
distance to forest	exclusion	upper bound
distance to interval	exclusion	exclusion
distance to linear forest	exclusion	exclusion
distance to maximum degree	exclusion	exclusion
distance to outerplanar	exclusion	upper bound
distance to perfect	exclusion	upper bound
distance to planar	exclusion	upper bound
distance to stars	exclusion	exclusion
domatic number	exclusion	upper bound
domination number	exclusion	exclusion
edge clique cover number	exclusion	exclusion
edge connectivity	exclusion	upper bound
edgeless	constant	exclusion
feedback vertex set	exclusion	upper bound
forest	constant	exclusion
genus	exclusion	upper bound
girth	exclusion	exclusion
grid	unbounded	exclusion
h-index	exclusion	exclusion
inf-flip-width	exclusion	upper bound
interval	unbounded	exclusion
iterated type partitions	exclusion	exclusion
linear clique-width	exclusion	unknown to HOPS
linear forest	constant	exclusion
linear NLC-width	exclusion	unknown to HOPS
linear rank-width	exclusion	unknown to HOPS
maximum clique	exclusion	upper bound
maximum degree	exclusion	exclusion
maximum independent set	exclusion	exclusion
maximum induced matching	exclusion	exclusion
maximum leaf number	upper bound	exclusion
maximum matching	exclusion	exclusion
maximum matching on bipartite graphs	unknown to HOPS	exclusion
mim-width	exclusion	upper bound
minimum degree	exclusion	upper bound
mm-width	exclusion	upper bound
modular-width	exclusion	exclusion
module-width	exclusion	upper bound
neighborhood diversity	exclusion	exclusion
NLC-width	exclusion	upper bound
NLCT-width	exclusion	upper bound
odd cycle transversal	exclusion	upper bound
outerplanar	unbounded	exclusion
path	constant	exclusion
pathwidth	exclusion	exclusion
pathwidth+maxdegree	exclusion	exclusion
perfect	unbounded	unknown to HOPS
planar	unbounded	unknown to HOPS
radius-r flip-width	exclusion	upper bound
rank-width	exclusion	upper bound
shrub-depth	exclusion	unknown to HOPS
sim-width	exclusion	upper bound
star	constant	exclusion
stars	constant	exclusion
topological bandwidth	exclusion	exclusion
tree	constant	exclusion
tree-independence number	exclusion	upper bound
treedepth	exclusion	exclusion
treelength	exclusion	unknown to HOPS
treewidth	exclusion	upper bound
twin-cover number	exclusion	exclusion
twin-width	exclusion	upper bound
vertex connectivity	exclusion	unknown to HOPS
vertex cover	exclusion	exclusion
vertex integrity	exclusion	exclusion

Results

2022 Expanding the Graph Parameter Hierarchy by Tran
- page 32 : feedback edge set upper bounds c-closure by a linear function – Theorem 5.2. Feedback Edge Number strictly upper bounds $c$-Closure.
- page 32 : bounded c-closure does not imply bounded feedback edge set – Theorem 5.2. Feedback Edge Number strictly upper bounds $c$-Closure.
2019 The Graph Parameter Hierarchy by Sorge
- page 10 : feedback edge set upper bounds genus by a linear function – Lemma 4.19. The feedback edge set number $f$ upper bounds the genus $g$. We have $g \le f$.
unknown source
- feedback edge set upper bounds feedback vertex set by a linear function – Given solution to feedback edge set one can remove one vertex incident to the solution edges to obtain feedback vertex set.
- feedback edge set upper bounds genus by a linear function – Removing $k$ edges creates a forest that is embeddable into the plane. We now add one handle for each of the $k$ edges to get embedding into $k$-handle genus.
- maximum leaf number upper bounds feedback edge set by a computable function
- feedback edge set upper bounds c-closure by a computable function
- graph class forest has constant feedback edge set
- maximum leaf number upper bounds feedback edge set by a polynomial function – M. Bentert (personal communication)
Comparing Graph Parameters by Schröder
- page 23 : bounded feedback edge set does not imply bounded pathwidth – Proposition 3.16
- page 25 : bounded feedback edge set does not imply bounded distance to interval – Proposition 3.21
- page 25 : bounded feedback edge set does not imply bounded h-index – Proposition 3.22
- page 30 : bounded feedback edge set does not imply bounded bisection bandwidth – Proposition 3.29
https://stackoverflow.com/questions/10791689/how-to-find-feedback-edge-set-in-undirected-graph
- feedback edge set – Let $G=(V,E)$ be an undirected graph. A set $F \subseteq E$ of edges is called a feedback-edge set if every cycle of $G$ has at least one edge in $F$.