On chromatic uniqueness of certain 5-partite graphs

Let P(G,λ) be the chromatic polynomial of a graph G. Two graphs G and H are said to be chromatically equivalent, denoted G～H, if P(G,λ)=P(H,λ). We write [G]={H∣H～G}. If [G]={G}, then G is said to be chromatically unique. In this paper, we first characterize certain complete 5-partite graphs with 5n+3 vertices according to the number of 6-independent partitions of G. Using these results, we investigate the chromaticity of G with certain star or matching deleted. As a by-product, many new families of chromatically unique complete 5-partite graphs with certain star or matching deleted are obtained.     

Chromatic uniqueness of certain complete tripartite graphs

Let P(G, λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H, λ) = P(G, λ) implies H is isomorphic to G. Liu et al. [Liu, R. Y., Zhao, H. X., Ye, C. F.: A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs. Discrete Math., 289, 175–179 (2004)], and Lau and Peng [Lau, G. C., Peng, Y. H.: Chromatic uniqueness of certain complete t-partite graphs. Ars Comb., 92, 353–376 (2009)] show that K(p − k, p − i, p) for i = 0, 1 are chromatically unique if p ≥ k + 2 ≥ 4. In this paper, we show that if 2 ≤ i ≤ 4, the complete tripartite graph K(p − k, p − i, p) is chromatically unique for integers k ≥ i and p ≥ k ²/4 + i + 1.     

Chromaticity of complete 6-partite graphs with certain star or matching deleted II

Let P(G,λ) be the chromatic polynomial of a graph G. Two graphs G and H are said to be chromatically equivalent, denoted G～H, if P(G,λ)=P (H,λ). We write [G]={H|H～G}. If[G]={G}, then G is said to be chromatically unique. In this paper, we first characterize certain complete 6-partite graphs with 6n+1 vertices according to the number of 7-independent partitions of G. Using these results, we investigate the chromaticity of G with certain star or matching deleted. As a by-product, many new families of chromatically unique complete 6-partite graphs with certain star or matching deleted are obtained.     

Another family of chromatically unique graphs

LetP(G; ) denote the chromatic polynomial of a graphG, expressed in the variable. ThenG is said to be chromatically unique ifG is isomorphic withH for any graphH such thatP(H; ) = P(G; ). In this paper, we provide a new family of chromatically unique graphs.Research was partly supported by the University of Agriculture research grant # 50205-91-05     

Reconstructing graphs as subsumed graphs of hypergraphs,and some self-complementary triple systems

