Search

Associated to any finite simple graph $\Gamma$ is the chromatic polynomial $P_\Gamma(q)$ whose complex zeroes are called the chromatic zeros of $\Gamma$. A hierarchical lattice is a sequence of finite simple graphs $\{\Gamma_n\}_{n=0}^\infty$ built recursively using a substitution rule expressed in terms of a generating graph. For each $n$, let $\mu_n$ denote the probability measure that assigns a Dirac measure to each chromatic zero of $\Gamma_n$. Under a mild hypothesis on the generating graph, we prove that the sequence $\mu_n$ converges to some measure $\mu$ as $n$ tends to infinity. We call $\mu$ the limiting measure of chromatic zeros associated to $\{\Gamma_n\}_{n=0}^\infty$. In the case of the Diamond Hierarchical Lattice we prove that the support of $\mu$ has Hausdorff dimension two. The main techniques used come from holomorphic dynamics and more specifically the theories of activity/bifurcation currents and arithmetic dynamics. We prove a new equidistribution theorem that can be used to relate the chromatic zeros of a hierarchical lattice to the activity current of a particular marked point. We expect that this equidistribution theorem will have several other applications.

We define the acyclic orientation polynomial of a graph to be the generating function for the sinks of its acyclic orientations. Stanley proved that the number of acyclic orientations is equal to the chromatic polynomial evaluated at $-1$ up to sign. Motivated by this link between acyclic orientations and the chromatic polynomial, we develop "acyclic orientation" analogues of theorems concerning the chromatic polynomial of Birkhoff, Whitney, and Greene-Zaslavsky. As an application, we provide a new proof for Stanley's sink theorem for chromatic symmetric functions $X_G$. This theorem gives a relation between the number of acyclic orientations with a fixed number of sinks and the coefficients in the expansion of $X_G$ with respect to elementary symmetric functions., Comment: 21 pages, 4 figures

A famous and wide-open problem, going back to at least the early 1970s, concerns the classification of chromatic polynomials of graphs. Toward this classification problem, one may ask for necessary inequalities among the coefficients of a chromatic polynomial, and we contribute such inequalities when a chromatic polynomial $$\chi _G(n)=\chi ^*_0\left( {\begin{array}{c}n+d\\ d\end{array}}\right) +\chi ^*_1\left( {\begin{array}{c}n+d-1\\ d\end{array}}\right) +\dots +\chi ^*_d\left( {\begin{array}{c}n\\ d\end{array}}\right) $$ is written in terms of a binomial-coefficient basis. For example, we show that $$\chi ^*_j\le \chi ^*_{d-j}$$ , for $$0\le j\le d/2$$ . Similar results hold for flow and tension polynomials enumerating either modular or integral nowhere-zero flows/tensions of a graph. Our theorems follow from connections among chromatic, flow, tension, and order polynomials, as well as Ehrhart polynomials of lattice polytopes that admit unimodular triangulations. Our results use Ehrhart inequalities due to Athanasiadis and Stapledon and are related to recent work by Hersh–Swartz and Breuer–Dall, where inequalities similar to some of ours were derived using algebraic-combinatorial methods.

The chromatic polynomial $P(G,x)$ of a graph $G$ of order $n$ can be expressed as $\sum\limits_{i=1}^n(-1)^{n-i}a_{i}x^i$, where $a_i$ is interpreted as the number of broken-cycle free spanning subgraphs of $G$ with exactly $i$ components. The parameter $\epsilon(G)=\sum\limits_{i=1}^n (n-i)a_i/\sum\limits_{i=1}^n a_i$ is the mean size of a broken-cycle-free spanning subgraph of $G$. In this article, we confirm and strengthen a conjecture proposed by Lundow and Markstr\"{o}m in 2006 that $\epsilon(T_n)< \epsilon(G), Comment: 20 pages, 23 references. To appear in J. Graph Theory

