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

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

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     

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.     

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.     

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.     

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

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

σ-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.     

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.     

Chromatic polynomials,polygon trees,and outerplanar graphs

It is proved that all classes of polygon trees are characterized by their chromatic polynomials, and a characterization is given of those polynominals that are chromatic polynomials of outerplanar graphs. The first result yields an alternative proof that outerplanar graphs are recognizable from their vertex-deleted subgraphs. © 1929 John Wiley & Sons, Inc.     

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.     

Die chromatischen Polynome unterringfreier Graphen

Let G be a finite undirected graph without loops and multiple edges. A graph is called “unterringfrei”, if there is no induced subgraph being a cycle of length?4. This note shows that the chromatic polynomial of such a graph does only have positive integers as its roots. Conversely all polynomials with only positive integral roots are the chromatic polynomials of such graphs under the slight restriction that M(G;α)=0 implies that M(G;β)=0 for α>β?0.     

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.     

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.     

Approximations for chromatic polynomials

A sequence of finite graphs may be constructed from a given graph by a process of repeated amalgamation. Associated with such a sequence is a transfer matrix whose minimum polynomial gives a recursion for the chromatic polynomials of the graphs in the sequence. Taking the limit, a generalised “chromatic polynomial” for infinite graphs is obtained.     

Chromatic series for functions of slow growth

The theory of chromatic derivatives leads to chromatic series which replace Taylor's series for bandlimited functions. For such functions, these series have a global convergence property not shared by Taylor's series. In this work the theory is extended to bandlimited functions of slow growth. This includes many signals of practical importance such as polynomials, periodic functions and almost periodic functions. This extension also enables us to get improved local convergence results for chromatic series.     

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

<正> 设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]).这个多项式记作     

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.     

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.     

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

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