Ruixue Zhang, Fengming Dong^a

^aMathematics and Mathematics Education, National Institute of Education, Nanyang Technological University, Singapore 637616

fengming.dong@nie.edu.sg

Chromatic polynomials of graphs have been studied extensively for around one century. The concept of chromatic polynomial of a hypergraph is a natural extension of chromatic polynomial of a graph. It also has been studied for more than 30 years. This short article will focus on introducing some important open problems on chromatic polynomials of hypergraphs.

Keywords: graph, hypergraph, chromatic polynomial Mathematics Subject Classification : 05C15, 05C31, 05C65

DOI: 10.5614/ejgta.2020.8.2.4

1. Introduction

A hypergraph H = (V, E) consists of two finite sets V and E, where E is a subset of {e ⊆ V : |e| ≥ 2}. A hypergraph is called Sperner hypergraph when no edge is a subset of another edge.

Erdos and Hajnal [14] first extended colourings on graphs to hypergraphs. For any integer ¨ λ ≥ 1, a proper λ-colouring of H is a mapping φ : V → {1, 2, · · · , λ} such that |{φ(v) : v ∈ e}| > 1 holds for each e ∈ E. Two proper λ-colourings φ and ψ of H are regarded as distinct if φ(u) 6= ψ(u) for some vertex u in H. Let P(H, λ) be the number of proper λ-colourings of H. This function P(H, λ) is called the chromatic polynomial of H, and it is indeed a polynomial in λ of degree |V |.

Received: 16 August 2019, Revised: 4 April 2020, Accepted: 19 April 2020.

We have assumed that a hypergraph \(\mathcal{H}\) has no loops. In the case that \(\mathcal{H}\) has edges \(e_1, e_2\) with \(e_1 \subseteq e_2\), \(P(\mathcal{H}, \lambda) = P(\mathcal{H} - e_2, \lambda)\) holds by the definition of \(P(\mathcal{H}, \lambda)\), where \(\mathcal{H} - e_2\) is obtained from \(\mathcal{H}\) by removing \(e_2\). Hence we can assume that \(\mathcal{H}\) is Sperner in the function \(P(\mathcal{H}, \lambda)\).

The graph-function \(P(\mathcal{H}, \lambda)\) for a hypergraph \(\mathcal{H}\) appeared in the work of Helgason [15] in 1972, but it is unknown if it had been mentioned earlier. It has been studied extensively in the past twenty years by many researches, such as Allagan [1, 2, 3], Borowiecki and Łazuka [5, 6], Dohmen [8, 9], Drgas-Burchardt and Łazuka [13], Tomescu [19, 20, 21, 22, 23] and Walter [24]. A number of properties of chromatic polynomials of graphs related to their expressions, computations and factorizations, etc, have been extended to chromatic polynomials of hypergraphs. In this short article, we will focus on introducing some important open problems in the study of chromatic polynomials of hypergraphs which are worth for further exploring.

2. Problems on chromatic polynomials of hypergraphs

A hypergraph \(\mathcal{H}=(V,\mathcal{E})\) is said to be connected if for any two vertices u,v in \(\mathcal{H}\), \(\mathcal{H}\) has a sequence of edges \(e_1,e_2,\cdots,e_k\) such that \(u\in e_1,v\in e_k\) and \(e_i\cap e_{i+1}\neq\emptyset\) for all \(i=1,2,\cdots,k-1\). A component of \(\mathcal{H}\) is a connected sub-hypergraph \(\mathcal{H}'=(V',\mathcal{E}')\), where \(V'\subseteq V\) and \(\mathcal{E}'=\{e\in\mathcal{E}:e\subseteq V'\}\), which has the property that \(e\subseteq V'\) holds for all \(e\in\mathcal{E}\) with \(e\cap V'\neq\emptyset\).

Dohmen [8] and Tomescu [19] independently showed that \(P(\mathcal{H}, \lambda)\) is a monic polynomial of degree |V|:

\[P(\mathcal{H}, \lambda) = \sum_{i=1}^{n} \left( \sum_{j=0}^{m} (-1)^{j} N(i, j) \right) \lambda^{i}, \tag{1}\]

