Results on Chromatic Polynomials Inspired by a Correlation Inequality of G.E. Farr

Graph Theory;Chromatic Polynomials;Correlation Inequality

McKay, Ghislainaffiliation1:Faculty of Mathematics ; advisor:Wagner, David ; Wagner, David ;

University of Waterloo

关键词: Correlation Inequality;    Master Thesis;    Graph Theory;    Chromatic Polynomials;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/13924/1/McKay_Ghislain.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

In1993 Graham Farr gave a proof of a correlation inequality involving colourings of graphs. His work eventually led to a conjecture that number of colourings of a graph with certain properties gave a log-concave sequence. We restate Farr's work in terms of the bivariate chromatic polynomial of Dohmen, Poenitz, Tittman and give a simple, self-contained proof of Farr's inequality using a basic combinatorial approach. We attempt to prove Farr's conjecture through methods in stable polynomials and computational verification, ultimately leading to a stronger conjecture.