unknown source

This knowledge was added to the database without tying it to an appropriate resource.

maximum matching on bipartite graphs upper and lower bounds vertex cover by a linear function – Kőnig’s theorem
vertex cover upper and lower bounds maximum matching by a linear function – Every edge of the matching needs to be covered by at least one vertex. Path shows that this relation is not better than linear.
maximum matching upper bounds vertex cover by a linear function – A set of all vertices taking part in a maximum matching creates a vertex cover, hence $vc(G) \le 2 \cdot mm(G)$.
odd cycle transversal is equivalent to distance to bipartite – Bipartite graphs is the graph class without any odd cycles.
distance to bipartite is equivalent to odd cycle transversal – Bipartite graphs is the graph class without any odd cycles.
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.
chromatic number upper bounds maximum clique by a linear function – Unbounded clique implies the number of needed colors is unbounded.
degeneracy upper bounds chromatic number by a linear function – Greedily color the vertices in order of the degeneracy ordering. As each vertex has at most $k$ colored predecesors we use at most $k+1$ colors.
degeneracy upper bounds average degree by a linear function – Removing a vertex of degree $d$ increases the value added to the sum of all degrees by at most $2d$, hence, the average is no more than twice the degeneracy.
maximum degree upper bounds h-index by a linear function – As h-index seeks $k$ vertices of degree $k$ it is trivially upper bound by maximum degree.
minimum degree upper bounds edge connectivity by a linear function – Removing edges incident to the minimum degree vertex disconnects the graph.
linear rank-width upper bounds rank-width by a computable function
pathwidth upper bounds linear rank-width by a computable function
minimum degree upper bounds domatic number by a linear function – The vertex of minimum degree needs to be dominated in each of the sets. As the sets cannot overlap there can be at most $k+1$ of them.
distance to linear forest upper bounds pathwidth by a linear function – After removal of $k$ vertices the remaining class has a bounded width $w$. So by including the removed vertices in every bag, we can achieve decomposition of width $w+k$
topological bandwidth upper bounds bisection bandwidth by a linear function – Order vertices by their bandwidth integer. We split the graph in the middle of this ordering. There are at most roughly $k^2/2$ edges over this split.
bandwidth upper bounds maximum degree by a linear function – Each vertex has an integer $i$ and may be connected only to vertices whose difference from $i$ is at most $k$. There are at most $k$ bigger and $k$ smaller such neighbors.
distance to linear forest upper bounds pathwidth by a linear function – After removal of $k$ vertices the remaining class has a bounded width $w$. So by including the removed vertices in every bag, we can achieve decomposition of width $w+k$
distance to outerplanar upper bounds treewidth by a linear function – After removal of $k$ vertices the remaining class has a bounded width $w$. So by including the removed vertices in every bag, we can achieve decomposition of width $w+k$
vertex integrity upper bounds treedepth by a linear function – First, treedepth removes vertices of the modulator, then it iterates through remaining components one by one.
distance to stars upper bounds treedepth by a linear function – First, treedepth removes vertices of the modulator, remainder has treedepth $2$
distance to complete upper bounds clique cover number by a linear function – We cover the $k$ vertices of the modulator by cliques of size $1$ and cover the remaining clique by another one.
maximum independent set upper bounds domination number by a linear function – Every maximal independent set is also a dominating set because any undominated vertex could be added to the independent set.
domination number upper bounds diameter by a linear function – An unbounded diameter implies a long path where no vertices that are more than $3$ apart may be dominated by the same dominating vertex, otherwise we could shorten the path. Hence, the number of dominating vertices is also unbounded.
distance to bipartite upper bounds chromatic number by a linear function – Removed vertices get one color each and we need only $2$ colors for the rest.
edge clique cover number upper bounds neighborhood diversity by an exponential function – Label vertices by the cliques they are contained in, each label is its own group in the neighborhood diversity, connect accordingly.
distance to complete upper bounds edge clique cover number by a polynomial function – Cover the remaining clique, cover each modulator vertex and its neighborhood outside of it with another clique, cover each edge within the modulator by its own edge.
treewidth upper bounds book thickness by a computable function
maximum leaf number upper bounds distance to linear forest by a computable function
acyclic chromatic number upper bounds boxicity by a computable function
h-index upper bounds distance to maximum degree by a linear function – Remove the $h$ vertices of degree at least $h$ to get a graph that has maximum degree $h$.
distance to maximum degree upper bounds h-index by a linear function – Removal of $k$ vertices yielding a graph with maximum degree $c$ means that there were $k$ vertices of arbitrary degree and the remaining vertices had degree at most $k+c$. Hence, $h$-index is no more than $k+c$.
distance to cograph upper bounds chordality by a linear function
distance to cograph upper bounds diameter by a linear function
book thickness upper bounds acyclic chromatic number by a computable function
average distance upper bounds girth by a computable function – Small average distance implies a small cycle while adding a triangle makes the girth constant and minimally changes the average distance.
bounded girth does not imply bounded average distance – Small average distance implies a small cycle while adding a triangle makes the girth constant and minimally changes the average distance.
bounded average distance does not imply bounded diameter – join of a path and a complete bipartite graph
maximum leaf number upper bounds feedback edge set by a polynomial function
maximum induced matching upper bounds diameter by a linear function – Diameter requires an induced path on $d$ edges, hence, maximum induced matching is at least $\lfloor (d+1)/3 \rfloor$.
maximum independent set upper bounds maximum induced matching by a linear function – Each edge of the induced matching can host at one vertex of the independent set.
vertex cover upper bounds neighborhood diversity by an exponential function
bounded twin-cover number does not imply bounded neighborhood diversity
linear clique-width upper bounds clique-width by a linear function
clique-width upper bounds boolean width by a linear function
boolean width upper bounds clique-width by an exponential function
branch width upper bounds boolean width by a linear function
module-width upper bounds clique-width by a computable function
clique-width upper bounds module-width by a computable function
treewidth upper bounds mm-width by a computable function
mm-width upper bounds treewidth by a computable function
branch width upper bounds rank-width by a linear function
treewidth upper bounds boolean width by a linear function
bandwidth upper bounds cutwidth by a linear function and lower bounds it by a polynomial function – Any bandwidth bound cutwidth quadratically. An example where this happens is $(P_n)^k$ which has bandwidth $k$ and cutwidth $O(k^2)$; both seem to be optimal.
modular-width upper bounds clique-width by a computable function
modular-width upper bounds diameter by a computable function
maximum degree upper bounds c-closure by a computable function
feedback edge set upper bounds c-closure by a computable function
feedback vertex set is equivalent to distance to forest
distance to forest is equivalent to feedback vertex set
vertex cover is equivalent to distance to edgeless
distance to edgeless is equivalent to vertex cover
graph class complete has unbounded maximum clique – Parameter is unbounded for the graph class of cliques.
graph class complete has unbounded domatic number – Parameter is unbounded for the graph class of cliques.
graph class complete has unbounded edge connectivity – Parameter is unbounded for the graph class of cliques.
graph class co-cluster has unbounded distance to chordal
cluster upper bounds twin-cover number by a constant
graph class cluster has unbounded domination number
graph class bipartite has unbounded girth
graph class bipartite has unbounded edge connectivity
forest upper bounds feedback edge set by a constant
graph class forest has unbounded girth
graph class forest has unbounded distance to interval
edgeless upper bounds vertex cover by a constant
graph class edgeless has unbounded domination number
graph class grid has unbounded distance to chordal
graph class grid has unbounded average distance
graph class grid has unbounded bisection bandwidth
disjoint cycles upper bounds bisection bandwidth by a constant
outerplanar upper bounds bisection bandwidth by a constant
grid upper bounds maximum degree by a constant
graph class disjoint cycles has unbounded girth
graph class interval has unbounded average distance
graph class path has unbounded treedepth
graph class linear forest has unbounded average distance
planar upper bounds genus by a constant
graph class planar has unbounded girth
graph class planar has unbounded maximum degree
graph class planar has unbounded distance to perfect
bounded vertex integrity does not imply bounded neighborhood diversity
graph class stars has unbounded h-index
graph class stars has unbounded vertex integrity
graph class cycles has unbounded distance to perfect
cycle upper bounds maximum leaf number by a constant
graph class cycle has unbounded girth
maximum leaf number upper bounds feedback edge set by a polynomial function – M. Bentert (personal communication)
bounded components upper bounds cutwidth by a linear function – By greedily placing one component after another.
bounded bounded components does not imply bounded distance to perfect – By a disjoint union of small components with distance to perfect at least 1.
bounded bounded components does not imply bounded distance to planar – By a disjoint union of many $K_5$ graphs.
star upper bounds vertex cover by a constant – trivially
star upper bounds h-index by a constant – trivially
graph class tree has unbounded h-index – trivially
graph class path has unbounded distance to cluster – trivially
graph class path has unbounded diameter – trivially
cycles upper bounds pathwidth by a constant – trivially
graph class star has unbounded maximum degree – trivially
graph class complete has unbounded maximum matching
graph class path has unbounded maximum matching
star upper bounds maximum matching by a constant
edgeless upper bounds maximum matching by a constant
clique-width upper bounds mim-width by a linear function
mim-width upper bounds sim-width by a computable function
treewidth upper bounds tree-independence number by a computable function
tree-independence number upper bounds sim-width by a computable function
clique-width upper bounds twin-width by a tower function
minimum degree upper bounds distance to disconnected by a computable function
bisection bandwidth upper bounds distance to disconnected by a computable function
distance to cluster upper bounds distance to cograph by a linear function
feedback vertex set upper bounds distance to outerplanar by a linear function
distance to planar upper bounds acyclic chromatic number by a computable function
bounded maximum independent set does not imply bounded clique cover number
bounded domination number does not imply bounded maximum independent set
genus upper bounds chromatic number by a linear function – in fact, bounded by square root
distance to cluster upper bounds shrub-depth by a constant – J. Pokorný, personal communication: Assume the class of constant dtc we want to show it has constant sd as well. For each clique connect them in a star in the tree model T. Each vertex in the modulator connect to their own vertex in T. Add a root that is in distance 2 to all leaves. Now give each vertex in the modulator a unique colour. Each other vertex that is not in the modulator has as it’s colour the set of neighbours from the modulator. In total there are $2^{dtc} + dtc$ colours that is a constant.