where \(n = |V|, m = |\mathcal{E}|\) and N(i, j) is the number of spanning sub-hypergraphs \((V, \mathcal{E}')\), where \(\mathcal{E}' \subseteq \mathcal{E}\), with i components and j edges.

Some properties on \(P(\mathcal{H}, \lambda)\) can be obtained from (1). It is obvious that \(P(\mathcal{H}, \lambda)\) is a monic polynomial with integral coefficients and has zero as its constant term. But the information on this polynomial from (1) or other results is far from enough to tell efficiently if a given polynomial is the chromatic polynomial of some hypergraph. It is natural to ask what polynomials are chromatic polynomials of hypergraphs.

Problem 1. Characterize chromatic polynomials of hypergraphs.

Two hypergraphs \(\mathcal{H}_1\) and \(\mathcal{H}_2\) are said to be isomorphic, denoted by \(\mathcal{H}_1 \cong \mathcal{H}_2\), if there exists a bijection

\[\phi:V(\mathcal{H}_1)\to V(\mathcal{H}_2)\]

such that for any subset \(e \subseteq V(\mathcal{H}_1)\), \(e \in \mathcal{E}(\mathcal{H}_1)\) if and only if \(\phi(e) \in \mathcal{E}(\mathcal{H}_2)\), where \(\phi(e) = \{\phi(v) : v \in e\}\), non-isomorphic otherwise. It is obvious that \(P(\mathcal{H}_1, \lambda) = P(\mathcal{H}_2, \lambda)\) if \(\mathcal{H}_1 \cong \mathcal{H}_2\). Two non-isomorphic hypergraphs may have the same chromatic polynomial. The problem of determining the family \(\langle \mathcal{H} \rangle = \{\mathcal{H}' : P(\mathcal{H}, \lambda) = P(\mathcal{H}', \lambda)\}\) for a given hypergraph \(\mathcal{H}\) is very difficult. Some families \(\langle \mathcal{H} \rangle\) have been confirmed in [5, 6, 19, 20, 21, 23, 24]. A hypergraph \(\mathcal{H} = (V, \mathcal{E})\) is said to be h-uniform if |e| = h holds for all \(e \in \mathcal{E}\). It is unknown if all hypergraphs in \(\langle \mathcal{H} \rangle\) are h-uniform for any given h-uniform hypergraph \(\mathcal{H}\).

Problem 2. Is it true that given any h-uniform hypergraph H, all hypergraphs in hHi are also h-uniform?

A special case is on complete h-uniform hypergraphs. A hypergraph H = (V, E) is said to be complete h-uniform of order n, denoted by Kn(h), if |V | = n and E = {e ⊆ V : |e| = h}.

Problem 3. For any integers n, h with 3 ≤ h ≤ n, is it true that hKn(h)i = {Kn(h)}?

It is well known that for any graph G of order n, P(G, λ) can be expressed as P c(G)≤i≤n aiλ i , where aⁱ is a non-zero integer for all i with c(G) ≤ i ≤ n and c(G) is the number of components of G. In other words, P(G, λ) has the property that its terms with non-zero coefficients are consecutive. However, by (1), the property does not hold for a hypergraph H = (V, E) with h = min{|e| : e ∈ E} > 2, as the coefficient of the term λ n−i in the polynomial P(H, λ) is non-zero for i = h − 1 but is zero for all i with 1 ≤ i ≤ h − 2. It is also unknown if the rest terms λ n−i (i ≥ h − 1) with non-zero coefficients are consecutive. Thus it is natural to ask what terms in the polynomial P(H, λ) have non-zero coefficients. In particular, it is interesting to know what is the minimum integer r such that the term λ r in P(H, λ) has non-zero coefficient. By the property that P(H, λ) = Q ¹≤i≤^k P(Hⁱ , λ) whenever H1, · · · , H^k are components of H, we can focus on connected hypergraphs for the above problem.

Problem 4. Let H = (V, E) be a connected hypergraph. Which terms λ i in the polynomial P(H, λ) have non-zero coefficients? In particular, what is the minimum integer i such that the term λ i in the polynomial P(H, λ) has non-zero coefficient?

It is known that the multiplicity of root '1' of P(G, λ) for a connected graph G is equal to the number of blocks of G. Is there an analogous result for hypergraphs? A hypergraph H = (V, E) is said to be separable if H has a vertex w and two proper subsets V1, V² of vertices such that V¹ ∩ V² = {w}, V¹ ∪ V² = V and for each e ∈ E, either w ∈ e or e ⊆ Vⁱ for some i.

Problem 5. For a connected hypergraph H = (V, E), what is the multiplicity of root '1' of P(H, λ)? Is it true that the multiplicity of root '1' of P(H, λ) is 1 whenever H is not separable?

