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

• 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?)
• Combinatorics and commutative algebra.
• Lectures on Polytopes
• Link complexes of subspace arrangements
• Signed graph coloring
• The Broken-Circuit Complex
• The Koszul property in affine semigroup rings
• The coloring ideal and coloring complex of a graph
• The topology of the coloring complex
• Two Decompositions in Topological Combinatorics with Applications to Matroid Complexes
• g-elements, finite buildings and higher Cohen-Macaulay connectivity.

Cited in

(19)

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

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)