The complex roots of the chromatic polynomial $$P_{G}(x)$$ of a graph G have been well studied, but the p-adic roots have received no attention as yet. We consider these roots, specifically the roots in the ring $$\mathbb{Z}_p$$ of p-adic integers. We first describe how the existence of p-adic roots is related to the p-divisibility of the number of colourings of a graph—colourings by at most k colours and also ones by exactly k colours. Then we turn to the question of the circumstances under which $$P_{G}(x)$$ splits completely over $$\mathbb{Z}_p$$, giving some generalities before considering in detail an infinite family of graphs whose chromatic polynomials have been discovered, by Morgan (LMS J Comput Math 15, 281–307, 2012), to each have a cubic abelian splitting field.

The connection between the matching polynomial and the chromatic polynomial for triangle-free graphs was revealed in the work of Farrell and Whitehead. We extend this result to all graph by mirroring the corresponding result of Godsil and Gutman for the acyclic polynomial and the characteristic polynomial. We also reintroduce the clique polynomial of Farrell as an evaluation of the U-polynomial of Noble and Welsh, which also happens to contain the matching and chromatic polynomials. Keywords: Matching polynomial, Chromatic polynomial, F-polynomial, U-polynomial

Let G be a threshold graph. In this paper, we give, in first hand, a formula relating the chromatic polynomial of Ḡ (the complement of G) to the chromatic polynomial of G. In second hand, we express the chromatic polynomials of G and Ḡ in terms of the generalized Bell polynomials.

Let m , n , λ be positive integers. What is the maximum number of proper vertex colorings in (at most) λ colors a graph with n vertices and m edges can have? On which graphs is this maximum attained? The question can be rephrased as the one of maximizing χ ( G , λ ) , the value of the chromatic polynomial of G at λ , over all graphs G with n vertices and m edges. This problem was stated independently by Wilf and Linial, and is still unsolved. In this article we survey the current state of the research directed at solving the problem.

For an undirected graph G , the chromatic polynomial is a key specialisation of its Tutte polynomial. The “ ( α + n ) -conjecture” states that given any algebraic integer α , for large enough n ∈ N the shifted value α + n is the root of some chromatic polynomial. We develop an algorithm whose input is a monic polynomial P d ( X ) ∈ Z [ X ] of degree d ≤ 4 , and the output is a ( d , N ) -biclique whose chromatic polynomial is a product of linear factors and the factor P d ( X − n ) where n ∈ N is taken to be sufficiently large, provided that such a ( d , N ) -biclique exists. In degree d = 3 our method tends to produce smaller ( 3 , N ) -bicliques than Adam Bohn’s cubic parameterisation (Bohn, 2014), while in degree d = 4 it provides an efficient way to check the ( α + n ) -conjecture for a given quartic polynomial. The construction relies on previous work of Farrell (1980) which interprets chromatic coefficients via induced subgraphs, together with a simple search algorithm that is based on the number of ways to partition an integer. We also derive new expressions for the interesting factors of the chromatic polynomials for ( 3 , N ) -bicliques and ( 4 , N ) -bicliques, in terms of these induced subgraphs.

We introduce the notion of a delta-matroid perspective. A delta-matroid perspective consists of a triple ( M , D , N ) , where M and N are matroids and D is a delta-matroid such that there are strong maps from M to the upper matroid of D and from the lower matroid of D to N . We describe two Tutte-like polynomials that are naturally associated with delta-matroid perspectives and determine various properties of them. Furthermore, we show when the delta-matroid perspective is read from a graph in a surface our polynomials coincide with B. Bollobas and O. Riordan's ribbon graph polynomial and the more general Krushkal polynomial of graphs in surfaces. This is analogous to the fact that the Tutte polynomial of a graph G coincides with the Tutte polynomial of its cycle matroid. We use this new framework to prove results about the topological graph polynomials that cannot be realised in the setting of cellularly embedded graphs.

