unknown source

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

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.
graph class complete has constant distance to complete – by definition
graph class co-cluster has constant distance to co-cluster – by definition
graph class cograph has constant distance to cograph – by definition
graph class cluster has constant distance to cluster – by definition
graph class linear forest has constant distance to linear forest – by definition
graph class outerplanar has constant distance to outerplanar – by definition
graph class block has constant distance to block – by definition
graph class edgeless has constant distance to edgeless – by definition
graph class forest has constant distance to forest – by definition
graph class bipartite has constant distance to bipartite – by definition
graph class planar has constant distance to planar – by definition
graph class chordal has constant distance to chordal – by definition
graph class stars has constant distance to stars – by definition
graph class perfect has constant distance to perfect – by definition
graph class interval has constant distance to interval – by definition
maximum degree upper bounds distance to maximum degree by a linear function – by definition
bounded components upper bounds distance to bounded components by a linear function – by definition
linear forest – Disjoint union of paths.
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 lower bound.
odd cycle transversal is equal to distance to bipartite – 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 clique-width by a computable function
distance to cograph upper bounds chordality by a computable function
distance to cograph upper bounds diameter by a computable function
book thickness upper bounds acyclic chromatic number by a computable function
average distance upper bounds girth by a computable function
maximum leaf number upper bounds feedback edge set by a computable 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 computable 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
branch width upper bounds rank-width by a linear function
treewidth upper bounds boolean width by a computable function
bandwidth upper and lower bounds cutwidth 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
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.
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
graph class cluster has constant twin-cover number
graph class cluster has unbounded domination number
graph class bipartite has unbounded girth
graph class bipartite has unbounded edge connectivity
graph class forest has constant feedback edge set
graph class forest has unbounded girth
graph class forest has unbounded distance to interval
graph class edgeless has constant vertex cover
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
graph class disjoint cycles has constant bisection bandwidth
graph class outerplanar has constant bisection bandwidth
graph class grid has constant maximum degree
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
graph class planar has constant genus
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
graph class cycle has constant maximum leaf number
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 polynomial 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.
graph class star has constant vertex cover – trivially
graph class star has constant h-index – 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
graph class cycles has constant pathwidth – trivially
graph class star has unbounded maximum degree – trivially