An algebraic formulation of hypergraph colorings

DOI10.37236/9894MaRDI QIDQ6106296zbMATH OpenOpenAlexFDO

Authors Michael Krul, Luboš Thoma

Publication date 27 June 2023

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/9894

zbMATH Keywords

algebraic algorithmGröbner bases

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Commutative rings defined by monomial ideals; Stanley-Reisner face rings; simplicial complexes (13F55) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Review text

Summary: A hypergraph is properly vertex-colored if no edge contains vertices which are assigned the same color. We provide an algebraic formulation of the \(k\)-colorability of uniform and non-uniform hypergraphs. This formulation provides an algebraic algorithm, via Gröbner bases, which can determine whether a given hypergraph is \(k\)-colorable or not. We further study new families of \(k\)-colorings with additional restrictions on permissible colorings. These new families of colorings generalize several recently studied variations of \(k\)-colorings.

Recommendations

• Colorings of hypergraphs
• A general framework for hypergraph coloring
• Chromatic numbers of algebraic hypergraphs
• ON HYPERGRAPH COLOURINGS
• DECIDING THE CHROMATIC NUMBERS OF ALGEBRAIC HYPERGRAPHS
• A geometric theory of hypergraph colouring
• scientific article; zbMATH DE number 5202627
• Deterministic Hypergraph Coloring and Its Applications
• scientific article; zbMATH DE number 1301963
• Hypergraph colouring

Cites work

• 2-colorability of \(r\)-uniform hypergraphs
• Algebraic characterization of uniquely vertex colorable graphs
• Color-bounded hypergraphs, III: model comparison
• Color-bounded hypergraphs. I: General results
• Coloring Geometric Range Spaces
• Coloring mixed hypergraphs: theory, algorithms and applications
• Colorings and orientations of graphs
• Combinatorial Nullstellensatz
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Expressing combinatorial problems by systems of polynomial equations and Hilbert's Nullstellensatz
• Graph theory
• Gröbner bases and graph colorings
• scientific article; zbMATH DE number 1206418 (Why is no real title available?)
• scientific article; zbMATH DE number 1970438 (Why is no real title available?)
• scientific article; zbMATH DE number 967945 (Why is no real title available?)
• Mixed hypergraphs and beyond
• On variants of conflict-free-coloring for hypergraphs
• Pattern hypergraphs
• Powers of Square-Free Monomial Ideals and Combinatorics
• Recognizing graph theoretic properties with polynomial ideals
• Stable sets and polynomials

Cited in

(2)

• Efficient formula of the colored Kauffman brackets
• The Chemist Cabinet Puzzle: A Polynomial Approach

This page was built for publication: An algebraic formulation of hypergraph colorings

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