The partition lattice and noncrossing partition lattice are well studied objects in combinatorics. Given a graph $G$ on vertex set $\{1,2,\dots, n\}$, its bond lattice, $L_G$, is the subposet of the partition lattice formed by restricting to the partitions whose blocks induce connected subgraphs of $G$. In this article, we introduce a natural noncrossing analogue of the bond lattice, the noncrossing bond poset, $NC_G$, obtained by restricting to the noncrossing partitions of $L_G$. Both the noncrossing partition lattice and the bond lattice have many nice combinatorial properties. We show that, for several families of graphs, the noncrossing bond poset also exhibits these properties. We present simple necessary and sufficient conditions on the graph to ensure the noncrossing bond poset is a lattice. Additionally, for several families of graphs, we give combinatorial descriptions of the M\"obius function and characteristic polynomial of the noncrossing bond poset. These descriptions are in terms of a noncrossing analogue of non-broken circuit (NBC) sets of the graphs and can be thought of as a noncrossing version of Whitney's NBC theorem for the chromatic polynomial. We also consider the shellability and supersolvability of the noncrossing bond poset, providing sufficient conditions for both. We end with some open problems., Comment: 40 pages, 13 figures

DP-coloring is a generalization of list coloring that was introduced in 2015 by Dvo\v{r}\'{a}k and Postle. The chromatic polynomial of a graph is a notion that has been extensively studied since the early 20th century. The chromatic polynomial of graph $G$ is denoted $P(G,m)$, and it is equal to the number of proper $m$-colorings of $G$. In 2019, Kaul and Mudrock introduced an analogue of the chromatic polynomial for DP-coloring; specifically, the DP color function of graph $G$ is denoted $P_{DP}(G,m)$. Two fundamental questions posed by Kaul and Mudrock are: (1) For any graph $G$ with $n$ vertices, is it the case that $P(G,m)-P_{DP}(G,m) = O(m^{n-3})$ as $m \rightarrow \infty$? and (2) For every graph $G$, does there exist $p,N \in \mathbb{N}$ such that $P_{DP}(K_p \vee G, m) = P(K_p \vee G, m)$ whenever $m \geq N$? We show that the answer to both these questions is yes. In fact, we show the answer to (2) is yes even if we require $p=1$., Comment: 13 pages. arXiv admin note: text overlap with arXiv:1904.07697

We study tension–flows ( f , g ) on a graph G (where f is a tension and g is a flow) of the following types: nowhere-zero, product-zero everywhere, and complementary. Counting the number of tension–flows of the three types over modulo integer pairs ( p , q ) results in polynomial functions of two variables p and q . It turns out that the two-variable polynomial of the complementary case is dual to the Tutte polynomial, in the sense that the former counts the number of lattice points inside certain open lattice polytopes while the latter counts the number of lattice points inside the corresponding closed lattice polytopes. Other than counting over modulo integer pairs, we further consider enumeration of tension–flows over finitely generated abelian groups and over the field of real numbers by valuations ( = finitely additive measures) on the corresponding tension–flow spaces of the three types with weights. We produce a number of Tutte type polynomials of two and of four variables associated with the graph G ; some are old or generalizations, some are completely new. The present paper is to introduce the Cartesian product arrangement and multivariable characteristic polynomial, then to examine the aforementioned two-variable and four-variable polynomials. We obtain expansion formulas of these polynomials and the reciprocity laws holding among them. Moreover, the reciprocity law for one-variable characteristic polynomial is treated geometrically so that the combinatorial interpretations are obtained uniformly for the absolute values of the chromatic polynomial, tension polynomial, and flow polynomial of graphs.

Let C 4 ( n ) be the family of all connected 4 -chromatic graphs of order n . Given an integer x ≥ 4 , we consider the problem of finding the maximum number of x -colorings of a graph in C 4 ( n ) . It was conjectured that the maximum number of x -colorings is equal to ( x ) ↓ 4 ( x − 1 ) n − 4 and the extremal graphs are those which have clique number 4 and size n + 2 . In this article, we reduce this problem to a finite family of graphs. We show that there exists a finite family F of connected 4 -chromatic graphs such that if the number of x -colorings of every graph G in F is less than ( x ) ↓ 4 ( x − 1 ) | V ( G ) | − 4 then the conjecture holds to be true.

