Hajós-Type Constructions and Neighborhood Complexes

DOI10.1137/19M1243476zbMath1453.05032arXiv1812.07991OpenAlexW3106326696MaRDI QIDQ5139660

Julianne Vega, Benjamin Braun

Publication date: 10 December 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Betti numberHajós constructionneighborhood complex

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial aspects of simplicial complexes (05E45)

Related Items

Perfect matching complexes of honeycomb graphs

Uses Software

• SageMath
• CoCalc

Cites Work

• Unnamed Item
• Unnamed Item
• Grassmann homomorphism and Hajós-type theorems
• Kneser's conjecture, chromatic number, and homotopy
• The neighborhood complex of a random graph
• Morse theory for cell complexes
• Topological lower bounds for the chromatic number: a hierarchy
• A Brooks-type result for sparse critical graphs
• Hajós' theorem for list coloring
• The complexity of the Hajós calculus for planar graphs
• Simplicial complexes of graphs
• [https://portal.mardi4nfdi.de/wiki/Publication:4256105 Haj�s constructions of critical graphs]
• [https://portal.mardi4nfdi.de/wiki/Publication:4376497 The graph constructions ofHaj�s and Ore]
• Using Hajós’ Construction to Generate Hard Graph 3-Colorability Instances
• Combinatorial algebraic topology