David Wellner:
Über Dicke und Splitdicke von Graphen
Kurzbeschreibung
In 2015 wurde die Splitdicke als Graphparameter eingeführt. Die Splitdicke hat Ähnlichkeiten zu der Dicke von Graphen. In dieser Arbeit stellen wir die beiden Parameter in Beziehung, erläutern die Ahnlichkeiten und nennen ein paar bekannte Fakten. Darauf aufbauend analysieren wir die Dicke und Splitdicke der Graphenklasse der (multidimensionalen) Gittergraphen, wozu auch die Würfelgraphen gehören. Abschließend gehen wir noch auf die Komplexit ät ein und zeigen, dass es NP-schwer ist für einen gegebenen Graphen die Gleichheit von Dicke und Splitdicke zu prüfen.