The Stanley chromatic symmetric function $X_G$ of a graph $G$ is a symmetric function generalization of the chromatic polynomial, and has interesting combinatorial properties. We apply the ideas of Khovanov homology to construct a homology of graded $S_n$-modules, whose graded Frobenius series $Frob_G(q,t)$ reduces to the chromatic symmetric function at $q=t=1$. This homology can be thought of as a categorification of the chromatic symmetric function, and provides a homological analogue of several familiar properties of $X_G$. In particular, the decomposition formula for $X_G$ discovered recently by Orellana and Scott, and Guay-Paquet is lifted to a long exact sequence in homology., Comment: 26 pages

Stanley's symmetrized chromatic polynomial is a generalization of the ordinary chromatic polynomial to a graph invariant with values in a ring of polynomials in infinitely many variables. The ordinary chromatic polynomial is a specialization of Stanley's one. To each orientable embedded graph with a single vertex, a simple graph is associated, which is called the intersection graph of the embedded graph. As a result, we can define Stanley's symmetrized chromatic polynomial for any orientable embedded graph with a single vertex. Our goal is to extend Stanley's chromatic polynomial to embedded graphs with arbitrary number of vertices, and not necessarily orientable. In contrast to well-known extensions of, say, the Tutte polynomial from abstract to embedded graphs [4] , our extension is based not on the structure of the underlying abstract graph and the additional information about the embedding. Instead, we consider the binary delta-matroid associated to an embedded graph and define the extended Stanley chromatic polynomial as an invariant of binary delta-matroids. We show that, similarly to Stanley's symmetrized chromatic polynomial of graphs, which satisfies 4-term relations for simple graphs, the polynomial that we introduce satisfies the 4-term relations for binary delta-matroids [7] . For graphs, Stanley's chromatic function produces a knot invariant by means of the correspondence between simple graphs and knots. Analogously we may interpret the suggested extension as an invariant of links, using the correspondence between binary delta-matroids and links.

We construct a new polynomial invariant of maps (graphs embedded in closed surfaces, not necessarily orientable). Our invariant is tailored to contain as evaluations the number of local flows and local tensions taking non-identity values in any given finite group. Moreover, it contains as specializations the Krushkal polynomial, the Bollobás-Riordan polynomial, the Las Vergnas polynomial, and their extensions to non-orientable surfaces, and hence in particular the Tutte polynomial of the under-lying graph of the map.

Tutte–Grothendieck invariants of graphs are mappings from a class of graphs to a commutative ring that are characterized recursively by contraction-deletion rules. Well known examples are the Tutte, chromatic, tension and flow polynomials. Suppose that an edge cut C divides a graph G into two parts G1, G1′ and that G1, G1′ are the sets of minors of G whose edge sets consist of C and edges of G1, G1′, respectively. We study determinant formulas evaluating a Tutte–Grothendieck invariant of G from the Tutte–Grothendieck invariants of graphs from G1 and G1′.

A restraintr on G is a function which assigns each vertex v of G a finite set of forbidden colours r(v). A proper colouring c of G is said to be permitted by the restraint r if c(v)r(v) for every vertex v of G. A restraint r on a graph G with n vertices is called a k-restraint if r(v)=k and r(v){1,2,,kn} for every vertex v of G. In this article we discuss the following problem: among all k-restraints r on G, which restraints permit the largest number of x-colourings for all large enough x? We determine such extremal restraints for all bipartite graphs.

Let G be a connected graph with n vertices and m edges. Using Whitney's broken cycle theorem, we prove that if k > m − 1 ln ⁡ ( 1 + 2 ) ≈ 1.135 ( m − 1 ) then for every k -list assignment L of G , the number of L -colorings of G is at least that of ordinary k -colorings of G . This improves previous results of Donner (1992) and Thomassen (2009), who proved the result for k sufficiently large and k > n 10 , respectively.

