On the Location of Roots of Graph Polynomials

Roots of graph polynomials such as the characteristic polynomial, the chromatic polynomial, the matching polynomial, and many others are widely studied. In this paper we examine to what extent the location of these roots reflects the graph theoretic properties of the underlying graph.     

Chromatic polynomials and σ-polynomials

In this paper we present some results on the sequence of coefficients of the chromatic polynomial of a graph relative to the complete graph basis, that is, when it is expressed as the sum of the chromatic polynomials of complete graphs. These coefficients are the coefficients of what is often called the σ-polynomial. We obtain necessary and sufficient conditions for this sequence to be symmetrical, and we prove that it is ‘skewed’ and decreasing beyond its midpoint. We also prove that it is strongly log-concave when G is a complete multipartite graph. © 1996 John Wiley & Sons, Inc.     

On chromatic coefficients

Explicit expressions in terms of subgraphs of the graph are given for the first five coefficients of the chromatic polynomial of a graph.     

Decomposable polymatroids and connections with graph coloring

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.     

Bijective proofs of two broken circuit theorems

We prove, by means of explicit bijections, theorems of Whitney and Stanley that express the coefficients of the chromatic polynomial of a graph G and the number of acyclic orientations of G in terms of numbers of sets of edges that contain no broken circuits of G.     

Chromatic polynomials and whitney's broken circuits

The theorem of Hassler Whitney, which gives the chromatic polynomial of a graph in terms of “broken circuits,” is used to derive a new formula for the coefficients of chromatic polynomials.     

Chromatic Polynomials and the Symmetric Group

In this paper we give first a new combinatorial interpretation of the coefficients of chromatic polynomials of graphs in terms of subsets of permutations. Motivated by this new interpretation, we introduce next a combinatorially defined polynomial associated to a directed graph, and prove that it is related to chromatic polynomials. These polynomials are a specialization of cover polynomials of digraphs.I am grateful to the Swiss National Science Foundation for its partial financial supportFinal version received: June 25, 2003     

图和色多项式根2的阶

本文证明了3-连通非偶图的色多项式根2的阶为1;满足一定条件的非3-连通非偶图的色多项式根2的阶是图的非偶块和非偶可分块数.从而,把色多项式P(G)中1的阶是图G的非平凡块数这一结果进一步加以推广.     

Computing clique and chromatic number of circular-perfect graphs in polynomial time

A main result of combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel et al. in Combinatorica 1(2):169–197, 1981). Perfect graphs have the key property that clique and chromatic number coincide for all induced subgraphs; we address the question whether the algorithmic results for perfect graphs can be extended to graph classes where the chromatic number of all members is bounded by the clique number plus one. We consider a well-studied superclass of perfect graphs satisfying this property, the circular-perfect graphs, and show that for such graphs both clique and chromatic number are computable in polynomial time as well. In addition, we discuss the polynomial time computability of further graph parameters for certain subclasses of circular-perfect graphs. All the results strongly rely upon Lovász’s Theta function.     

On chromatic and flow polynomial unique graphs

It is known that the chromatic polynomial and flow polynomial of a graph are two important evaluations of its Tutte polynomial, both of which contain much information of the graph. Much research is done on graphs determined entirely by their chromatic polynomials and Tutte polynomials, respectively. Oxley asked which classes of graphs or matroids are determined by their chromatic and flow polynomials together. In this paper, we found several classes of graphs with this property. We first study which graphic parameters are determined by the flow polynomials. Then we study flow-unique graphs. Finally, we show that several classes of graphs, ladders, Möbius ladders and squares of n-cycle are determined by their chromatic polynomials and flow polynomials together. A direct consequence of our theorem is a result of de Mier and Noy [A. de Mier, M. Noy, On graphs determined by their Tutte polynomial, Graphs Comb. 20 (2004) 105-119] that these classes of graphs are Tutte polynomial unique.     

On the location of zeros of the Laplacian matching polynomials of graphs

Journal of Algebraic Combinatorics - The Laplacian matching polynomial of a graph G, denoted by $$\mathscr {LM}(G,x)$$ , is a new graph polynomial whose all zeros are nonnegative real numbers. In...     

The chromatic polynomial of fatgraphs and its categorification

