Seminar of Graph Theory - Matúš Matok (3.4.2025)
Thursday 3.4.2025 at 9:50, Lecture room M 213
Matúš Matok:
(Mostly) total colouring of (sub)cubic Halin graphs
Abstract:
A Halin graph is a planar graph consisting of a tree and an additional cycle connecting all the leaves in such manner that no two edges are crossing. We will be interested in (sub)cubic Halin graphs. Total colouring of a graph is a mapping from the set of vertices and edges to a set of colours such that no two neighbouring objects receive the same colour. We will be (mostly) talking about total colouring, but we will also briefly mention two very related colourings, namely AVD-colouring and SND-colouring. As there were only 3 known cubic Halin graphs with total chromatic index greater than 4, a natural open question was informally posed by Borut Lužar on whether the number of such graphs is finite. We managed to prove that the set of cubic Halin graphs with total chromatic index greater than 4 is finite, containing only the cubic Halin graphs known before-hand. By a slight modification of our approach, we managed to establish similar results for total and AVD-colouring of subcubic Halin graphs. Lastly, we observed that the set of subcubic Halin graphs with SND-chromatic index greater than 4 is infinite and its precise characterisation is currently a work in progress.