{"id":1301,"date":"2015-04-06T22:02:34","date_gmt":"2015-04-07T02:02:34","guid":{"rendered":"http:\/\/matroidunion.org\/?p=1301"},"modified":"2015-04-07T02:03:07","modified_gmt":"2015-04-07T06:03:07","slug":"chromatic-polynomials-i","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=1301","title":{"rendered":"Chromatic polynomials I"},"content":{"rendered":"

At the beginning of this year I started a new postdoc, still at the University of Western Australia and still with Gordon Royle, but on a new project, which is titled “Real chromatic roots of graphs and matroids”. That is, real roots of the chromatic polynomial of graphs and matroids. Since its first definition by Birkhoff in 1912, the chromatic polynomial has received much attention, not only by the mathematical community, but also, for example, by physicists. There are lots of interesting results and yet more interesting open problems in the area, and since I’m now navigating the extensive literature I decided to write a series of posts on the subject. I will mostly follow the notation of Gordon Royle’s excellent survey on chromatic and flow roots [R09].<\/span><\/p>\n

Let’s start with a bit of history and some basic definitions. The chromatic polynomial (for planar graphs) was first defined by Birkhoff in an attempt to find an algebraic proof of the then open four-colour problem. The\u00a0chromatic polynomial<\/b>\u00a0$P(G,q)$ of a graph $G$ counts,\u00a0for every positive integer $q$, the number of proper colouring of the vertices of $G$ with $q$ colours. One can easily check that, if $e$ is an edge of $G$, then \\[P(G, q)=P(G\\backslash e, q)-P(G\/e, q).\\] In fact, the number of $q$-colouring of $G$ is equal to the number of $q$-colouring of $G\\backslash e$ where the endpoints of $e$ receive distinct colours and $P(G\/e,q)$ counts the number of $q$-colourings of $G \\backslash e$ where the endpoints of $e$ receive the same colour. The above formula is called the\u00a0deletion-contraction<\/strong> formula and from it one can easily deduce that $P(G,q)$ is indeed a polynomial. One can also see that this is the case by showing directly that $P(G,q)$ is a sum of polynomials, as in the next lemma.<\/span><\/p>\n

Lemma 1:<\/strong>\u00a0For every graph $G$, \\[P(G,q)=\\sum_{X\\subseteq E(G)}(-1)^{|X|}q^{k(X)},\\] where $k(X)$ is the number of components of the graph induced by $X$.<\/span><\/p>\n

proof:\u00a0<\/strong>Let us consider colourings (not necessarily proper ones) of $V(G)$ with $q$ colours; there are $q^{|V(G)|}$ of them. For every $e \\in E(G)$, denote by $B_e$ the set of colourings where the endpoints of $e$ receive the same colour.\u00a0Then \\[P(G,q)=q^{|V(G)|}-|\\cup_{e\\in E(G)}B_e|.\\] Also note that \\[|\\cap_{e\\in X}B_e|=q^{k(X)}.\\] Now the result follows from applying the inclusion-exclusion principle to the first equality and using the second equality.$\\qquad \\Box$<\/span><\/p>\n

Since the chromatic polynomial can be evaluated at real and complex values, Birkhoff hoped to use analytic methods to prove the 4-colour conjecture. In fact, the four-colour Theorem is equivalent to stating that $P(G,4)>0$ for all planar graphs $G$, i.e. 4 is not a chromatic root of any planar graph. As we know, such an analytic proof was never found, but\u00a0Birkhoff and Lewis [BL46] did show that if $G$ is planar then $P(G,q)>0$ for all real<\/em> $q\\geq 5$. They conjectured that 5 could be changed to 4, and almost 70 years later their\u00a0conjecture is still open.<\/span><\/p>\n

Conjecture 2 (Birkhoff-Lewis, 1946).\u00a0<\/strong>If $G$ is a planar graph, then $P(G,q)>0$ for all real $q \\geq 4$.<\/span><\/p>\n

The Birkhoff-Lewis conjecture motivated the study of real chromatic roots of graphs, with\u00a0special attention to finding lower and upper bounds on them. A real interval $(a,b)$ is a\u00a0root-free interval\u00a0<\/strong>for a family of graphs $\\mathcal{G}$ if no graph in $\\mathcal{G}$ has a chromatic root (i.e. a root of its chromatic polynomial) in the interval $(a,b)$.<\/span><\/p>\n

The chromatic polynomial of a graph $G$ with $n$ vertices may be expressed as \\[P(G,q)=\\sum_{i=1}^n (-1)^{n-i}h_iq^i,\\] where $h_i \\in \\mathbb{N}$ for all $i=1,\\ldots,n$ and $h_n=1$. From this one can easily\u00a0deduce that $(-1)^nP(G,q)>0$ for all real $q<0$, thus the interval $(-\\infty,0)$ is a root-free interval for all graphs. With a bit more work (considering forests first, then using induction and the deletion-contraction formula) one can also show that $(-1)^{n-k(G)}P(G,q)>0$ for all real $q \\in (0,1)$. A much less trivial result, due to Jackson [J93] gives the following surprising root-free interval.<\/span><\/p>\n

Theorem 3 (Jackson\u00a0[J93]).\u00a0<\/strong>Let $G$ be a connected graph with $n\\geq 2$ vertices and $b$ blocks. Then $(-1)^{n+b+1}P(G,q)>0$ for all real $q \\in (1,32\/27]$.<\/span><\/p>\n

What is especially surprising about this result is the fact that this interval is best possible, in \u00a0the following sense.<\/span><\/p>\n

Theorem 4 (Thomassen, [T97]).\u00a0<\/strong>For all\u00a0real numbers $a,b$ with $32\/27<a<b$, there exists a graph $G$ that has a chromatic root in $[a,b]$.<\/span><\/p>\n

What about largest<\/em> real roots? A family of graphs $\\mathcal{G}$ has an\u00a0upper root-free interval<\/strong> if there is a real number $a$ such that no graph in\u00a0$\\mathcal{G}$ has a real root larger than $a$. The class of all graphs does not have an upper root-free interval (since you can get arbitrarily large chromatic roots from cliques). Restricting our attention to bipartite graphs, the situation does not improve.<\/span><\/p>\n

Theorem 5 (Woodall [W77]).\u00a0<\/strong>If $n$ is sufficiently large compared to $m$, then the complete bipartite graph $K_{m,n}$ has real chromatic roots arbitrarily close to all integers in $[2,m\/2]$.<\/span><\/p>\n

However, the situation is quite different when\u00a0we consider proper minor-closed classes of graphs instead. This is because graphs in a proper minor-closed class must have a vertex of “small” degree.\u00a0<\/span><\/p>\n

Theorem 6 (Mader [M67]).\u00a0<\/strong>For every $k \\in \\mathbb{N}$ there exists an integer $f(k)$ such that any graph with minimum degree at least $f(k)$ has a $K_k$-minor.<\/span><\/p>\n

It follows that, for every proper minor-closed family of graphs $\\mathcal{G}$, there exists a smallest integer\u00a0$d=d(\\mathcal{G})$ such that every graph in $\\mathcal{G}$ has a vertex of degree at most $d$. Woodall and Thomassen proved the next result independently.<\/span><\/p>\n

Theorem 7 (Thomassen [T97], Woodall [W97]).\u00a0<\/strong>If\u00a0$\\mathcal{G}$ is\u00a0a proper minor-closed family of graphs, then $(d(\\mathcal{G}),\\infty)$ is an upper root-free interval for $\\mathcal{G}$.<\/span><\/p>\n

In the next post I’ll talk about complex chromatic roots and then move on to matroids.<\/span><\/p>\n

References:<\/strong><\/h1>\n

[BL46]\u00a0G.D.\u00a0Birkhoff, D.C.\u00a0Lewis,\u00a0Chromatic polynomials<\/span><\/em>.<\/span>\u00a0Trans. Amer. Math. Soc.<\/em><\/a>\u00a060,\u00a0<\/strong>(1946). 355\u2013451.<\/span><\/p>\n

[J93] B.\u00a0Jackson,<\/span>\u00a0A zero-free interval for chromatic polynomials of graphs<\/span><\/em>.<\/span>\u00a0<\/span>Combin. Probab. Comput.<\/a>\u00a02\u00a0<\/a>(1993),\u00a0<\/a>no. 3,<\/a>\u00a0325\u2013336.<\/span><\/p>\n

[R09] G.F. Royle,\u00a0Recent results on chromatic and flow roots of graphs and matroids<\/em>.<\/span>\u00a0Surveys in combinatorics 2009,\u00a0289\u2013327,\u00a0London Math. Soc. Lecture Note Ser., 365,<\/a>\u00a0Cambridge Univ. Press, Cambridge,\u00a02009.<\/span><\/p>\n

[T97]\u00a0Thomassen, Carsten,\u00a0The zero-free intervals for chromatic polynomials of graphs<\/span><\/em>.\u00a0<\/span>Combin. Probab. Comput.\u00a06\u00a0(1997),\u00a0no. 4,<\/a>\u00a0497\u2013506.<\/span><\/p>\n

[W77]\u00a0D.R. Woodall,\u00a0Zeros of chromatic polynomials<\/span><\/em>.<\/span>\u00a0Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Royal Holloway College, Egham, 1977),\u00a0pp. 199\u2013223.\u00a0Academic Press, London,\u00a01977.<\/span><\/p>\n

[W97]\u00a0D.R. Woodall,\u00a0The largest real zero of the chromatic polynomial<\/span>.<\/span><\/em>\u00a0Discrete Math.\u00a0172\u00a0(1997),\u00a0no. 1-3,\u00a0141\u2013153.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

At the beginning of this year I started a new postdoc, still at the University of Western Australia and still with Gordon Royle, but on a new project, which is titled “Real chromatic roots of graphs and matroids”. That is, … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1301","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1301","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1301"}],"version-history":[{"count":60,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1301\/revisions"}],"predecessor-version":[{"id":1362,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1301\/revisions\/1362"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1301"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1301"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1301"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}