Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor

Sergey Norin, Zi‐Xia Song

Type: Preprint

Publication Date: 2019-01-01

Citations: 23

DOI: https://doi.org/10.48550/arxiv.1910.09378

View Publication

Locations

arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Breaking the degeneracy barrier for coloring graphs with no K minor	2023	Sergey Norin Luke Postle Zi‐Xia Song
+	Connectivity and choosability of graphs with no $K_t$ minor	2020	Sergey Norin Luke Postle
+	Halfway to Hadwiger's Conjecture.	2019	Luke Postle
+	Halfway to Hadwiger's Conjecture	2019	Luke Postle
+	Further progress towards Hadwiger's conjecture	2020	Luke Postle
+	Further progress towards Hadwiger's conjecture.	2020	Luke Postle
+	Connectivity and choosability of graphs with no K minor	2021	Sergey Norin Luke Postle
+	An even better Density Increment Theorem and its application to Hadwiger's Conjecture.	2020	Luke Postle
+	An even better Density Increment Theorem and its application to Hadwiger's Conjecture	2020	Luke Postle
+	A new upper bound on the chromatic number of graphs with no odd $K_t$ minor	2019	Sergey Norin Zi‐Xia Song
+	Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs	2021	Michelle Delcourt Luke Postle
+	Asymptotic Equivalence of Hadwiger's Conjecture and its Odd Minor-Variant	2021	Raphael Steiner
+	Linear-sized minors with given edge density	2022	Tung H. Nguyen
+ PDF Chat	Forcing a sparse minor	2015	Bruce Reed David R. Wood
+	Further Progress towards the List and Odd Versions of Hadwiger's Conjecture	2020	Luke Postle
+	Finding dense minors using average degree	2023	Kevin Hendrey Sergey Norin Raphael Steiner Jérémie Turcotte
+	Recent progress towards Hadwiger’s conjecture	2023	Sergey Norin
+	Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant	2022	Raphael Steiner
+	A Note on Hadwiger's Conjecture	2013	David R. Wood
+ PDF Chat	Dominating $K_t$-Models	2024	Freddie Illingworth David R. Wood

Works That Cite This (24)

Action	Title	Year	Authors
+ PDF Chat	Disproof of a Conjecture by Woodall on the Choosability of $K_{s,t}$-Minor-Free Graphs	2022	Raphael Steiner
+	Clique immersion in graphs without fixed bipartite graph	2020	Hong Liu Guanghui Wang Donglei Yang
+	A local epsilon version of Reed's Conjecture	2019	Tom Kelly Luke Postle
+	Improved bound for Hadwiger's conjecture	2021	Yan Wang
+	Phase Transition of Degeneracy in Minor-Closed Families	2019	Chun‐Hung Liu Fan Wei
+ PDF Chat	Immersion and clustered coloring	2022	Chun‐Hung Liu
+	Defective coloring is perfect for minors	2022	Chun‐Hung Liu
+ PDF Chat	Reducing linear Hadwiger’s conjecture to coloring small graphs	2024	Michelle Delcourt Luke Postle
+ PDF Chat	Subgraphs of large connectivity and chromatic number	2022	António Girão Bhargav Narayanan
+	Strong complete minors in digraphs	2020	Maria Axenovich António Girão Richard Snyder Lea Weber

Works Cited by This (26)

Action	Title	Year	Authors
+	On Hadwiger's Number and the Stability Number	1982	Pierre Duchet H. Meyniel
+	Extremal problems in graph theory	1997	Christopher M. Hartman
+	A Note on Hadwiger's Conjecture	2013	David R. Wood
+	A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs	1952	G. A. Dirac
+	Cycles of even length in graphs	1974	J. A. Bondy Miklós Simonovits
+	A relaxed Hadwiger's Conjecture for list colorings	2007	Ken‐ichi Kawarabayashi Bojan Mohar
+	Some Recent Progress and Applications in Graph Minor Theory	2007	Ken‐ichi Kawarabayashi Bojan Mohar
+	Subcontraction-equivalence and Hadwiger's conjecture	1987	Douglas R. Woodall
+	Lower bound of the hadwiger number of graphs by their average degree	1984	Alexandr Kostochka
+	Über eine Eigenschaft der ebenen Komplexe	1937	Klaus W. Wagner