LetV be a set ofn elements. The set of allk-subsets ofV is denoted . Ak-hypergraph G consists of avertex-set V(G) and anedgeset , wherek≥2. IfG is a 3-hypergraph, then the set of edges containing a given vertexvεV(G) define a graphG _v . The graphs {G _v νvεV(G)} aresubsumed byG. Each subsumed graphG _v is a graph with vertex-setV(G) − v. They can form the set of vertex-deleted subgraphs of a graphH, that is, eachG _v ≽H −v, whereV(H)=V(G). In this case,G is a hypergraphic reconstruction ofH. We show that certain families of self-complementary graphsH can be reconstructed in this way by a hypergraphG, and thatG can be extended to a hypergraphG ^*, all of whose subsumed graphs are isomorphic toH, whereG andG ^* are self-complementary hypergraphs. In particular, the Paley graphs can be reconstructed in this way. This work was supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada.     

Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any v ? V(G){v \in V(G)} , let N(v)={u ? V(G): uv ? E(G)}{N(v)=\{u \in V(G): uv \in E(G)\}} , NC(G) = min{|N(u) èN(v)|: u, v ? V(G){NC(G)= \min \{|N(u) \cup N(v)|: u, v \in V(G)} and uv \not ? E(G)}{uv \not \in E(G)\}} , and NC₂(G) = min{|N(u) èN(v)|: u, v ? V(G){NC_2(G)= \min\{|N(u) \cup N(v)|: u, v \in V(G)} and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any u, v ? V(G){u, v \in V(G)} , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.     

On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

Isometric embeddings of Johnson graphs in Grassmann graphs

Let V be an n-dimensional vector space (4≤n<∞) and let G_k(V){\mathcal{G}}_{k}(V) be the Grassmannian formed by all k-dimensional subspaces of V. The corresponding Grassmann graph will be denoted by Γ _k (V). We describe all isometric embeddings of Johnson graphs J(l,m), 1<m<l−1 in Γ _k (V), 1<k<n−1 (Theorem 4). As a consequence, we get the following: the image of every isometric embedding of J(n,k) in Γ _k (V) is an apartment of G_k(V){\mathcal{G}}_{k}(V) if and only if n=2k. Our second result (Theorem 5) is a classification of rigid isometric embeddings of Johnson graphs in Γ _k (V), 1<k<n−1.     

The binding number of line graphs and total graphs

D.R. Woodall [7] introduced the concept of the binding number of a graphG, bind (G), and proved that bind(G)≦(|V(G)|−1)/(|V(G)|−ρ(G)). In this paper, some properties of a graph with bind(G)=(|V(G)|−1)/(|V(G)|−ρ(G)) are given, and the binding number of some line graphs and total graphs are determined.     

Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any , let , and , and and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.      

Some results on distance two labelling of outerplanar graphs

Let G be an outerplanar graph with maximum degree △. Let χ（G^2） and A（G） denote the chromatic number of the square and the L（2, 1）-labelling number of G, respectively. In this paper we prove the following results： （1） χ（G^2） = 7 if △= 6; （2） λ（G） ≤ △ ＋5 if △ ≥ 4, and ）,（G）≤ 7 if △ = 3; and （3） there is an outerplanar graph G with △ = 4 such that ）λ（G） = 7. These improve some known results on the distance two labelling of outerplanar graphs.     

The chromatic number of the product of two 4-chromatic graphs is 4

For any graphG and numbern≧1 two functionsf, g fromV(G) into {1, 2, ...,n} are adjacent if for all edges (a, b) ofG, f(a) ≠g(b). The graph of all such functions is the colouring graph ℒ(G) ofG. We establish first that χ(G)=n+1 implies χ(ℒ(G))=n iff χ(G ×H)=n+1 for all graphsH with χ(H)≧n+1. Then we will prove that indeed for all 4-chromatic graphsG χ(ℒ(G))=3 which establishes Hedetniemi’s [3] conjecture for 4-chromatic graphs. This research was supported by NSERC grant A7213     

On the Upper Bounds of the Numbers of Perfect Matchings in Graphs with Given Parameters

Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!].     

Acyclic edge colorings of planar graphs and seriesparallel graphs

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1. This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation of Shandong Province (Grant No. Y2008A20).     

On the maximal number of certain subgraphs inK r -free graphs

Given two graphsH andG, letH(G) denote the number of subgraphs ofG isomorphic toH. We prove that ifH is a bipartite graph with a one-factor, then for every triangle-free graphG withn verticesH(G) H(T ₂(n)), whereT ₂(n) denotes the complete bipartite graph ofn vertices whose colour classes are as equal as possible. We also prove that ifK is a completet-partite graph ofm vertices,r > t, n max(m, r – 1), then there exists a complete (r – 1)-partite graphG* withn vertices such thatK(G) K(G*) holds for everyK _r -free graphG withn vertices. In particular, in the class of allK _r -free graphs withn vertices the complete balanced (r – 1)-partite graphT _r–1(n) has the largest number of subgraphs isomorphic toK _t (t < r),C ₄,K _2,3. These generalize some theorems of Turán, Erdös and Sauer.Dedicated to Paul Turán on his 80th Birthday     

Score sets in oriented 3-partite graphs

Let D(U, V, W) be an oriented 3-partite graph with |U|=p, |V|=q and |W|= r. For any vertex x in D(U, V, W), let d x and d-x be the outdegree and indegree of x respectively. Define aui (or simply ai) = q r d ui - d-ui, bvj(or simply bj) = p r d vj - d-vj and Cwk (or simply ck) = p q d wk - d-wk as the scores of ui in U, vj in V and wk in Wrespectively. The set A of distinct scores of the vertices of D(U, V, W) is called its score set. In this paper, we prove that if a1 is a non-negative integer, ai(2≤i≤n - 1) are even positive integers and an is any positive integer, then for n≥3, there exists an oriented 3-partite graph with the score set A = {a1,2∑i=1 ai,…,n∑i=1 ai}, except when A = {0,2,3}. Some more results for score sets in oriented 3-partite graphs are obtained.     

The Fractional Chromatic Number Of The Categorical Product Of Graphs

We prove that the identity

On a graph property generalizing planarity and flatness

We introduce a topological graph parameter σ(G), defined for any graph G. This parameter characterizes subgraphs of paths, outerplanar graphs, planar graphs, and graphs that have a flat embedding as those graphs G with σ(G)≤1,2,3, and 4, respectively. Among several other theorems, we show that if H is a minor of G, then σ(H)≤σ(G), that σ(K _n )=n−1, and that if H is the suspension of G, then σ(H)=σ(G)+1. Furthermore, we show that μ(G)≤σ(G) + 2 for each graph G. Here μ(G) is the graph parameter introduced by Colin de Verdière in [2].     

Some results on R 2-edge-connectivity of even regular graphs

Let G be a connected k(≥3)-regular graph with girth g. A set S of the edges in G is called an Rredge-cut if G-S is disconnected and comains neither an isolated vertex nor a one-degree vertex. The R2-edge-connectivity of G, denoted by λ^n(G), is the minimum cardinality over all R2-edge-cuts, which is an important measure for fault-tolerance of computer interconnection networks. In this paper, λ^n(G)=g(2k-2) for any 2k-regular connected graph G (≠K5) that is either edge-transitive or vertex-transitive and g≥5 is given.     

The number of K m,m -free graphs

A graph is called H-free if it contains no copy of H. Denote by f _n (H) the number of (labeled) H-free graphs on n vertices. Erdős conjectured that f _n (H) ≤ 2^{(1+o(1))ex(n,H)}. This was first shown to be true for cliques; then, Erdős, Frankl, and R?dl proved it for all graphs H with χ(H)≥3. For most bipartite H, the question is still wide open, and even the correct order of magnitude of log₂ f _n (H) is not known. We prove that f _n (K _m,m ) ≤ 2 ^O (n ^2−1/m ) for every m, extending the result of Kleitman and Winston and answering a question of Erdős. This bound is asymptotically sharp for m∈{2,3}, and possibly for all other values of m, for which the order of ex(n,K _m,m ) is conjectured to be Θ(n ^2−1/m ). Our method also yields a bound on the number of K _m,m -free graphs with fixed order and size, extending the result of Füredi. Using this bound, we prove a relaxed version of a conjecture due to Haxell, Kohayakawa, and Łuczak and show that almost all K _3,3-free graphs of order n have more than 1/20·ex(n,K _3,3) edges.