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

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

Authors: Ruixue Zhang, F. M. Dong 

Publication date: 23 June 2017

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

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$.

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

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

zbMATH Keywords

totally cyclic orientations of a graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Zero-free intervals of chromatic polynomials of hypergraphs
• Title not available (Why is that?)
• On P-unique hypergraphs
• Counting Candy Crush configurations
• Comparing list-color functions of uniform hypergraphs with their chromatic polynomials. II
• More connections between the matching polynomial and the chromatic polynomial

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)