On P-unique hypergraphs

2017/12/20 by Makowsky, J. A., Zhang, R. X. · 1 citation
#05C31 #05C65 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1712.07357

Abstract

We study hypergraphs which are uniquely determined by their chromatic, independence and matching polynomials. B. Bollobás, L. Pebody and O. Riordan (2000) conjectured (BPR-conjecture) that almost all graphs are uniquely determined by their chromatic polynomials. We show that for r-uniform hypergraphs with r ≥ 3 this is almost never the case. This disproves the analolgue of the BPR-conjecture for 3-uniform hypergraphs. For r =2 this also holds for the independence polynomial, as shown by J.A. Makowsky and V. Rakita (2017), whereas for the chromatic and matching polynomial this remains open.

Cited by

• Distinctive power and comparability of Harary polynomial

Related

• Uniquely colorable hypergraphs
• Hypergraph independence polynomials with a zero close to the origin
• Uniquely K^(k)_r-saturated Hypergraphs
• Independence and Matchings in σ-hypergraphs
• 3-uniform hypergraphs and linear cycles