We introduce the ``trivariate Tutte polynomial" of a signed graph as an invariant of signed graphs up to vertex switching that contains among its evaluations the number of proper colorings and the number of nowhere-zero flows. In this, it parallels the Tutte polynomial of a graph, which contains the chromatic polynomial and flow polynomial as specializations. The number of nowhere-zero tensions (for signed graphs they are not simply related to proper colorings as they are for graphs) is given in terms of evaluations of the trivariate Tutte polynomial at two distinct points. Interestingly, the bivariate dichromatic polynomial of a biased graph, shown by Zaslavsky to share many similar properties with the Tutte polynomial of a graph, does not in general yield the number of nowhere-zero flows of a signed graph. Therefore the ``dichromate" for signed graphs (our trivariate Tutte polynomial) differs from the dichromatic polynomial (the rank-size generating function). The trivariate Tutte polynomial of a signed graph can be extended to an invariant of ordered pairs of matroids on a common ground set -- for a signed graph, the cycle matroid of its underlying graph and its frame matroid form the relevant pair of matroids. This invariant is the canonically defined Tutte polynomial of matroid pairs on a common ground set in the sense of a recent paper of Krajewski, Moffatt and Tanasa, and was first studied by Welsh and Kayibi as a four-variable linking polynomial of a matroid pair on a common ground set., 53 pp. 9 figures

Motivated by Dohmen-P\"onitz-Tittmann's bivariate chromatic polynomial $\chi_G(x,y)$, which counts all $x$-colorings of a graph $G$ such that adjacent vertices get different colors if they are $\le y$, we introduce a bivarate version of Stanley's order polynomial, which counts order preserving maps from a given poset to a chain. Our results include decomposition formulas in terms of linear extensions, a combinatorial reciprocity theorem, and connections to bivariate chromatic polynomials., Comment: 8 pages, 3 figures

This paper deals with distinct computational methods to enumerate the set $\mathrm{PLR}(r,s,n;m)$ of $r \times s$ partial Latin rectangles on $n$ symbols with $m$ non-empty cells. For fixed $r$, $s$, and $n$, we prove that the size of this set is a symmetric polynomial of degree $3m$, and we determine the leading terms (the monomials of degree $3m$ through $3m-9$) using inclusion-exclusion. For $m \leq 13$, exact formulas for these symmetric polynomials are determined using a chromatic polynomial method. Adapting Sade's method for enumerating Latin squares, we compute the exact size of $\mathrm{PLR}(r,s,n;m)$, for all $r \leq s \leq n \leq 7$, and all $r \leq s \leq 6$ when $n=8$. Using an algebraic geometry method together with Burnside's Lemma, we enumerate isomorphism, isotopism, and main classes when $r \leq s \leq n \leq 6$. Numerical results have been cross-checked where possible., Comment: 36 pages, 2 figures, 15 tables

Let G be a graph, and let $\chi$G be its chromatic polynomial. For any non-negative integers i, j, we give an interpretation for the evaluation $\chi$ (i) G (--j) in terms of acyclic orientations. This recovers the classical interpretations due to Stanley and to Green and Zaslavsky respectively in the cases i = 0 and j = 0. We also give symmetric function refinements of our interpretations, and some extensions. The proofs use heap theory in the spirit of a 1999 paper of Gessel., Comment: minor corrections

