Local Hadwiger's conjecture

DOI10.1016/J.JCTB.2023.05.004MaRDI QIDQ6170795zbMATH OpenFDO

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)

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

zbMATH Keywords

Hadwiger's conjecturegraph minorsgraph colouringlocal algorithms

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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
• scientific article; zbMATH DE number 18032 (Why is no real title available?)
• 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)