Optimal graphs for chromatic polynomials

Let F(n,e) be the collection of all simple graphs with n vertices and e edges, and for G∈F(n,e) let P(G;λ) be the chromatic polynomial of G. A graph G∈F(n,e) is said to be optimal if another graph H∈F(n,e) does not exist with P(H;λ)?P(G;λ) for all λ, with strict inequality holding for some λ. In this paper we derive necessary conditions for bipartite graphs to be optimal, and show that, contrarily to the case of lower bounds, one can find values of n and e for which optimal graphs are not unique. We also derive necessary conditions for bipartite graphs to have the greatest number of cycles of length 4.     

Maximal chromatic polynomials of connected planar graphs

In this paper we obtain chromatic polynomials of connected 3- and 4-chromatic planar graphs that are maximal for positive integer-valued arguments. We also characterize the class of connected 3-chromatic graphs having the maximum number of p-colorings for p ≥ 3, thus extending a previous result by the author (the case p = 3).     

Maximum chromatic polynomials of 2-connected graphs

In this paper we obtain chromatic polynomials P(G; λ) of 2-connected graphs of order n that are maximum for positive integer-valued arguments λ ≧ 3. The extremal graphs are cycles C_n and these graphs are unique for every λ ≧ 3 and n ≠ 5. We also determine max{P(G; λ): G is 2-connected of order n and G ≠ C_n} and all extremal graphs relative to this property, with some consequences on the maximum number of 3-colorings in the class of 2-connected graphs of order n having _X(G) = 2 and _X(G) = 3, respectively. For every n ≧ 5 and λ ≧ 4, the first three maximum chromatic polynomials of 2-connected graphs are determined.     

Series-parallel chromatic hypergraphs

In this paper two-terminal series-parallel chromatic hypergraphs are introduced and for this class of hypergraphs it is shown that the chromatic polynomial can be computed with polynomial complexity. It is also proved that h-uniform multibridge hypergraphs θ(h;a₁,a₂,…,a_k) are chromatically unique for h≥3 if and only if h=3 and a₁=a₂=?=a_k=1, i.e., when they are sunflower hypergraphs having a core of cardinality 2 and all petals being singletons.     

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.     

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.     

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.     

Critical hypergraphs for the weak chromatic number

Instead of removing a vertex or an edge from a hypergraph H, one may add to some edges of H new vertices (not necessarily belonging to V_H). The weak chromatic number of H tends to drop by this operation. This suggests the definition of an order relation ≥ on the set $\text{S}$ of all Sperner hypergraphs on a universal set V of vertices. The corresponding criticality study leads to unifying and interesting results: reconstruction of critical hypergraphs and two general characterizations of k-chromatic critical hypergraphs (k ≥ 3), from which a special characterization of 3-chromatic critical hypergraphs can be derived.     

The circular chromatic number of hypergraphs

A generalization of the circular chromatic number to hypergraphs is discussed. In particular, it is indicated how the basic theory, and five equivalent formulations of the circular chromatic number of graphs, can be carried over to hypergraphs with essentially the same proofs.     

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.     

The chromatic numbers of random hypergraphs

For a pair of integers 1≤γ<r, the γ-chromatic number of an r-uniform hypergraph H=(V, E) is the minimal k, for which there exists a partition of V into subsets T₁,…,T_k such that |e∩T_i|≤γ for every e∈E. In this paper we determine the asymptotic behavior of the γ-chromatic number of the random r-uniform hypergraph H_r(n, p) for all possible values of γ and for all values of p down to p=Θ(n^−r+1). © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12: 381–403, 1998     

Supersaturated graphs and hypergraphs

We shall consider graphs (hypergraphs) without loops and multiple edges. Let ? be a family of so called prohibited graphs and ex (n, ?) denote the maximum number of edges (hyperedges) a graph (hypergraph) onn vertices can have without containing subgraphs from ?. A graph (hyper-graph) will be called supersaturated if it has more edges than ex (n, ?). IfG hasn vertices and ex (n, ?)+k edges (hyperedges), then it always contains prohibited subgraphs. The basic question investigated here is: At least how many copies ofL ε ? must occur in a graphG ⁿ onn vertices with ex (n, ?)+k edges (hyperedges)?     

Color-critical graphs and hypergraphs

The main purpose of this paper is to present a technique for obtaining constructions of color-critical graphs. The technique consists in reducing color-critical hypergraphs to color-critical graphs, and the constructions obtained generalize and unify known constructions. It is suggested that constructions of other classes of graphs may be obtained by a similar technique.     

On the chromatic number of Kneser hypergraphs

We give a simple and elementary proof of Kríz's lower bound on the chromatic number of the Kneser -hypergraph of a set system .