8 papers · 1 filter
Counterexamples to Thomassen's conjecture on decomposition of cubic graphs
Thomas Bellitto, Tereza Klimošová, Martin Merker +2
We construct an infinite family of counterexamples to Thomassen's conjecture that the vertices of every 3-connected, cubic graph on at least 8 vertices can be colored blue and red…
Gaps in the cycle spectrum of 3-connected cubic planar graphs
Martin Merker
We prove that, for every natural number , every sufficiently large 3-connected cubic planar graph has a cycle whose length is in . We also show that this bound is clos…
Cycle lengths modulo in large 3-connected cubic graphs
Kasper S. Lyngsie, Martin Merker
We prove that for all natural numbers and where is odd, there exists a natural number such that any 3-connected cubic graph with at least vertices contain…
Spanning trees without adjacent vertices of degree 2
Kasper Szabo Lyngsie, Martin Merker
Albertson, Berman, Hutchinson, and Thomassen showed in 1990 that there exist highly connected graphs in which every spanning tree contains vertices of degree 2. Using a result of A…
A counterexample to Montgomery's conjecture on dynamic colourings of regular graphs
Nathan Bowler, Joshua Erde, Florian Lehner +3
A \emph{dynamic colouring} of a graph is a proper colouring in which no neighbourhood of a non-leaf vertex is monochromatic. The \emph{dynamic colouring number} of a graph…
Bounded Diameter Arboricity
Martin Merker, Luke Postle
We introduce the notion of \emph{bounded diameter arboricity}. Specifically, the \emph{diameter- arboricity} of a graph is the minimum number such that the edges of the grap…