It is also known that if G is a graph of order n and P(G, λ) is the polynomial P 1≤i≤n ai(G)λ i , then (−1)ⁿ−ⁱai(G) ≥ 0 holds for all i = 1, 2, · · · , n. This property implies that (−1)ⁿP(G, λ) > 0 for all negative real numbers λ and thus (−∞, 0) is a zero-free interval for chromatic polynomials of graphs. Dohmen [9] showed that this above property holds for those hypergraphs H = (V, E) such that |e| is even for each e ∈ E and each cycle in H has an edge e with |e| = 2, where a cycle in H is a sequence (v1, e1, v2, e2, . . . , vk, ek) of distinct vertices and edges such that vⁱ , vi+1 ∈ eⁱ for all i = 1, 2, · · · , k, where vk+1 = v1. But this property does not hold for all hypergraphs. Observe that if E = {V }, then P(H, λ) = λ ^{|V |} −λ, implying that P(H, λ) has negative real roots whenever |V | is odd. Thus (−∞, 0) is not a zero-free interval for chromatic polynomials of hypergraphs. However, it is unknown if there is a zero-free interval (a, b) with b ≤ 0 for chromatic polynomials of hypergraphs.

Problem 6. Is there a zero-free interval for chromatic polynomials of hypergraphs? In particular, is there a zero-free interval (a, b) within some intervals (−∞, 0) or (0, 1)?

For any graph G of order n, we have the property that G has an n-colouring and \(P(G, \lambda) > 0\) holds for all real \(\lambda > n-1\). For a hypergraph \(\mathcal{H} = (V, \mathcal{E})\) with |V| = n and \(h = \min\{|e| : e \in \mathcal{E}\}\), \(\mathcal{H}\) has a (|V| - h + 2)-colouring. But it is unknown if \(P(\mathcal{H}, \lambda) > 0\) holds for all real \(\lambda > |V| - h + 1\).

Problem 7. For a hypergraph \(\mathcal{H} = (V, \mathcal{E})\) with |V| = n and \(h = \min\{|e| : e \in \mathcal{E}\}\), is it true that \(P(\mathcal{H}, \lambda) > 0\) holds for all real \(\lambda > |V| - h + 1\)?

The shameful conjecture on chromatic polynomials of graphs was proposed by Bartels and Welsh [4] in 1995: for any graph G of order n, the following inequality holds:

\[\frac{P(G,n)}{P(G,n-1)} \ge e,\tag{2}\]

where e is the base of natural logarithms.

This conjecture was finally proved by Dong [11] in 2000. Actually, Dong got a stronger result that, for any graph G of order n, the inequality \(\frac{P(G,\lambda)}{P(G,\lambda-1)} \geq \frac{\lambda^n}{(\lambda-1)^n}\) holds for all real \(\lambda \geq n\). We guess this result can be extended to hypergraphs.

Problem 8. Let \(\mathcal{H} = (V, \mathcal{E})\) be a hypergraph with |V| = n. Does the following inequality

\[\frac{P(\mathcal{H}, \lambda)}{P(\mathcal{H}, \lambda - 1)} \ge \frac{\lambda^n}{(\lambda - 1)^n}\]

hold for all real \(\lambda \geq n\)?

Welsh in 1970s and Brenti [7] in 1992 conjectured that for any graph G, \(P(G,k)^2 \ge P(G,k+1)P(G,k-1)\) holds for all integers \(k \ge 1\). However, Seymour [18] found some graphs G with sufficiently large order such that \(P(G,6)^2 < P(G,7)P(G,5)\) holds. But it is still unknown if this conjecture holds for integers \(k \ge n-1\). It has been proposed in [10] that \(P(G,\lambda)^2 \ge P(G,\lambda+1)P(G,\lambda-1)\) holds for all real numbers \(\lambda \ge |V(G)|-1\). We also believe that this conjecture also holds for hypergraphs.

Problem 9. For any hypergraph \(\mathcal{H} = (V, \mathcal{E})\) with |V| = n, does the following inequality

\[P(\mathcal{H}, \lambda)^2 \ge P(\mathcal{H}, \lambda - 1)P(\mathcal{H}, \lambda + 1)\]

holds for all real numbers \(\lambda \geq n-1\)?

Lundow and Markström [16] conjectured that \(\frac{P'(G,-1)}{P(G,-1)} < \frac{P'(K_n,-1)}{P(K_n,-1)}\) holds for any connected graph G which is not complete, where P'(G,-1) is the value of \(\frac{\mathrm{d}(P(G,\lambda))}{\mathrm{d}\lambda}\) at \(\lambda=-1\). This conjecture was recently proved to be true [12]. We think this conjecture can be extended to h-uniform hypergraphs.

