8 papers · 1 filter
Towards the Lovász conjecture via sublinear expanders
Matija BuciÄ, Micha Christoph, Alexey Pokrovskiy +1
Lovász' famous Hamiltonicity conjecture (1969) states that every connected vertex-transitive graph has a Hamiltonian path. A stronger version of the conjecture, often attributed t…
Extending Thomassen's conjecture to directed graphs
Micha Christoph, Barnabás Janzer, Kalina Petrova +1
A famous conjecture by Thomassen from 1983 asserts that for any given there exists some such that every graph of minimum degree at leas…
Critical edge sets in vertex-critical graphs
Ema Skottova, Raphael Steiner
Criticality is a fundamental notion in graph theory that has been studied continually since its introduction in the early 50s by Dirac. A graph is called -vertex-critical (-e…
Proof of the KAMAK tree conjecture
Micha Christoph, Raphael Steiner
There are many intriguing questions in extremal graph theory that are well-understood in the undirected setting and yet remain elusive for digraphs. A natural instance of such a pr…
Local Shearer bound
Anders Martinsson, Raphael Steiner
We prove the following local strengthening of Shearer's classic bound on the independence number of triangle-free graphs: For every triangle-free graph there exists a probabili…
Resolution of the Kohayakawa-Kreuter conjecture
Micha Christoph, Anders Martinsson, Raphael Steiner +1
A graph is said to be Ramsey for a tuple of graphs if every -coloring of the edges of contains a monochromatic copy of in color , for some …