unknown

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

• complete upper bounds connected by a constant – by definition
• complete upper bounds cluster by a constant – by definition
• tree upper bounds connected by a constant – by definition
• tree upper bounds forest by a constant – by definition
• path upper bounds connected by a constant – by definition
• path upper bounds linear forest by a constant – by definition
• star upper bounds connected by a constant – by definition
• star upper bounds stars by a constant – by definition
• cycle upper bounds connected by a constant – by definition
• cycle upper bounds cycles by a constant – by definition
• block – Every block (maximal 2-connected subgraph) is a clique.
• cluster – Disjoint union of complete graphs.
• cluster – Every connected component is a complete graph.
• cluster – Does not include path on three vertices as an induced subgraph.
• co-cluster – Complete multipartite graph.
• disjoint cycles – All cycles in the graph are disjoint. Can contain arbitrary trees attached to and between the cycles.
• pathwidth+maxdegree $k$ upper bounds pathwidth by $\mathcal O(k)$ – by definition
• pathwidth+maxdegree $k$ upper bounds maximum degree by $\mathcal O(k)$ – by definition
• degree treewidth $k$ upper bounds maximum degree by $\mathcal O(k)$ – by definition
• degree treewidth $k$ upper bounds treewidth by $\mathcal O(k)$ – by definition
• complete upper bounds distance to complete by a constant – by definition
• co-cluster upper bounds distance to co-cluster by a constant – by definition
• cograph upper bounds distance to cograph by a constant – by definition
• cluster upper bounds distance to cluster by a constant – by definition
• linear forest upper bounds distance to linear forest by a constant – by definition
• outerplanar upper bounds distance to outerplanar by a constant – by definition
• block upper bounds distance to block by a constant – by definition
• edgeless upper bounds distance to edgeless by a constant – by definition
• forest upper bounds distance to forest by a constant – by definition
• bipartite upper bounds distance to bipartite by a constant – by definition
• planar upper bounds distance to planar by a constant – by definition
• chordal upper bounds distance to chordal by a constant – by definition
• stars upper bounds distance to stars by a constant – by definition
• perfect upper bounds distance to perfect by a constant – by definition
• interval upper bounds distance to interval by a constant – by definition
• maximum degree $k$ upper bounds distance to maximum degree by $\mathcal O(k)$ – by definition
• bounded components $k$ upper bounds distance to bounded components by $\mathcal O(k)$ – by definition
• disconnected upper bounds distance to disconnected by a constant – by definition
• maximum matching on bipartite graphs $k$ upper bounds bipartite by $\mathcal O(k)$ – by definition
• maximum matching on bipartite graphs $k$ upper bounds maximum matching by $\mathcal O(k)$ – by definition
• linear forest – Disjoint union of paths.
• maximum matching on bipartite graphs $k$ implies that vertex cover is $\mathcal O(k)$ – Kőnig’s theorem
• vertex cover $k$ implies that maximum matching is $\mathcal O(k)$ – Every edge of the matching needs to be covered by at least one vertex. Path shows lower bound.
• odd cycle transversal is equal to distance to bipartite – Bipartite graphs is the graph class without any odd cycles.
• feedback edge set $k$ upper bounds feedback vertex set by $\mathcal O(k)$ – Given solution to feedback edge set one can remove one vertex incident to the solution edges to obtain feedback vertex set.
• feedback edge set $k$ upper bounds genus by $\mathcal O(k)$ – 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 $k$ upper bounds maximum clique by $\mathcal O(k)$ – Unbounded clique implies the number of needed colors is unbounded.
• degeneracy $k$ upper bounds chromatic number by $\mathcal O(k)$ – 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 $k$ upper bounds average degree by $\mathcal O(k)$ – 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 $k$ upper bounds h-index by $\mathcal O(k)$ – As h-index seeks $k$ vertices of degree $k$ it is trivially upper bound by maximum degree.
• minimum degree $k$ upper bounds edge connectivity by $\mathcal O(k)$ – Removing edges incident to the minimum degree vertex disconnects the graph.
• linear rank-width $k$ upper bounds rank-width by $f(k)$
• pathwidth $k$ upper bounds linear rank-width by $f(k)$
• minimum degree $k$ upper bounds domatic number by $\mathcal O(k)$ – 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 $k$ upper bounds pathwidth by $\mathcal O(k)$ – 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 $k$ upper bounds bisection bandwidth by $\mathcal O(k)$ – 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 $k$ upper bounds maximum degree by $\mathcal O(k)$ – 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 $k$ upper bounds pathwidth by $\mathcal O(k)$ – 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 $k$ upper bounds treewidth by $\mathcal O(k)$ – 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 $k$ upper bounds treedepth by $\mathcal O(k)$ – First, treedepth removes vertices of the modulator, then it iterates through remaining components one by one.
• distance to stars $k$ upper bounds treedepth by $\mathcal O(k)$ – First, treedepth removes vertices of the modulator, remainder has treedepth $2$
• distance to complete $k$ upper bounds clique cover number by $\mathcal O(k)$ – We cover the $k$ vertices of the modulator by cliques of size $1$ and cover the remaining clique by another one.
• maximum independent set $k$ upper bounds domination number by $\mathcal O(k)$ – Every maximal independent set is also a dominating set because any undominated vertex could be added to the independent set.
• domination number $k$ upper bounds diameter by $\mathcal O(k)$ – 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 $k$ upper bounds chromatic number by $\mathcal O(k)$ – Removed vertices get one color each and we need only $2$ colors for the rest.
• edge clique cover number $k$ upper bounds neighborhood diversity by $2^{\mathcal O(k)}$ – Label vertices by the cliques they are contained in, each label is its own group in the neighborhood diversity, connect accordingly.
• distance to complete $k$ upper bounds edge clique cover number by $k^{\mathcal O(1)}$ – 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 $k$ upper bounds book thickness by $f(k)$
• maximum leaf number $k$ upper bounds distance to linear forest by $f(k)$
• acyclic chromatic number $k$ upper bounds boxicity by $f(k)$
• h-index $k$ upper bounds distance to maximum degree by $\mathcal O(k)$ – Remove the $h$ vertices of degree at least $h$ to get a graph that has maximum degree $h$.
• distance to maximum degree $k$ upper bounds h-index by $\mathcal O(k)$ – 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$.
• vertex connectivity is equal to distance to disconnected – By definition
• distance to cograph $k$ upper bounds clique-width by $f(k)$
• distance to cograph $k$ upper bounds chordality by $f(k)$
• distance to cograph $k$ upper bounds diameter by $f(k)$
• book thickness $k$ upper bounds acyclic chromatic number by $f(k)$
• average distance $k$ upper bounds girth by $f(k)$
• maximum leaf number $k$ upper bounds feedback edge set by $f(k)$
• maximum induced matching $k$ upper bounds diameter by $\mathcal O(k)$ – Diameter requires an induced path on $d$ edges, hence, maximum induced matching is at least $\lfloor (d+1)/3 \rfloor$.
• maximum independent set $k$ upper bounds maximum induced matching by $\mathcal O(k)$ – Each edge of the induced matching can host at one vertex of the independent set.
• vertex cover $k$ upper bounds neighborhood diversity by $2^{\mathcal O(k)}$
• bounded twin-cover number does not imply bounded neighborhood diversity
• twin-cover number $k$ upper bounds shrub-depth by $\mathcal O(k)$
• linear clique-width $k$ upper bounds clique-width by $f(k)$
• clique-width $k$ upper bounds boolean width by $\mathcal O(k)$
• boolean width $k$ upper bounds clique-width by $2^{\mathcal O(k)}$
• branch width $k$ upper bounds boolean width by $\mathcal O(k)$
• branch width $k$ upper bounds rank-width by $\mathcal O(k)$
• treewidth $k$ upper bounds boolean width by $f(k)$
• bandwidth $k$ implies that cutwidth is $k^{\mathcal O(1)}$ – 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 $k$ upper bounds clique-width by $f(k)$
• modular-width $k$ upper bounds diameter by $f(k)$
• maximum degree $k$ upper bounds c-closure by $f(k)$
• feedback edge set $k$ upper bounds c-closure by $f(k)$
• vertex integrity $k$ upper bounds distance to bounded components by $\mathcal O(k)$ – By definition
• distance to bounded components $k$ upper bounds vertex integrity by $\mathcal O(k)$ – By definition
• bandwidth $k$ upper bounds topological bandwidth by $\mathcal O(k)$ – By definition
• twin-cover number $k$ upper bounds distance to cluster by $\mathcal O(k)$ – By definition
• vertex cover $k$ upper bounds twin-cover number by $\mathcal O(k)$ – By definition
• average degree $k$ upper bounds minimum degree by $\mathcal O(k)$ – By definition
• diameter $k$ upper bounds average distance by $\mathcal O(k)$ – By definition
• maximum matching $k$ upper bounds maximum induced matching by $\mathcal O(k)$ – By definition
• distance to interval $k$ upper bounds boxicity by $\mathcal O(k)$ – By definition
• bisection bandwidth $k$ upper bounds edge connectivity by $\mathcal O(k)$ – By definition
• vertex integrity – Minimum $k$ such that there exists $k$ vertices whose removal results in connected components of sizes at most $k$.
• twin-cover number – Distance to cluster where all vertices of each clique are siblings.
• maximum degree – maximum degree of graph’s vertices
• feedback vertex set – can be thought of as a distance to forest
• minimum degree – minimum degree of graph’s vertices
• diameter – Maximum distance of two vertices that are in the same connected component.
• treedepth $k$ upper bounds diameter by $f(k)$ – An unbounded diameter implies the class contains paths as subgraphs. Minimum treedepth to embed a path of length $n$ in a treedepth tree is $\log n$.
• feedback vertex set is equal to distance to forest
• vertex cover is equal to distance to edgeless
• 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 disjoint cycles has unbounded distance to perfect
• cycle upper bounds maximum leaf number by a constant
• graph class cycle has unbounded girth
• maximum leaf number $k$ upper bounds feedback edge set by $k^{\mathcal O(1)}$ – M. Bentert (personal communication)
• bounded components $k$ upper bounds cutwidth by $k^{\mathcal O(1)}$ – 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.
• edgeless upper bounds bounded components by a constant – By definition
• grid upper bounds maximum degree by a constant – By definition
• bounded components $k$ upper bounds maximum degree by $\mathcal O(k)$ – By definition
• linear forest upper bounds maximum degree by a constant – By definition
• cycles upper bounds maximum degree by a constant – By definition