Motivated by Khovanov homology and relations between the Jones polynomial and graph polynomials, we construct a homology theory for embedded graphs from which the chromatic polynomial can be recovered as the Euler characteristic. For plane graphs, we show that our chromatic homology can be recovered from the Khovanov homology of an associated link. We apply this connection with Khovanov homology to show that the torsion-free part of our chromatic homology is independent of the choice of planar embedding of a graph. We extend our construction and categorify the Bollobás-Riordan polynomial (a generalization of the Tutte polynomial to embedded graphs). We prove that both our chromatic homology and the Khovanov homology of an associated link can be recovered from this categorification.     

The connected partition lattice of a graph and the reconstruction conjecture

Previously we showed that many invariants of a graph can be computed from its abstract induced subgraph poset, which is the isomorphism class of the induced subgraph poset, suitably weighted by subgraph counting numbers. In this paper, we study the abstract bond lattice of a graph, which is the isomorphism class of the lattice of distinct unlabelled connected partitions of a graph, suitably weighted by subgraph counting numbers. We show that these two abstract posets can be constructed from each other except in a few trivial cases. The constructions rely on certain generalisations of a lemma of Kocay in graph reconstruction theory to abstract induced subgraph posets. As a corollary, trees are reconstructible from their abstract bond lattice. We show that the chromatic symmetric function and the symmetric Tutte polynomial of a graph can be computed from its abstract induced subgraph poset. Stanley has asked if every tree is determined up to isomorphism by its chromatic symmetric function. We prove a counting lemma, and indicate future directions for a study of Stanley's question.     

Graph colorings and acyclic orientations

This paper presents new combinatorial proofs of two identities due to R. Stanley relating the chromatic polynomial and acyclic orientations of a graph. In addition, using elementary means, explicit formulae for the generating functions of the chromatic numbers and the number of color compatible acyclic orientations are derived. These formulae immediately show a reciprocity law concerning the generating functions.     

Cutpoints and the chromatic polynomial

We prove that the multiplicity of the root 1 in the chromatic polynomial of a simple graph G is equal to the number of nontrivial blocks in G. In particular, a connected simple graph G has a cutpoint if and only if its chromatic polynomial is divisible by (λ – 1)². We apply this theorem to obtain some chromatic equivalence and uniqueness results.     

广义Pòlya组合计数方法

文中引入了P-置换图的概念．作为置换群的指标多项式和函数等价类配置多项式的推广形式分别定义了P-置换图的容量指标多项式与色权多项式,并给出了递归公式和相关定理,由此建立了计算P-置换图的色权多项式的一般方法和P-置换图的色轨道多项式的表达公式．Polya计数定理是这一公式当约束图是空图时的特例．最后给出了P-置换图的色权多项式的一些基本性质和两个计算实例．     

A generalization of chromatic polynomial of a graph subdivision

Considering the partitions of a set into nonempty subsets, we obtain an expression for the number of all partitions of a given type. The chromatic polynomial of a graph subdivision is generalized, considering two sets of colors, and a general explicit expression is obtained for this generalization. Using these results, we determine the generalized chromatic polynomial for the particular case of complete graph subdivision.     

On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs

A main result in combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel, Lovász and Schrijver 1981). The circular-clique and circular-chromatic number are well-studied refinements of these graph parameters, and circular-perfect graphs form the corresponding superclass of perfect graphs. So far, it is unknown whether the (weighted) circular-clique and circular-chromatic number of a circular-perfect graph are computable in polynomial time. In this paper, we show the polynomial time computability of these two graph parameters for some super-classes of perfect graphs with the help of polyhedral arguments.     

图的星色数

给出了一些星色数为４的平面图,它们不含有轮图作为子图,这回答了Ｚｈｕ的一个问题,给出了一类４连通平面图其星色数在３与４之间,这也回答了Ａｂｂｏｔｔ和Ｚｈｏｕ的一个问题,应用图的同态概念,讨论了某些图的字典积的星色数,证明了一个图及其补图的星色数的和与积所满足的两个不等式。     

RECURSIVE FORMULA FOR CALCULATING THE CHROMATIC POLYNOMIAL OF A GRAPH BY VERTEX DELETION

A new recursive vertex-deleting formula for the computation of the chromatic polynomial of a graph is obtained in this paper. This algorithm is not only a good tool for further studying chromatic polynomials but also the fastest among all the algorithms for the computation of chromatic polynomials.