Tran2022

https://fpt.akt.tu-berlin.de/publications/theses/BA-Duc-Long-Tran.pdf

@thesis{Tran2022,
author = {Duc Long Tran},
month = {September},
institution = {Technische Universität Berlin},
title = {Expanding the Graph Parameter Hierarchy},
type = {Bachelor's Thesis},
url = {https://fpt.akt.tu-berlin.de/publications/theses/BA-Duc-Long-Tran.pdf},
year = {2022},
}

• page 14 : twin-cover number – An edge ${v,w}$ is a twin edge if vertices $v$ and $w$ have the same neighborhood excluding each other. The twin cover number $tcn(G)$ of a graph $G$ is the size of a smallest set $V’ \subseteq V(G)$ of vertices such that every edge in $E(G)$ is either a twin edge or incident to a vertex in $V'$
• page 14 : edge clique cover number – The edge clique cover number $eccn(G)$ of a graph $G$ is the minimum number of complete subgraphs required such that each edge is contained in at least one of them.
• page 14 : neighborhood diversity – The neighborhood diversity $nd(G)$ of a graph $G$ is the smallest number $k$ such that there is a $k$-partition $(V_1,\dots,V_k)$ of $G$, where each subset $V_i$, $i \in [k]$ is a module and is either a complete set or an independent set.
• page 14 : modular-width – The modular-width $mw(G)$ of a graph $G$ is the smallest number $h$ such that a $k$-partition $(V_1,\dots,V_k)$ of $G$ exists, where $k \le h$ and each subset $V_i$, $i \in [k]$ is a module and either contains a single vertex or for which the modular-subgraph $G[V_i]$ has a modular-width of $h$.
• page 14 : c-closure – The c-closure $\mathrm{cc}(G)$ of a graph $G$ is the smallest number $c$ such that any pair of vertices $v,w \in V(G)$ with $|N_G(v) \cap N_G(w)| \ge c$ is adjacent. …
• page 16 : boxicity – The boxicity of a graph $G$ is the minimum amount of interval graphs required, such that their intersection (ed: fixed typo) results in $G$.
• page 16 : chordality – The chordality of a graph $G$ is the minimum amount of chordal graphs required, such that their intersection (ed: fixed typo) results in $G$.
• page 18 : vertex cover $k$ upper bounds twin-cover number by $\mathcal O(k)$ – By definition
• page 18 : graph class complete has unbounded vertex cover – Note that a clique of size $n$ has … a vertex cover number of $n-1$
• page 18 : complete upper bounds twin-cover number by a constant – Note that a clique of size $n$ has a twin cover number of 0 …
• page 18 : twin-cover number $k$ upper bounds distance to cluster by $\mathcal O(k)$ – … graph $H$ with a twin cover of size $k$ has a distance to cluster of at most $k$.
• page 18 : bounded distance to cluster does not imply bounded twin-cover number – We show that twin cover number is not upper bounded by distance to cluster.
• page 18 : bounded twin-cover number does not imply bounded distance to complete – Observation 3.3. Twin Cover Number is incomparable to Distance to Clique.
• page 18 : bounded distance to complete does not imply bounded twin-cover number – Observation 3.3. Twin Cover Number is incomparable to Distance to Clique.
• page 19 : bounded twin-cover number does not imply bounded maximum clique – Observation 3.4. Twin Cover Number is incomparable to Maximum Clique, Domatic Number and Distance to Disconnected.
• page 19 : bounded maximum clique does not imply bounded twin-cover number – Observation 3.4. Twin Cover Number is incomparable to Maximum Clique, Domatic Number and Distance to Disconnected.
• page 19 : bounded twin-cover number does not imply bounded domatic number – Observation 3.4. Twin Cover Number is incomparable to Maximum Clique, Domatic Number and Distance to Disconnected.
• page 19 : bounded domatic number does not imply bounded twin-cover number – Observation 3.4. Twin Cover Number is incomparable to Maximum Clique, Domatic Number and Distance to Disconnected.
• page 19 : bounded twin-cover number does not imply bounded edge connectivity – Observation 3.4. Twin Cover Number is incomparable to Maximum Clique, Domatic Number and Distance to Disconnected.
• page 19 : bounded edge connectivity does not imply bounded twin-cover number – Observation 3.4. Twin Cover Number is incomparable to Maximum Clique, Domatic Number and Distance to Disconnected.
• page 21 : bounded twin-cover number does not imply bounded distance to co-cluster – Proposition 3.5. Twin Cover Number is incomparable to Distance to Co-Cluster.
• page 21 : bounded distance to co-cluster does not imply bounded twin-cover number – Proposition 3.5. Twin Cover Number is incomparable to Distance to Co-Cluster.
• page 22 : edge clique cover number $k$ upper bounds neighborhood diversity by $2^{\mathcal O(k)}$ – Theorem 4.1. Edge Clique Cover Number strictly upper bounds Neighborhood Diversity.
• page 22 : bounded neighborhood diversity does not imply bounded edge clique cover number – Theorem 4.1. Edge Clique Cover Number strictly upper bounds Neighborhood Diversity.
• page 23 : distance to complete $k$ upper bounds edge clique cover number by $k^{\mathcal O(1)}$ – Proposition 4.2. Disatnce to Clique strictly upper bounds Edge Clique Cover Number.
• page 23 : bounded edge clique cover number does not imply bounded distance to complete – Proposition 4.2. Disatnce to Clique strictly upper bounds Edge Clique Cover Number.
• page 23 : vertex cover $k$ upper bounds neighborhood diversity by $2^{\mathcal O(k)}$ – Proposition 4.3. Vertex Cover Number strictly upper bounds Neighborhood Diversity.
• page 23 : bounded neighborhood diversity does not imply bounded vertex cover – Proposition 4.3. Vertex Cover Number strictly upper bounds Neighborhood Diversity.
• page 24 : graph class path has unbounded modular-width – The Modular-width of a path $P$ with length $n > 3$ is $n$.
• page 25 : modular-width $k$ upper bounds clique-width by $\mathcal O(k)$ – Proposition 4.6. Modular-width strictly upper bounds Clique-width.
• page 25 : bounded clique-width does not imply bounded modular-width – Proposition 4.6. Modular-width strictly upper bounds Clique-width.
• page 25 : modular-width $k$ upper bounds diameter by $\mathcal O(k)$ – Theorem 4.7. Modular-width strictly upper bounds Max Diameter of Components.
• page 25 : bounded diameter does not imply bounded modular-width – Theorem 4.7. Modular-width strictly upper bounds Max Diameter of Components.
• page 26 : graph class path has unbounded neighborhood diversity – The Neighborhood Diversity of a Path $P$ with length $n > 3$ is $n$.
• page 26 : neighborhood diversity $k$ upper bounds boxicity by $k^{\mathcal O(1)}$ – Note that given a path of length $n > 3$. The boxicity is 1 while … neighborhood diversity is $n$. … a graph … with neighborhood diversity of $k$, its boxicity is at most $k+k^2$.
• page 26 : bounded boxicity does not imply bounded neighborhood diversity – Note that given a path of length $n > 3$. The boxicity is 1 while … neighborhood diversity is $n$. … a graph … with neighborhood diversity of $k$, its boxicity is at most $k+k^2$.
• page 28 : bounded modular-width does not imply bounded distance to cluster – Proposition 4.10. Modular-width is incomparable to Distance to Cluster.
• page 28 : bounded distance to cluster does not imply bounded modular-width – Proposition 4.10. Modular-width is incomparable to Distance to Cluster.
• page 28 : bounded modular-width does not imply bounded distance to co-cluster – Proposition 4.11. Modular-width is incomparable to Distance to Co-Cluster.
• page 28 : bounded distance to co-cluster does not imply bounded modular-width – Proposition 4.11. Modular-width is incomparable to Distance to Co-Cluster.
• page 28 : bounded neighborhood diversity does not imply bounded twin-cover number – Proposition 4.12. Modular-width is incomparable to Distance to Twin Cover Number.
• page 28 : bounded twin-cover number does not imply bounded neighborhood diversity – Proposition 4.12. Modular-width is incomparable to Distance to Twin Cover Number.
• page 29 : bounded edge clique cover number does not imply bounded vertex cover – Proposition 4.13. Edge Clique Cover Number is incomparable to Vertex Cover Number.
• page 29 : bounded vertex cover does not imply bounded edge clique cover number – Proposition 4.13. Edge Clique Cover Number is incomparable to Vertex Cover Number.
• page 29 : bounded edge clique cover number does not imply bounded domination number – Proposition 4.14. Edge Clique Cover Number is incomparable to Domination Number.
• page 29 : bounded domination number does not imply bounded edge clique cover number – Proposition 4.14. Edge Clique Cover Number is incomparable to Domination Number.
• page 29 : bounded edge clique cover number does not imply bounded distance to perfect – Proposition 4.15. Edge Clique Cover Number is incomparable to Distance to Perfect.
• page 29 : bounded distance to perfect does not imply bounded edge clique cover number – Proposition 4.15. Edge Clique Cover Number is incomparable to Distance to Perfect.
• page 30 : bounded modular-width does not imply bounded chordality – Theorem 4.16. Modular-width is incomparable to Chordality.
• page 30 : bounded chordality does not imply bounded modular-width – Theorem 4.16. Modular-width is incomparable to Chordality.
• page 32 : maximum degree $k$ upper bounds c-closure by $\mathcal O(k)$ – Proposition 5.1. Maximum Degree strictly upper bounds $c$-Closure.
• page 32 : bounded c-closure does not imply bounded maximum degree – Proposition 5.1. Maximum Degree strictly upper bounds $c$-Closure.
• page 32 : feedback edge set $k$ upper bounds c-closure by $\mathcal O(k)$ – Theorem 5.2. Feedback Edge Number strictly upper bounds $c$-Closure.
• page 32 : bounded c-closure does not imply bounded feedback edge set – Theorem 5.2. Feedback Edge Number strictly upper bounds $c$-Closure.
• page 34 : bounded c-closure does not imply bounded vertex cover – Proposition 5.3. $c$-Closure is incomparable to Vertex Cover Number.
• page 34 : bounded vertex cover does not imply bounded c-closure – Proposition 5.3. $c$-Closure is incomparable to Vertex Cover Number.
• page 34 : bounded c-closure does not imply bounded distance to complete – Proposition 5.4. $c$-Closure is incomparable to Distance to Clique.
• page 34 : bounded distance to complete does not imply bounded c-closure – Proposition 5.4. $c$-Closure is incomparable to Distance to Clique.
• page 34 : bounded c-closure does not imply bounded bisection bandwidth – Proposition 5.5. $c$-Closure is incomparable to Bisection Width.
• page 34 : bounded bisection bandwidth does not imply bounded c-closure – Proposition 5.5. $c$-Closure is incomparable to Bisection Width.
• page 34 : bounded c-closure does not imply bounded genus – Proposition 5.6. $c$-Closure is incomparable to Genus.
• page 34 : bounded genus does not imply bounded c-closure – Proposition 5.6. $c$-Closure is incomparable to Genus.
• page 34 : bounded c-closure does not imply bounded vertex connectivity – Observation 5.7. $c$-Closure is incomparable to Distance to Disconnected, Domatic Number and Maximum Clique.
• page 34 : bounded vertex connectivity does not imply bounded c-closure – Observation 5.7. $c$-Closure is incomparable to Distance to Disconnected, Domatic Number and Maximum Clique.
• page 34 : bounded c-closure does not imply bounded domatic number – Observation 5.7. $c$-Closure is incomparable to Distance to Disconnected, Domatic Number and Maximum Clique.
• page 34 : bounded domatic number does not imply bounded c-closure – Observation 5.7. $c$-Closure is incomparable to Distance to Disconnected, Domatic Number and Maximum Clique.
• page 34 : bounded c-closure does not imply bounded maximum clique – Observation 5.7. $c$-Closure is incomparable to Distance to Disconnected, Domatic Number and Maximum Clique.
• page 34 : bounded maximum clique does not imply bounded c-closure – Observation 5.7. $c$-Closure is incomparable to Distance to Disconnected, Domatic Number and Maximum Clique.
• page 35 : bounded c-closure does not imply bounded boxicity – Proposition 5.8. $c$-Closure is incomparable to Boxicity.
• page 35 : bounded boxicity does not imply bounded c-closure – Proposition 5.8. $c$-Closure is incomparable to Boxicity.
• page 36 : clique-width $k$ upper bounds twin-width by $2^{\mathcal O(k)}$ – Proposition 6.2. Clique-width strictly upper bounds Twin-width.
• page 36 : bounded twin-width does not imply bounded clique-width – Proposition 6.2. Clique-width strictly upper bounds Twin-width.
• page 37 : genus $k$ upper bounds twin-width by $\mathcal O(k)$ – Proposition 6.3. Genus strictly upper bounds Twin-width.
• page 37 : bounded twin-width does not imply bounded genus – Proposition 6.3. Genus strictly upper bounds Twin-width.
• page 37 : distance to planar $k$ upper bounds twin-width by $2^{\mathcal O(k)}$ – Theorem 6.4. Distance to Planar strictly upper bounds Twin-width.
• page 37 : bounded twin-width does not imply bounded distance to planar – Theorem 6.4. Distance to Planar strictly upper bounds Twin-width.
• page 38 : bounded twin-width does not imply bounded distance to interval – Observation 6.5. Twin-width is incomparable to Distance to Interval.
• page 38 : bounded distance to interval does not imply bounded twin-width – Observation 6.5. Twin-width is incomparable to Distance to Interval.
• page 38 : bounded twin-width does not imply bounded distance to bipartite – Proposition 6.6. Twin-width is incomparable to Distance to Bipartite.
• page 38 : bounded distance to bipartite does not imply bounded twin-width – Proposition 6.6. Twin-width is incomparable to Distance to Bipartite.
• page 40 : bounded twin-width does not imply bounded clique cover number – Proposition 6.7. Twin-width is incomparable to Clique Cover Number.
• page 40 : bounded clique cover number does not imply bounded twin-width – Proposition 6.7. Twin-width is incomparable to Clique Cover Number.
• page 40 : bounded twin-width does not imply bounded maximum degree – Proposition 6.8. Twin-width is incomparable to Maximum Degree.
• page 40 : bounded maximum degree does not imply bounded twin-width – Proposition 6.8. Twin-width is incomparable to Maximum Degree.
• page 40 : bounded twin-width does not imply bounded bisection bandwidth – Observation 6.9. Twin-width is incomparable to Bisection Width.
• page 40 : bounded bisection bandwidth does not imply bounded twin-width – Observation 6.9. Twin-width is incomparable to Bisection Width.
• page 42 : bounded degeneracy does not imply bounded boxicity – Proposition 7.1. Degeneracy is incomparable to Boxicity.
• page 42 : bounded boxicity does not imply bounded degeneracy – Proposition 7.1. Degeneracy is incomparable to Boxicity.