Sorge2019

@unpublished{Sorge2019,
author = {Manuel Sorge},
title = {The Graph Parameter Hierarchy},
url = {https://manyu.pro/assets/parameter-hierarchy.pdf},
year = {2019},
}

• page 3 : acyclic chromatic number – The \emph{acyclic chromatic number} of a graph $G = (V,E)$ is the smallest size of a vertex partition $P={V_1,\dots,V_\ell}$ such that each $V_i$ is an independent set and for all $V_i,V_j$ the graph $G[V_i \cup V_j]$ does not contain a cycle.
• page 3 : arboricity – The \emph{arboricity} of a graph $G$ is the minimum number of forests the edges of $G$ can be partitioned into.
• page 3 : average degree – The \emph{average degree} of a graph $G = (V,E)$ is $2|E|/|V|$.
• page 8 : arboricity upper bounds degeneracy by a linear function – Lemma 4.5
• page 8 : degeneracy upper bounds arboricity by a linear function – Lemma 4.5
• page 8 : maximum degree upper bounds acyclic chromatic number by a polynomial function – Lemma 4.6 ([15]). The acyclic chromatic number $\chi_a$ is uppre bounded by the maximum degree $\Delta$ (for every graph with $\Delta > 4$). We have $\chi_a \le \Delta(\Delta-1)/2$.
• page 8 : h-index upper bounds acyclic chromatic number by a polynomial function – Lemma 4.7. The acyclic chromatic number $\chi_a$ is upper bounded by the $h$-index $h$. We have $\chi_a \le h(h+1)/2$.
• page 8 : genus upper bounds acyclic chromatic number by a linear function – Lemma 4.8 ([3]). The accylic chromatic number $\chi_a$ is upper bounded by the genus $g$. We have $\chi_a \le 4g+4$.
• page 8 : acyclic chromatic number upper bounds boxicity by a polynomial function – Lemma 4.9. The boxicity $b$ is upper bounded by the acyclic chromatic number $\chi_a$ (for every graph with $\chi_a>1$). We have $b \le \chi_a(\chi_a-1)$.
• page 8 : maximum leaf number upper bounds distance to linear forest by a linear function – Lemma 4.10 ([14]). The max-leaf number $\mathrm{ml}$ upper bounds the distance to disjoint paths $d$. We have $d \le \mathrm{ml}-1$.
• page 9 : boxicity upper bounds chordality by a linear function – Lemma 4.15 ([8,11]). The boxicity $b$ upper-bounds the chordality $c$. We have $c \le b$.
• page 9 : distance to interval upper bounds boxicity by a linear function – Lemma 4.16. The distance $i$ to an interval graph upper bounds the boxicity $b$. We have $b \le i+1$.
• page 9 : distance to chordal upper bounds chordality by a linear function – (ed: apparently goes as the lemma for ddist to interval and boxicity) Lemma 4.16. The distance $i$ to an interval graph upper bounds the boxicity $b$. We have $b \le i+1$.
• page 9 : distance to cograph upper bounds clique-width by an exponential function – Lemma 4.17. The distance $c$ to a cograph upper bounds the cliquewidth $q$. We have $q \le 2^{3+c}-1$.
• page 9 : acyclic chromatic number upper bounds degeneracy by a polynomial function – Lemma 4.18. The acyclic chromatic number $a$ upper bounds the degeneracy $d$. We have $d \le 2 \binom a2 - 1$
• 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$.
• page 10 : feedback vertex set upper bounds distance to chordal by a linear function – Lemma 4.20. The feedback edge set number $f$ upper bounds the distance to a chordal graph $c$. We have $c \le f$.
• page 10 : maximum leaf number upper bounds bandwidth by a linear function – Lemma 4.25. The max leaf number $\mathrm{ml}$ strictly upper bounds the bandwidth $\mathrm{bw}$.
• page 11 : clique cover number upper bounds maximum independent set by a linear function – Lemma 4.26. The minimum clique cover number $c$ strictly upper bounds the independence number $\alpha$.
• page 11 : treedepth upper bounds pathwidth by a linear function – Lemma 4.27. The treedepth $t$ strictly upper bounds the pathwidth $p$. We have $p \le t$.