PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
February 9, 2026Transactions of the American Mathematical Society0 citations

Limits of degeneracy for colouring graphs with forbidden minors

View Full Paper
SNSergey NorinMcGill UniversityJTJérémie TurcotteMcGill University

Key Points

  • To identify under what conditions graphs with certain properties ensure a vertex of restricted degree in the absence of forbidden minors.
  • Analysis of monotone graph families
  • Examination of bipartite graphs
  • Investigation of strongly sublinear separators
  • Development of criteria based on maximum degree
  • All sufficiently large bipartite graphs with bounded maximum degree possess the vertex degree property
  • Conditions for H not belonging to family F can be omitted without loss of generality
  • Link established between graph properties and degeneracy limits in colouring

Abstract

Motivated by Hadwiger’s conjecture, Seymour asked which graphs H H have the property that every non-null graph G G with no H H minor has a vertex of degree at most | V (H) | − 2 |V (H) |-2. We show that for every monotone graph family F F with strongly sublinear separators, all sufficiently large bipartite graphs H ∈ F H F with bounded maximum degree have this property. None of the conditions that H H belongs to F F, that H H is bipartite and that H H has bounded maximum degree can be omitted.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Norin et al. (2025) studied this question.

synapsesocial.com/papers/698979f5f0ec2af6756e8084https://doi.org/10.1090/tran/9493
Ask AI
Helpful
Bookmark
Share
View Full Paper