Local Hadwiger's conjecture

DOI10.1016/J.JCTB.2023.05.004zbMATH Open1519.05083arXiv2203.06718MaRDI QIDQ6170795FDOQ6170795

Authors: Benjamin Moore, Luke Postle, Lise Turner 

Publication date: 10 August 2023

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: We propose local versions of Hadwiger's Conjecture, where only balls of radius $Omega(logv(G))$ around each vertex are required to be $K_t$-minor-free. We ask: if a graph is locally-$K_t$-minor-free, is it $t$-colourable? We show that the answer is yes when $tleq5$, even in the stronger setting of list-colouring, and we complement this result with a $O(logv(G))$-round distributed colouring algorithm in the LOCAL model. Further, we show that for large enough values of $t$, we can list-colour locally-$K_t$-minor-free graphs with $13cdotmaxlefth(t),leftlceilfrac312(t-1)ightceilight$ colours, where $h(t)$ is any value such that all $K_t$-minor-free graphs are $h(t)$-list-colourable. We again complement this with a $O(logv(G))$-round distributed algorithm.

Full work available at URL: https://arxiv.org/abs/2203.06718

Recommendations

• A local version of Szpiro's conjecture
• scientific article; zbMATH DE number 432944
• On the local approach to Sidorenko's conjecture
• Hadwiger's conjecture
• Hadwiger's conjecture
• The Linnik conjecture. A local approach
• Sur le théorème local de Harnack
• scientific article; zbMATH DE number 2124266
• A localized Erdős-Wintner theorem
• The local sum conjecture in two dimensions

zbMATH Keywords

Hadwiger's conjecturegraph minorsgraph colouringlocal algorithms

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

Cites Work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Über eine Eigenschaft der ebenen Komplexe
• Title not available (Why is that?)
• An extremal function for contractions of graphs
• Lower bound of the Hadwiger number of graphs by their average degree
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Title not available (Why is that?)
• Every Planar Map is Four Colorable
• Graph theory
• Linear connectivity forces large complete bipartite minors
• Disproof of the list Hadwiger conjecture
• Parallel Symmetry-Breaking in Sparse Graphs
• Deterministic coin tossing with applications to optimal parallel list ranking
• Some recent progress and applications in graph minor theory
• Fractional colouring and Hadwiger's conjecture
• Choosability of \(K_5\)-minor-free graphs
• A relaxed Hadwiger's conjecture for list colorings
• Distributed coloring in sparse graphs with fewer colors
• Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.
• Hyperbolic families and coloring graphs on surfaces
• Connectivity and choosability of graphs with no \(K_t\) minor
• Breaking the degeneracy barrier for coloring graphs with no \(K_t\) minor
• Progress towards Nash-Williams' conjecture on triangle decompositions
• 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
• Improved lower bound for the list chromatic number of graphs with no K_t minor

Cited In (5)

• A local strategy to decide the Alperin and Dade conjectures
• Kato's local \(\varepsilon\)-conjecture in dimension 2
• Kato's local epsilon conjecture: \(l\neq p\) case
• Title not available (Why is that?)
• Hadwiger's conjecture is decidable

This page was built for publication: Local Hadwiger's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6170795)