research
∙
03/13/2022
Local Hadwiger's Conjecture
We propose local versions of Hadwiger's Conjecture, where only balls of ...
share
research
∙
02/06/2022
The chromatic number of triangle-free hypergraphs
A triangle in a hypergraph ℋ is a set of three distinct edges e, f, g∈ℋ ...
research
∙
08/03/2021
Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs
In 1943, Hadwiger conjectured that every graph with no K_t minor is (t-1...
research
∙
10/04/2020
On decidability of hyperbolicity
We prove that a wide range of coloring problems in graphs on surfaces ca...
research
∙
06/25/2020
An even better Density Increment Theorem and its application to Hadwiger's Conjecture
In 1943, Hadwiger conjectured that every graph with no K_t minor is (t-1...
research
∙
06/21/2020
Further progress towards Hadwiger's conjecture
In 1943, Hadwiger conjectured that every graph with no K_t minor is (t-1...
research
∙
11/06/2019
A local epsilon version of Reed's Conjecture
In 1998, Reed conjectured that every graph G satisfies χ(G) ≤1/2(Δ(G) + ...
research
∙
11/06/2019
On the density of critical graphs with no large cliques
A graph G is k-critical if χ(G) = k and every proper subgraph of G is (k...
research
∙
11/04/2019
Halfway to Hadwiger's Conjecture
In 1943, Hadwiger conjectured that every K_t-minor-free graph is (t-1)-c...
research
∙
04/07/2019
Linear-Time and Efficient Distributed Algorithms for List Coloring Graphs on Surfaces
In 1994, Thomassen proved that every planar graph is 5-list-colorable. I...
research
∙
11/28/2018
Fractional coloring with local demands
We investigate fractional colorings of graphs in which the amount of col...
research
∙
10/30/2018
Improved Bounds for Randomly Sampling Colorings via Linear Programming
A well-known conjecture in computer science and statistical physics is t...
research
∙
10/15/2018
Colouring Graphs with Sparse Neighbourhoods: Bounds and Applications
Let G be a graph with chromatic number χ, maximum degree Δ and clique nu...
research
∙
04/11/2018