6 papers
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…
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…
Decomposing graphs into a constant number of locally irregular subgraphs
Julien Bensmail, Martin Merker, Carsten Thomassen
A graph is locally irregular if no two adjacent vertices have the same degree. The irregular chromatic index of a graph is the smallest number of locally irre…
Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree
Martin Merker
The Tree Decomposition Conjecture by Barát and Thomassen states that for every tree there exists a natural number such that the following holds: If is a -edge-…