Let $\mathfrak g$ be a Borcherds algebra with the associated graph $G$. We prove that the chromatic symmetric function of $G$ can be recovered from the Weyl denominator identity of $\mathfrak g$ and this gives a Lie theoretic proof of Stanley's expression for chromatic symmetric function in terms of power sum symmetric function. Also, this gives an expression for chromatic symmetric function of $G$ in terms of root multiplicities of $\lie g$. The absolute value of the linear coefficient of the chromatic polynomial of $G$ is known as the chromatic discriminant of $G$. As an application of our main theorem, we prove that graphs with different chromatic discriminants are distinguished by their chromatic symmetric functions. Also, we find a connection between the Weyl denominators and the $G$-elementary symmetric functions. Using this connection, we give a Lie theoretic proof of non-negativity of coefficients of $G$-power sum symmetric functions., Comment: arXiv admin note: text overlap with arXiv:1612.01320

Let $G=(V,E)$ be a simple graph with $V=\{1,2,\cdots,n\}$ and $\chi(G,x)$ be its chromatic polynomial. For an ordering $\pi=(v_1,v_2,\cdots,v_n)$ of elements of $V$, let $\delta_G(\pi)$ be the number of $i$'s, where $1\le i\le n-1$, with either $v_i, Comment: 33 pages and 5 figures. Will appear in JGT

The oriented chromatic polynomial of a oriented graph outputs the number of oriented $k$-colourings for any input $k$. We fully classify those oriented graphs for which the oriented graph has the same chromatic polynomial as the underlying simple graph, closing an open problem posed by Sopena. We find that such oriented graphs can be both identified and constructed in polynomial time as they are exactly the family of quasi-transitive oriented co-interval graphs. We study the analytic properties of this polynomial and show that there exist oriented graphs which have chromatic polynomials have roots, including negative real roots, that cannot be realized as the root of any chromatic polynomial of a simple graph.

In this paper, we prove that ( − ∞ , 0 ) is a zero-free interval for chromatic polynomials of a family L 0 of hypergraphs and ( 0 , 1 ) is a zero-free interval for chromatic polynomials of a subfamily L 0 ′ of L 0 of hypergraphs. These results extend known results on zero-free intervals of chromatic polynomials of graphs and hypergraphs.

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.

We extend the definition of the chromatic symmetric function X G to include graphs G with a vertex-weight function w : V ( G ) → N . We show how this provides the chromatic symmetric function with a natural deletion–contraction relation analogous to that of the chromatic polynomial. Using this relation we derive new properties of the chromatic symmetric function, and we give alternate proofs of many fundamental properties of X G .

We introduce ideas that complement the many known connections between polymatroids and graph coloring. Given a hypergraph that satisfies certain conditions, we construct polymatroids, given as rank functions, that can be written as sums of rank functions of matroids, and for which the minimum number of matroids required in such sums is the chromatic number of the line graph of the hypergraph. This result motivates introducing chromatic numbers and chromatic polynomials for polymatroids. We show that the chromatic polynomial of any 2-polymatroid is a rational multiple of the chromatic polynomial of some graph. We also find the excluded minors for the minor-closed class of polymatroids that can be written as sums of rank functions of matroids that form a chain of quotients., Comment: 21 pages

A vertex subset WV of the graph G=(V,E) is a total dominating set if every vertex of the graph is adjacent to at least one vertex in W. The total domination polynomial is the ordinary generating function for the number of total dominating sets in the graph. We investigated some graph products for a generalization of the total domination polynomial, called the trivariate total domination polynomial. We also show that the chromatic polynomial is encoded in the independent domination polynomial of some graph products. These results have a wide applicability to other domination related graph polynomials, e.g.the domination polynomial, the independent domination polynomial or the independence polynomial.

The Fomin-Kirillov algebra E n is a noncommutative algebra with a generator for each edge of the complete graph on n vertices. For any graph G on n vertices, let E G be the subalgebra of E n generated by the edges in G . We show that the commutative quotient of E G is isomorphic to the Orlik-Terao algebra of G . As a consequence, the Hilbert series of this quotient is given by ( - t ) n ? G ( - t - 1 ) , where ? G is the chromatic polynomial of G . We also give a reduction algorithm for the graded components of E G that do not vanish in the commutative quotient and show that their structure is described by the combinatorics of noncrossing forests.

