Coloring complexes and arrangements

DOI10.1007/S10801-007-0086-ZMaRDI QIDQ2481072zbMATH OpenOpenAlexFDO

Authors Patricia Hersh, Ed Swartz

Publication date 14 April 2008

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Chromatic polynomialColoring complexConvex ear decomposition

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15)

Abstract: Steingrimsson's coloring complex and Jonsson's unipolar complex are interpreted in terms of hyperplane arrangements. This viewpoint leads to short proofs that all coloring complexes and a large class of unipolar complexes have convex ear decompositions. These convex ear decompositions impose strong new restrictions on the chromatic polynomials of all finite graphs. Similar results are obtained for characteristic polynomials of submatroids of type B_n arrangements.

Recommendations

• The topology of the coloring complex
• Link complexes of subspace arrangements
• Hypergraph coloring complexes
• On certain hyperplane arrangements and colored graphs
• The Hodge structure of the coloring complex of a hypergraph

Cites work

• g-elements, finite buildings and higher Cohen-Macaulay connectivity.
• Combinatorics and commutative algebra.
• scientific article; zbMATH DE number 67324 (Why is no real title available?)
• scientific article; zbMATH DE number 3547324 (Why is no real title available?)
• scientific article; zbMATH DE number 1309427 (Why is no real title available?)
• scientific article; zbMATH DE number 2223037 (Why is no real title available?)
• Lectures on Polytopes
• Link complexes of subspace arrangements
• Signed graph coloring
• The Broken-Circuit Complex
• The coloring ideal and coloring complex of a graph
• The Koszul property in affine semigroup rings
• The topology of the coloring complex
• Two Decompositions in Topological Combinatorics with Applications to Matroid Complexes

Cited in

(19)

• The homology of the cyclic coloring complex of simple graphs
• Fibres and ordered set coloring
• The topology of the coloring complex
• Binomial inequalities for chromatic, flow, and tension polynomials
• Coloring complexes and combinatorial Hopf monoids
• Enumerating colorings, tensions and flows in cell complexes
• Colouring multijoints
• Properly charged coloring of two-dimensional arrays
• Coloring of lattices
• Existence of unimodular triangulations -- positive results
• Hyperoctahedral Eulerian idempotents, Hodge decompositions, and signed graph coloring complexes
• Hypergraph coloring complexes
• Multicolor Discrepancy of Arithmetic Structures
• On certain hyperplane arrangements and colored graphs
• scientific article; zbMATH DE number 6257577 (Why is no real title available?)
• Bounds on the coefficients of tension and flow polynomials
• Posets arising as 1-skeleta of simple polytopes, the nonrevisiting path conjecture, and poset topology
• Edge colored hypergraphic arrangements
• Scheduling problems

This page was built for publication: Coloring complexes and arrangements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2481072)