unknown source
This knowledge was added to the database without tying it to an appropriate resource.
- strong d-coloring number upper bounds d-admissibility by a linear function – by definition
- weak coloring number upper bounds strong coloring number by a linear function – by definition
- bounded expansion upper bounds degeneracy by a constant – $wcol_1-1 = col_1-1=adm_1=degeneracy$
- d-admissibility upper bounds strong d-coloring number by a tower function – $col_d \le 1+(adm_d)^d$
- strong d-coloring number upper bounds weak d-coloring number by a tower function – $wcol_d \le \sum_{i=0}^d(col_d-1)^i$
- weak inf-coloring number upper bounds treedepth by a computable function
- treedepth upper bounds weak inf-coloring number by a computable function
- strong inf-coloring number upper bounds treewidth by a computable function
- treewidth upper bounds strong inf-coloring number by a computable function
- weak inf-coloring number upper bounds weak coloring number by a constant
- weak coloring number upper bounds weak d-coloring number by a computable function
- strong inf-coloring number upper bounds strong coloring number by a constant
- strong coloring number upper bounds strong d-coloring number by a computable function
- bounded expansion upper bounds weak coloring number by a computable function
- weak coloring number upper bounds bounded expansion by a computable function
- bounded expansion upper bounds strong coloring number by a computable function
- strong coloring number upper bounds bounded expansion by a computable function
- bounded expansion upper bounds admissibility by a computable function
- admissibility upper bounds bounded expansion by a computable function
- bounded expansion upper bounds nowhere dense by a constant – By definition
- excluded top-minor upper bounds bounded expansion by a constant
- degeneracy upper bounds weakly sparse by a constant
- nowhere dense upper bounds weakly sparse by a constant
- outerplanar upper bounds excluded planar minor by a constant
- excluded minor upper bounds excluded top-minor by a constant
- excluded planar minor upper bounds excluded minor by a constant
- maximum degree upper bounds excluded top-minor by a constant
- treewidth upper bounds excluded top-minor by a constant
- planar upper bounds excluded minor by a constant
- maximum matching on bipartite graphs upper and lower bounds vertex cover by a linear function – Kőnig’s theorem
- 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
- graph classes with bounded average distance are not 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
- graph classes with bounded twin-cover number are not 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
- 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 is not constant maximum clique – Parameter is unbounded for the graph class of cliques.
- graph class complete is not constant domatic number – Parameter is unbounded for the graph class of cliques.
- graph class complete is not constant edge connectivity – Parameter is unbounded for the graph class of cliques.
- graph class co-cluster is not constant distance to chordal
- cluster upper bounds twin-cover number by a constant
- graph class cluster is not constant domination number
- graph class bipartite is not constant edge connectivity
- forest upper bounds feedback edge set by a constant
- graph class forest is not constant distance to interval
- edgeless upper bounds vertex cover by a constant
- graph classes that are edgeless are not constant domination number
- graph class grid is not constant distance to chordal
- graph class grid is not constant average distance
- graph class grid is not constant bisection bandwidth
- outerplanar upper bounds bisection bandwidth by a constant
- grid upper bounds maximum degree by a constant
- graph class interval is not constant average distance
- graph class path is not constant treedepth
- graph class linear forest is not constant average distance
- planar upper bounds genus by a constant
- graph class planar is not constant maximum degree
- graph class planar is not constant distance to perfect
- graph classes with bounded vertex integrity are not bounded neighborhood diversity
- graph class stars is not constant h-index
- graph class stars is not constant vertex integrity
- graph class cycles is not constant distance to perfect
- cycle upper bounds maximum leaf number by a constant
- 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.
- graph classes with bounded bounded components are not bounded distance to perfect – By a disjoint union of small components with distance to perfect at least 1.
- graph classes with bounded bounded components are not 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 is not constant h-index – trivially
- graph class path is not constant distance to cluster – trivially
- graph class path is not constant diameter – trivially
- cycles upper bounds pathwidth by a constant – trivially
- graph class star is not constant maximum degree – trivially
- graph class complete is not constant maximum matching
- graph class path is not constant 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
- distance to cluster upper bounds distance to cograph by a linear function
- feedback vertex set upper bounds distance to outerplanar by a computable function
- distance to planar upper bounds acyclic chromatic number by a computable function
- graph classes with bounded maximum independent set are not bounded clique cover number
- graph classes with bounded domination number are not bounded maximum independent set
- genus upper bounds chromatic number by a constant – 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.
- distance to co-cluster upper bounds shrub-depth by a constant – M. Dvořák, personal communication: The proof essentially follows the Reason why there’s an arrow from cvdn (distance to cluster) to sd. Or note that distance to co-cluster is just complement of distance to cluster. And shrub-depth is closed under complemenetation.
- domino treewidth upper bounds slim tree-cut width by a computable function
- slim tree-cut width upper bounds edge-treewidth by a computable function
- edge-treewidth upper bounds overlap treewidth by a computable function
- overlap treewidth upper bounds treewidth by a computable function
- slim tree-cut width upper bounds tree-cut width by a computable function
- tree-cut width upper bounds tree-partition-width by a computable function
- edge-treewidth upper bounds tree-partition-width by a computable function
- treewidth upper bounds sparse twin-width by a tower function
- sparse twin-width upper bounds bounded expansion by a linear function
- nowhere dense upper bounds monadically stable by a constant
- monadically stable upper bounds monadically dependent by a constant
- twin-width upper bounds monadically dependent by a constant
- genus upper bounds excluded minor by a computable function
- sparse twin-width upper bounds twin-width by a linear function
- perfect upper bounds chi-bounded by a constant
- clique-width upper bounds chi-bounded by a constant
- series-parallel upper bounds chi-bounded by a constant
- distance to chordal upper bounds tree-independence number by a linear function – Put the modulator to every bag of the natural chodal graph tree decomposition which contains a clique in every bag. The biggest independent set can contain the modulator and no more than a single vertex of the clique.