Research

Symmetry Breaking in Infinite Graphs

A central theme of my research is symmetry breaking in finite and infinite graphs. I study distinguishing vertex and edge colourings, with particular emphasis on infinite graphs. Recently, I have focused on list variants of distinguishing colourings.

I establish optimal bounds for various distinguishing parameters for wide classes of graphs. In recent work, I obtained new optimal results on list distinguishing colourings, some of which were not previously known even for the non-list variants.

Distinguishing Colourings and the Axiom of Choice

I investigate distinguishing and proper colourings in ZF (i.e. without assuming the Axiom of Choice).

I proved that certain statements about distinguishing and proper colourings are, over ZF, equivalent either to the Axiom of Choice or to Kőnig’s Lemma.

Infinite Regular Graphs and Factorizations

I study decompositions of non-locally finite regular graphs, in particular factorizations of regular graphs of infinite degree.

In 1936, Kőnig proved that for every infinite cardinal κ, every κ-regular graph admits a factorization into κ perfect matchings. I generalized this theorem in full generality, extending classical results of Andersen and Thomassen.

Majority Colourings

I study majority vertex and edge colourings, which are closely related to the Unfriendly Partition Conjecture, arguably one of the most prominent open problems concerning infinite graphs.

I obtained optimal results on majority edge colourings in the list setting, leading to a proof that the Unfriendly Partition Conjecture holds for line graphs. The result is established in the more general list framework and for line graphs of arbitrary cardinality. It constitutes one of the very few results towards the Unfriendly Partition Conjecture.

Eulerian Subgraphs

I studied a structural problem related to Eulerian graphs, the first topic in graph theory. For a given finite graph G and its subgraph H, we ask whether there exists an Eulerian subgraph of G that contains H, thus generalising the classical problem of Euler.

I proved that this problem is NP-complete in general. However, it becomes polynomial — and even linear — when restricted to connected subgraphs H.