Coloring complexes and arrangements

DOI10.1007/S10801-007-0086-ZzbMATH Open1154.05315arXiv0706.3657OpenAlexW2008983248MaRDI QIDQ2481072FDOQ2481072

Authors: Patricia Hersh, Ed Swartz 

Publication date: 14 April 2008

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

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.

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

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

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)

Cites Work

• Lectures on Polytopes
• Signed graph coloring
• Combinatorics and commutative algebra.
• Title not available (Why is that?)
• Two Decompositions in Topological Combinatorics with Applications to Matroid Complexes
• The Broken-Circuit Complex
• Title not available (Why is that?)
• \(g\)-elements, finite buildings and higher Cohen-Macaulay connectivity.
• The Koszul property in affine semigroup rings
• The topology of the coloring complex
• The coloring ideal and coloring complex of a graph
• Link complexes of subspace arrangements
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (19)

• Hypergraph coloring complexes
• Fibres and ordered set coloring
• Title not available (Why is that?)
• Scheduling problems
• 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
• Posets arising as 1-skeleta of simple polytopes, the nonrevisiting path conjecture, and poset topology
• Enumerating colorings, tensions and flows in cell complexes
• Coloring of lattices
• Existence of unimodular triangulations -- positive results
• Properly charged coloring of two-dimensional arrays
• On certain hyperplane arrangements and colored graphs

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)