The search for chromatically unique graphs

The number of vertex-colourings of a simple graphG in not more than colours is a polynomial in. This polynomial, denoted byP(G, ), is called the chromatic polynomial ofG. A graphG is said to be chromatically unique, in short-unique, ifH G for any graphH withP(H, ) = P(G, ). Since the appearance of the first paper on-unique graphs by Chao and Whitehead in 1978, various families of and several results on such graphs have been obtained successively, especially during the last five years. It is the aim of this expository paper to give a survey on most of the works done on-unique graphs. A number of related problems and conjectures are also included.1980 Mathematical Subject Classification. Primary 05C15This work was done while the author was visiting the Department of Mathematics, National University of Singapore.  

On a construction of critical graphs which are not sensitive

Let ℒ(G) be theclosed-set lattice of a graphG. G issensitive if the following implication is always true for any graphG′: ℒ(G)≅ℒ(G′)⇒(G)≅G′G iscritical if ℒ(G)≇ℒ(G-e) for anye inE(G) and ℒ(G)≇ℒ(G+e) for anye in where is the complement ofG. Every sensitive graph is, a fortiori, critical. Is every critical graph sensitive? A negative answer to this question is given in this note.  

On an isomorphism problem on the closed-set lattice of a graph

Let (G) and V(G) be, respectively, the closed-set lattice and the vertex set of a graph G. Any lattice isomorphism : V(G)(G) induces a bijection : V(G)V(G) such that for each x in V(G), (x)=x' in V(G') iff ({x})={x'}. A graph G is strongly sensitive if for any graph G' and any lattice isomorphism : (G)(G), the bijection induced by is a graph isomorphism of G onto G'. In this paper we present some sufficient conditions for graphs to be strongly sensitive and prove in particular that all C ₄-free graphs and all covering graphs of finite lattices are strongly sensitive.  

ContributionsOn optimal orientations of cartesian products of graphs (I)

For a graph G, let D(G) be the family of strong orientations of G, and define [ovbar|d] (G) = min[d(D) vb D ] D(G), where d(D) denotes the diameter of the digraph D. Let G × H denote the cartesian product of the graphs G and H. In this paper, we determine completely the values of and , except , where K_n, P_n and C_n denote the complete graph, path and cycle of order n, respectively.  

Optimal Orientations of Graphs and Digraphs: A Survey

 For a graph or digraph G, let be the family of strong orientations of G; and for any , we denote by d(D) the diameter of D. Define . In this paper, we survey the results obtained and state some problems and conjectures for the parameter . Received: October, 2001 Final version received: September 23, 2002  

Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs

 Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s ₃(G) ≥ 2 ^{k −3}, where s _r (G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s ₃(G) < 2 ^{k −2}, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C _k by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W _n by deleting all but s consecutive spokes. Received: January 29, 1999 Final version received: April 8, 2000  

The minimum diameter of orientations of complete multipartite graphs

Given a graphG, letB be the family of strong orientations ofG, and define A pair {p,q} of integers is called aco-pair if 1 p q . A multiset {p, q, r} of positive integers is called aco-triple if {p, q} and {p, r} are co-pairs. LetK(p₁, p₂,..., p_n) denote the completen-partite graph havingp _i vertices in theith partite set.In this paper, we show that if {p ₁, p₂,...,p_n} can be partitioned into co-pairs whenn is even, and into co-pairs and a co-triple whenn is odd, then(K(p₁, p₂,..., p_n)) = 2 provided that (n,p ₁, p₂, p₃, p₄) (4, 1, 1, 1, 1). This substantially extends a result of Gutin [3] and a result of Koh and Tan [4].  

On the factor-thickness of regular graphs

For eachr-regular graphG, define a binary sequence(G) = ( ₁, ₂,..., _r-1) by _k = 0 ifG has ak-factor, and _k = 1 otherwise. A binary sequence = ( _i |i = 1, 2,...,r – 1) is said to be realizable if there exists anr-regular graphG such that(G) = . In this paper we characterize all binary sequences which are realizable.