We give some extremal properties on the number B ( G ) of non-equivalent ways of coloring a given graph G , also known as the (graphical) Bell number of G . In particular, we study bounds on B ( G ) for graphs with a maximum degree constraint. First, an upper bound on B ( G ) is given for graphs with fixed order n and maximum degree Δ . Then, we give lower bounds on B ( G ) for fixed order n and maximum degree 1, 2, n - 2 and n - 1 . In each case, the bound is tight and we describe all graphs that reach the bound with equality.

For a graph $G$, let $P(G,\lambda)$ denote the chromatic polynomial of $G$. Two graphs $G$ and $H$ are chromatically equivalent if they share the same chromatic polynomial. A graph $G$ is chromatically unique if for any graph chromatically equivalent to $G$ is isomorphic to $G$. In this paper, the chromatically unique of a new family of 6-bridge graph $\theta(a,a,a,b,b,c)$ where $2\le a\le b\le c$ is investigated.

The $$\sigma $$ź-polynomial is given by $$\sigma (G,x) = \sum _{i=\chi (G)}^{n} a_{i}(G)\, x^{i}$$ź(G,x)=źi=ź(G)nai(G)xi, where $$a_{i}(G)$$ai(G) is the number of partitions of the vertices of G into i nonempty independent sets. These polynomials are closely related to chromatic polynomials, as the chromatic polynomial of G is given by $$\sum _{i=\chi (G)}^{n} a_{i}(G)\, x(x-1) \ldots (x-(i-1))$$źi=ź(G)nai(G)x(x-1)ź(x-(i-1)). It is known that the closure of the real roots of chromatic polynomials is precisely $$\{0,~1\} \bigcup [32/27,\infty )$${0,1}ź[32/27,ź), with $$(-\infty ,0)$$(-ź,0), (0, 1) and (1, 32 / 27) being maximal zero-free intervals for roots of chromatic polynomials. We ask here whether such maximal zero-free intervals exist for $$\sigma $$ź-polynomials, and show that the only such interval is $$[0,\infty )$$[0,ź)--that is, the closure of the real roots of $$\sigma $$ź-polynomials is $$(-\infty ,0]$$(-ź,0].

Recently, M.Abrt and T.Hubai studied the following problem. The chromatic measure of a finite simple graph is defined to be the uniform distribution on its chromatic roots. Abrt and Hubai proved that for a BenjaminiSchramm convergent sequence of finite graphs, the chromatic measures converge in holomorphic moments. They also showed that the normalized logarithm of the chromatic polynomial converges to a harmonic real function outside a bounded disc.In this paper we generalize their work to a wide class of graph polynomials, namely, multiplicative graph polynomials of bounded exponential type. A special case of our results is that for any fixed complex number v0 the measures arising from the Tutte polynomial ZGn(z,v0) converge in holomorphic moments if the sequence (Gn) of finite graphs is BenjaminiSchramm convergent. This answers a question of Abrt and Hubai in the affirmative. Even in the original case of the chromatic polynomial, our proof is considerably simpler.

The odd-even invariant for graphs is the graphic version of the odd-even invariant for oriented matroids. Here, simple properties of this invariant are verified, and for certain graphs, including chordal graphs and complete bipartite graphs, its value is determined. The odd-even chromatic polynomial is introduced, its coefficients are briefly studied, and it is shown that the absolute value of this polynomial at -1 equals the odd-even invariant, in analogy with the usual chromatic polynomial and the number of acyclic orientations.

