Seminár z teórie grafov - Matúš Matok (3.4.2025)
vo štvrtok 3.4.2025 o 9:50 hod. v miestnosti M 213
Prednášajúci: Matúš Matok
Názov: (Mostly) total colouring of (sub)cubic Halin graphs
Termín: 3.4.2025, 9:50 hod., M 213
Abstrakt:
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.