LLT polynomials,chromatic quasisymmetric functions and graphs with cycles

We use a Dyck path model for unit-interval graphs to study the chromatic quasisymmetric functions introduced by Shareshian and Wachs, as well as unicellular LLT polynomials, revealing some parallel structure and phenomena regarding their $\mathrm{e}$-positivity.The Dyck path model is also extended to circular arc digraphs to obtain larger families of polynomials, giving a new extension of LLT polynomials. Carrying over a lot of the non-circular combinatorics, we prove several statements regarding the $\mathrm{e}$-coefficients of chromatic quasisymmetric functions and LLT polynomials, including a natural combinatorial interpretation for the $\mathrm{e}$-coefficients for the line graph and the cycle graph for both families. We believe that certain $\mathrm{e}$-positivity conjectures hold in all these families above.Furthermore, beyond the chromatic analogy, we study vertical-strip LLT polynomials, which are modified Hall–Littlewood polynomials.     

关于Q-树偶次整子图色性的一族反例(英文)

Chao ,Li和Xu[1 ],韩伯棠 [2 ,3]和ThomasWanner[4 ]证明 ,以q 树 ,qk 树和q 树整子图的色多项式为色多项式的图是唯一的 ,即它们本身 .但本文 ,我们证明了q 树的偶次整子图的色多项式 ,除本身外 ,至少对应一类新图 ,而且指出这类图 ,即使色多项式仅有整根也不能三角化 .     

去掉一些连续弦的轮图的补图的色多项式

本文给出计算图的色多项式的新方法。特别的,对轮图中去掉一些连续弦后所得到的图的补图,给出了它的色多项式的计算公式。     

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.     

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.     

Lower Bounds for Measurable Chromatic Numbers

The Lovász theta function provides a lower bound for the chromatic number of finite graphs based on the solution of a semidefinite program. In this paper we generalize it so that it gives a lower bound for the measurable chromatic number of distance graphs on compact metric spaces. In particular we consider distance graphs on the unit sphere. There we transform the original infinite semidefinite program into an infinite linear program which then turns out to be an extremal question about Jacobi polynomials which we solve explicitly in the limit. As an application we derive new lower bounds for the measurable chromatic number of the Euclidean space in dimensions 10, . . . , 24 and we give a new proof that it grows exponentially with the dimension.     

两类图的伴随多项式

本文推广已有图D_n,F_n到两类新图D_n~i,F_n~i(i≥4),并运用与色和有关的代数函数—伴随函数得到它们的伴随多项式并讨论了当i=4时的不可约性.     

An introduction to the k-defect polynomials

The 0-defect polynomial of a graph is just the chromatic polynomial. This polynomial has been widely studied in the literature. Yet little is known about the properties of k-defect polynomials of graphs in general, when 0 < k ≤ |E(G)|. In this survey we give some properties of k-defect polynomials, in particular we highlight the properties of chromatic polynomials which also apply to k-defect polynomials. We discuss further research which can be done on the k-defect polynomials.     

Chromatic Polynomials of Complements of Bipartite Graphs

We define a biclique to be the complement of a bipartite graph, consisting of two cliques joined by a number of edges. In this paper we study algebraic aspects of the chromatic polynomials of these graphs. We derive a formula for the chromatic polynomial of an arbitrary biclique, and use this to give certain conditions under which two of the graphs have chromatic polynomials with the same splitting field. Finally, we use a subfamily of bicliques to prove the cubic case of the α + n conjecture, by showing that for any cubic integer α, there is a natural number n such that α + n is a chromatic root.     

两类只含整数根的色多项式

研究了两类只含整数根的色多项式,给出其相应图G为弦图的必要条件,并完全刻画了G的色等价类[G].     

σ-polynomials and graph coloring

A new class of graph polynomials is defined. Tight bounds on the coefficients of the polynomials are given, and the exact polynomials for several classes of graphs are derived. The relationship of these polynomials to chromatic polynomials and graph coloring is discussed.     

On Chromatic Polynomials of Some Kinds of Graphs

In this paper,a new method is used to calculate the chromatic polynomials of graphs.The chro-matic polynomials of the complements of a wheel and a fan are determined.Furthermore,the adjoint polynomialsof F_n with n vertices are obtained.This supports a conjecture put forward by R.Y.Liu et al.     

A logician's view of graph polynomials

Graph polynomials are graph parameters invariant under graph isomorphisms which take values in a polynomial ring with a fixed finite number of indeterminates. We study graph polynomials from a model theoretic point of view. In this paper we distinguish between the graph theoretic (semantic) and the algebraic (syntactic) meaning of graph polynomials. Graph polynomials appear in the literature either as generating functions, as generalized chromatic polynomials, or as polynomials derived via determinants of adjacency or Laplacian matrices. We show that these forms are mutually incomparable, and propose a unified framework based on definability in Second Order Logic. We show that this comprises virtually all examples of graph polynomials with a fixed finite set of indeterminates. Finally we show that the location of zeros and stability of graph polynomials is not a semantic property. The paper emphasizes a model theoretic view. It gives a unified exposition of classical results in algebraic combinatorics together with new and some of our previously obtained results scattered in the graph theoretic literature.     

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.     

A maximal zero-free interval for chromatic polynomials of bipartite planar graphs

It is well known that (-∞,0) and (0,1) are two maximal zero-free intervals for all chromatic polynomials. Jackson [A zero-free interval for chromatic polynomials of graphs, Combin. Probab. Comput. 2 (1993), 325-336] discovered that is another maximal zero-free interval for all chromatic polynomials. In this note, we show that is actually a maximal zero-free interval for the chromatic polynomials of bipartite planar graphs.     

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.     

Gale duality bounds for roots of polynomials with nonnegative coefficients

We bound the location of roots of polynomials that have nonnegative coefficients with respect to a fixed but arbitrary basis of the vector space of polynomials of degree at most d. For this, we interpret the basis polynomials as vector fields in the real plane, and at each point in the plane analyze the combinatorics of the Gale dual vector configuration. This approach permits us to incorporate arbitrary linear equations and inequalities among the coefficients in a unified manner to obtain more precise bounds on the location of roots. We apply our technique to bound the location of roots of Ehrhart and chromatic polynomials. Finally, we give an explanation for the clustering seen in plots of roots of random polynomials.     

关于图的色多项式的若干问题

<正> 设G是连通的无向的标定的(p,q)图.集S={1,2,…,t}.G的一个t-着色σ是G的点的集V(G)到S内的一个映射,满足条件:若u,v∈V(G)在G中邻接,则σu≠σv.G的不同的t-着色的总数f(G;t)是t的一个p次多项式.(关于色多项式的一般论述,下文未注明出处的结果及未给出定义的名词与记号均参见[1]).这个多项式记作     

Rook theory III. Rook polynomials and the chromatic structure of graphs

This paper studies the relationship between the rook vector of a general board and the chromatic structure of an associated set of graphs. We prove that every rook vector is a chromatic vector. We give algebraic relations between the factorial polynomials of two boards and their union and sum, and the chromatic polynomials of two graphs and their union and sum.     

关于几类图族伴随多项式的第四项系数

主要研究了几类图族伴随多项式第四项系数的规律，此结果有助于进一步讨论这些图族补图的色唯一性、色等价划分．