Properties of chromatic polynomials of hypergraphs not held for chromatic polynomials of graphs

DOI10.1016/J.EJC.2017.04.006zbMATH Open1365.05140OpenAlexW2607325709MaRDI QIDQ2359983FDOQ2359983

Authors Ruixue Zhang, F. M. Dong

Publication date 23 June 2017

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

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

zbMATH Keywords

totally cyclic orientations of a graph

Mathematics Subject Classification ID

Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Abstract: In this paper, we present some properties on chromatic polynomials of hypergraphs which do not hold for chromatic polynomials of graphs. We first show that chromatic polynomials of hypergraphs have all integers as their zeros and contain dense real zeros in the set of real numbers. We then prove that for any multigraph $G=(V,E)$, the number of totally cyclic orientations of $G$ is equal to the value of $|P(H,-1)|$, where $P(H,lambda)$ is the chromatic polynomial of a hypergraph $H$ which is constructed from $G$. Finally we show that the multiplicity of root "$0$" of $P(H,lambda)$ may be at least $2$ for some connected hypergraphs $H$, and the multiplicity of root "$1$" of $P(H,lambda)$ may be $1$ for some connected and separable hypergraphs $H$ and may be $2$ for some connected and non-separable hypergraphs $H$.

Recommendations

• Zero-free intervals of chromatic polynomials of hypergraphs
• Some results on chromatic polynomials of hypergraphs
• Series-parallel chromatic hypergraphs
• On chromatic polynomials of hypergraphs
• Problems on chromatic polynomials of hypergraphs

Cites work

• scientific article; zbMATH DE number 4091530 (Why is no real title available?)
• scientific article; zbMATH DE number 3468904 (Why is no real title available?)
• scientific article; zbMATH DE number 3556126 (Why is no real title available?)
• scientific article; zbMATH DE number 1369835 (Why is no real title available?)
• scientific article; zbMATH DE number 2199828 (Why is no real title available?)
• scientific article; zbMATH DE number 5237267 (Why is no real title available?)
• scientific article; zbMATH DE number 3394158 (Why is no real title available?)
• scientific article; zbMATH DE number 3402652 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• A Zero-Free Interval for Chromatic Polynomials of Graphs
• A broken-circuits-theorem for hypergraphs
• Acyclic orientations of graphs
• An introduction to chromatic polynomials
• Chromatic Polynomials
• Chromatic Roots are Dense in the Whole Complex Plane
• Chromatic coefficients of linear uniform hypergraphs
• Chromatic polynomials of hypergraphs
• Chromatic polynomials of some \((m,l)\)-hyperwheels
• Chromatic polynomials of some mixed hypergraphs
• Coloring \(d\)-embeddable \(k\)-uniform hypergraphs
• Coloring mixed hypergraphs: theory, algorithms and applications
• Computing Graph Polynomials on Graphs of Bounded Clique-Width
• Cutpoints and the chromatic polynomial
• Every Planar Map is Four Colorable
• Graph polynomials and their applications. I: The Tutte polynomial
• HYPERGRAPHS
• Hypergraph planarity and the complexity of drawing venn diagrams
• Hypergraphs and Ramseyian Theorems
• Hypergraphs with pendant paths are not chromatically unique
• Log-concavity of characteristic polynomials and the Bergman fan of matroids
• Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• On the location of roots of independence polynomials
• Some properties of chromatic coefficients of linear uniform hypergraphs
• Some results on chromatic polynomials of hypergraphs
• Sunflower hypergraphs are chromatically unique
• The Zero-Free Intervals for Chromatic Polynomials of Graphs
• The four-colour theorem
• The roots of the independence polynomial of a clawfree graph

Cited in

(6)

• Zero-free intervals of chromatic polynomials of hypergraphs
• Counting Candy Crush configurations
• More connections between the matching polynomial and the chromatic polynomial
• A new polynomial for polymatroids
• Comparing list-color functions of uniform hypergraphs with their chromatic polynomials. II
• On \(P\)-unique hypergraphs

This page was built for publication: Properties of chromatic polynomials of hypergraphs not held for chromatic polynomials of graphs

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