Problems on chromatic polynomials of hypergraphs

Ruixue Zhang, Fengming Dong

Abstract


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 prblems on chromatic polynomials of hypergraphs.


Keywords


graph, hypergraph, chromatic polynomial

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2020.8.2.4

References

J.A. Allagan, The chromatic polynomials of some linear uniform hypergraphs, Congr. Numer. 187 (2007), 156–160.

J.A. Allagan, Chromatic polynomials of some (m, l)-hyperwheels, Comput. Sci. J. Moldova 22 (2014), 64.

J.A. Allagan and S. David, Chromatic polynomials of some mixed hypergraphs, Australas. J. Combin. 58 (2014), 197–213.

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.

M. Borowiecki and E. Łazuka, Chromatic polynomials of hypergraphs, Discuss. Math. Graph Theory 20 (2000), 293–301.

M. Borowiecki and E. Łazuka, On chromaticity of hypergraphs, Discrete Math. 307 (2007), 1418–1429.

F. Brenti, Expansions of chromatic polynomials and log-concavity, Trans. Amer. Math. Soc. 332 (1992), 729–756.

K.Dohmen, Chromatische polynomevon graphen und hypergraphen, Universita ̈t Du ̈sseldorf (1993).

K. Dohmen, A broken-circuits-theorem for hypergraphs Arch. Math. 64 (1995), 159–162.

F.M. Dong, K.M. Koh and K.L. Teo, Chromatic Polynomials and Chromaticity of Graphs, World Scientific, Singapore (2005).

F.M. Dong, Proof of a chromatic polynomial conjecture J. Combin. Theory Ser. B 78 (2000), 35–74.

F.M. Dong, J. Ge, H. Gong, B. Ning, Z. Ouyang and E.G. Tay, Proof of Lundow and Markstro ̈m’s conjecture on chromatic polyomials via novel inequalities, arXiv preprint arXiv:1803.08658 (2018).

E. Drgas-Burchardt and E. Łazuka, Chromatic polynomials of hypergraphs, Applied Mathe- matics Letters 20 (2007), 1250–1254.

P. Erdo ̋s and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 1966 (17), 61–99.

T. Helgason, Aspects of the theory of hypermatroids, Hypergraph Seminar, Ohio State Uni- versity 1972, Lecure Notes in Mathematics, C. Berge and D. Ray-Chaudhuri, eds., Springer- Verlag 411 (1974), 191–213.

P.H. Lundow and K. Markstro ̈m, Broken-cycle-free subgraphs and the log-concavity conjecture for chromatic polynomials, Experiment. Math. 15 (2006), 343–353.

R.C. Read, An introduction to chromatic polynomials, J. Combin. Theory 4 (1968), 52–71.

P. Seymour, Two chromatic polynomial conjectures, J. Combin. Theory Ser. B 70 (1997), 184–196.

I. Tomescu, Chromatic coefficients of linear uniform hypergraphs, J. Combin. Theory Ser. B 260 (1998), 229–235.

I. Tomescu, Sunflower hypergraphs are chromatically unique, Discrete Math. 285 (2004), 355–357.

I. Tomescu, On the chromaticity of sunflower hypergraphs SH(n, p, h), Discrete Math. 307 (2007), 781–788.

I.Tomescu, Some properties of chromatic coefficients of linear uniform hypergraphs, Graphs and Combin. 25 (2009), 639–646.

I. Tomescu, Hypergraphs with pendant paths are not chromatically unique, Discuss. Math. Graph Theory 34 (2014), 23-29.

M. Walter, Some results on chromatic polynomials of hypergraphs, Electron. J. Combin. 16 (2009), R94.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats