Lune

SODA2024Top-tier venue

Partial Coloring Complex, Vertex Decomposability and Tverberg's Theorem with Constraints

Sharareh Alipour, Amir Jafari, Mohammad Hassan Mazidi, Seyed Abolfazl Najafian

Abstract

We present a novel family of simplicial complexes associated with the graph coloring problem. They include many well-known simplicial complexes such as chessboard complexes and crosspolytopes. We then study conditions under which these complexes become vertex decomposable and hence shellable. The connectivity of these complexes is also investigated. We apply these results to Tverberg's theorem with constraints and also to the chromatic number of certain Kneser-type hypergraphs and improve upon existing facts. Notably, we prove a conjecture of Engström and Norén on Tverberg graphs.

Ask Lune

Know where this paper stands in minutes, not an afternoon.

Lune can read the top-tier papers that cite it and the ones closest to it, and tells you what it claims, what came after and where it falls short, each point cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

its abstract · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. Three-edge-coloring (Tait coloring) cubic graphs and nowhere-zero 4-flow for graphs on the torusYuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar et al.SODA 2026 · 1 citation
  2. Extended VC-dimension, and Radon and Tverberg type theorems for unions of convex setsNoga Alon, Shakhar SmorodinskySODA 2026
  3. Counting list homomorphisms from graphs of bounded treewidth: tight complexity boundsJacob Focke, Dániel Marx, Pawel RzazewskiSODA 2022 · 1 citation
  4. Counting and Finding Homomorphisms is Universal for Parameterized Complexity TheoryMarc Roth, Philip WellnitzSODA 2020 · 8 citations
  5. Optimal thresholds for Latin squares, Steiner Triple Systems, and edge coloringsVishesh Jain, Huy Tuan PhamSODA 2024 · 5 citations
Dusk over the sea between two cliffs drawn in fine vertical lines