Problem 10. For any connected h-uniform hypergraph \(\mathcal{H} = (V, \mathcal{E})\) with |V| = n and \(\mathcal{H} \ncong K_n(h)\), does the following inequality hold

\[\frac{P'(\mathcal{H}, -1)}{P(\mathcal{H}, -1)} < \frac{P'(K_n(h), -1)}{P(K_n(h), -1)}?\]

References

• [1] J.A. Allagan, The chromatic polynomials of some linear uniform hypergraphs, Congr. Numer. 187 (2007), 156–160.
• [2] J.A. Allagan, Chromatic polynomials of some (m, l)-hyperwheels, Comput. Sci. J. Moldova 22 (2014), 64.
• [3] J.A. Allagan and S. David, Chromatic polynomials of some mixed hypergraphs, Australas. J. Combin. 58 (2014), 197–213.
• [4] J.E. Bartels and D.J. Welsh, The Markov chain of colourings, in Proceedings of the Fourth Conference on Integer Programming and Combinatorial Optimisation 920 (1995), 373-387.
• [5] M. Borowiecki and E. Łazuka, Chromatic polynomials of hypergraphs, Discuss. Math. Graph Theory 20 (2000), 293–301.
• [6] M. Borowiecki and E. Łazuka, On chromaticity of hypergraphs, Discrete Math. 307 (2007), 1418–1429.
• [7] F. Brenti, Expansions of chromatic polynomials and log-concavity, Trans. Amer. Math. Soc. 332 (1992), 729–756.
• [8] K. Dohmen, Chromatische polynome von graphen und hypergraphen, Universitat D ¨ usseldorf ¨ (1993).
• [9] K. Dohmen, A broken-circuits-theorem for hypergraphs Arch. Math. 64 (1995), 159–162.
• [10] F.M. Dong, K.M. Koh and K.L. Teo, Chromatic Polynomials and Chromaticity of Graphs, World Scientific, Singapore (2005).
• [11] F.M. Dong, Proof of a chromatic polynomial conjecture J. Combin. Theory Ser. B 78 (2000), 35–74.
• [12] F.M. Dong, J. Ge, H. Gong, B. Ning, Z. Ouyang and E.G. Tay, Proof of Lundow and Markstrom's conjecture on chromatic polyomials via novel inequalities, ¨ arXiv preprint arXiv:1803.08658 (2018).
• [13] E. Drgas-Burchardt and E. Łazuka, Chromatic polynomials of hypergraphs, Applied Mathematics Letters 20 (2007), 1250–1254.
• [14] P. Erdos and A. Hajnal, On chromatic number of graphs and set-systems, ˝ Acta Math. Acad. Sci. Hungar. 1966 (17), 61–99.
• [15] T. Helgason, Aspects of the theory of hypermatroids, Hypergraph Seminar, Ohio State University 1972, Lecure Notes in Mathematics, C. Berge and D. Ray-Chaudhuri, eds., Springer-Verlag 411 (1974), 191–213.

• [16] P.H. Lundow and K. Markstrom, Broken-cycle-free subgraphs and the log-concavity conjec- ¨ ture for chromatic polynomials, Experiment. Math. 15 (2006), 343–353.
• [17] R.C. Read, An introduction to chromatic polynomials, J. Combin. Theory 4 (1968), 52–71.
• [18] P. Seymour, Two chromatic polynomial conjectures, J. Combin. Theory Ser. B 70 (1997), 184–196.
• [19] I. Tomescu, Chromatic coefficients of linear uniform hypergraphs, J. Combin. Theory Ser. B 260 (1998), 229–235.
• [20] I. Tomescu, Sunflower hypergraphs are chromatically unique, Discrete Math. 285 (2004), 355–357.
• [21] I. Tomescu, On the chromaticity of sunflower hypergraphs SH(n, p, h), Discrete Math. 307 (2007), 781–788.
• [22] I. Tomescu, Some properties of chromatic coefficients of linear uniform hypergraphs, Graphs and Combin. 25 (2009), 639–646.
• [23] I. Tomescu, Hypergraphs with pendant paths are not chromatically unique, Discuss. Math. Graph Theory 34 (2014), 23-29.
• [24] M. Walter, Some results on chromatic polynomials of hypergraphs, Electron. J. Combin. 16 (2009), R94.