The cycle polynomial of a finite permutation group $G$ is the generating function for the number of elements of $G$ with a given number of cycles: \[F_G(x) = \sum_{g\in G}x^{c(g)},\] where $c(g)$ is the number of cycles of $g$ on $\Omega$. In the first part of the paper, we develop basic properties of this polynomial, and give a number of examples. In the 1970s, Richard Stanley introduced the notion of reciprocity for pairs of combinatorial polynomials. We show that, in a considerable number of cases, there is a polynomial in the reciprocal relation to the cycle polynomial of $G$; this is the orbital chromatic polynomial of $\Gamma$ and $G$, where $\Gamma$ is a $G$-invariant graph, introduced by the first author, Jackson and Rudd. We pose the general problem of finding all such reciprocal pairs, and give a number of examples and characterisations: the latter include the cases where $\Gamma$ is a complete or null graph or a tree. The paper concludes with some comments on other polynomials associated with a permutation group., Comment: 16 pages

In this note we prove that the product of two arithmetic multiplicity functions on a matroid is again an arithmetic multiplicity function. This allows us to answer a question by Bajo–Burdick–Chmutov [2] , concerning the modified Tutte–Krushkal–Renhardy polynomials defined by these authors. Furthermore, we show that the Tutte quasi-polynomial introduced by Branden and Moci encompasses invariants defined by Beck–Breuer–Godkin–Martin [3] and Duval–Klivans–Martin [11] and can thus be considered as a dichromate for CW complexes.

We study “holomorphic quadratic differentials” on graphs. We relate them to the reactive power in an LC circuit, and also to the chromatic polynomial of a graph. Specifically, we show that the chromatic polynomial χ of a graph G , at negative integer values, can be evaluated as the degree of a certain rational mapping, arising from the defining equations for a holomorphic quadratic differential. This allows us to give an explicit integral expression for χ ( − k ) .

Given a graph G of order n, the σ-polynomial of G is the generating function where is the number of partitions of the vertex set of G into i nonempty independent sets. Such polynomials arise in a natural way from chromatic polynomials. Brenti (Trans Am Math Soc 332 (1992), 729–756) proved that σ-polynomials of graphs with chromatic number at least had all real roots, and conjectured the same held for chromatic number . We affirm this conjecture.

The chromatic equivalence class of a graph G is the set of graphs that have the same chromatic polynomial as G . We find the chromatic equivalence class of the complete tripartite graphs K 1 , n , n + 2 for all n ? 2 . This partially answers a question raised in Chia and Ho (2009), which asks for the chromatic equivalence class of the graph K 1 , m , n where 2 ? m ? n .

Recently, Tittmann et?al. introduced the subgraph component polynomial and showed that its power for distinguishing graphs is quite different from the power of other graph polynomials that appear in the literature such as the matching polynomial, the Tutte polynomial, the characteristic polynomial, the chromatic polynomial, etc. The subgraph component polynomial enumerates vertex-induced subgraphs in a given undirected graph with respect to the number of components. We show the use of the subgraph component polynomial to count the number of primitive partial words of a given length over an alphabet of a fixed size, which leads to a method for enumerating such partial words. We also give a tight bound for the maximum number of holes a primitive partial word can have. Doing so allows us to establish some tight upper and lower bounds on the maximum number of occurrences of primitively-rooted squares, i.e.,?adjacent occurrences of two compatible substrings with primitive root, in a given partial word with a fixed number of holes over a fixed alphabet size.

The domination polynomial of a graph is the polynomial whose coefficients count the number of dominating sets of each cardinality. A recent question asks which graphs are uniquely determined (up to isomorphism) by their domination polynomial. In this paper, we completely describe the complete $$r$$r-partite graphs which are; in the bipartite case, this settles in the affirmative a conjecture of Aalipour et al. (Ars Comb, 2014).

We give a new interpretation of the chromatic polynomial of a simple graph $$G$$G in terms of the Kac---Moody Lie algebra $$\mathfrak {g}$$g with Dynkin diagram $$G$$G. We show that the chromatic polynomial is essentially the $$q$$q-Kostant partition function of $$\mathfrak {g}$$g evaluated on the sum of the simple roots. Applying the Peterson recurrence formula for root multiplicities of $$\mathfrak {g}$$g, we obtain a new realization of the chromatic polynomial as a weighted sum of paths in the bond lattice of $$G$$G.