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.     

Improvement on Brooks' chromatic bound for a class of graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and K_n+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K_1,3;K₅?e and H) as an induced subgraph and if Δ(G)?6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)?6 can not be non-trivially relaxed and the graph K₅?e can not be removed from the hypothesis. Moreover, for a graph G with none of K_1,3;K₅?e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)?9 and d(G)<Δ(G), then χ(G)<Δ(G).     

On the chromaticity of complete multipartite graphs with certain edges added

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. For integers k≥0, t≥2, denote by K((t−1)×p,p+k) the complete t-partite graph that has t−1 partite sets of size p and one partite set of size p+k. Let K(s,t,p,k) be the set of graphs obtained from K((t−1)×p,p+k) by adding a set S of s edges to the partite set of size p+k such that 〈S〉 is bipartite. If s=1, denote the only graph in K(s,t,p,k) by K⁺((t−1)×p,p+k). In this paper, we shall prove that for k=0,1 and p+k≥s+2, each graph G∈K(s,t,p,k) is chromatically unique if and only if 〈S〉 is a chromatically unique graph that has no cut-vertex. As a direct consequence, the graph K⁺((t−1)×p,p+k) is chromatically unique for k=0,1 and p+k≥3.     

On graphs critical with respect to vertex partition numbers

For k?0, ?_k(G) denotes the Lick-White vertex partition number of G. A graph G is called (n, k)-critical if it is connected and for each edge e of G?_k(G–e)<?_k(G)=n. We describe all (2, k)-critical graphs and for n?3,k?1 we extend and simplify a result of Bollobás and Harary giving one construction of a family of (n, k)-critical graphs of every possible order.     

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.     

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.     

On the join of graphs and chromatic uniqueness

A graph is chromatically unique if it is uniquely determined by its chromatic polynomial. Let G be a chromatically unique graph and let K_m denote the complete graph on m vertices. This paper is mainly concerned with the chromaticity of K_m + G where + denotes the join of graphs. Also, it is shown that a large family of connected vertextransitive graphs that are not chromatically unique can be obtained by taking the join of some vertex-transitive graphs. © 1995 John Wiley & Sons, Inc.     

Independence and coloring properties of direct products of some vertex-transitive graphs

Let α(G) and χ(G) denote the independence number and chromatic number of a graph G, respectively. Let G×H be the direct product graph of graphs G and H. We show that if G and H are circular graphs, Kneser graphs, or powers of cycles, then α(G×H)=max{α(G)|V(H)|,α(H)|V(G)|} and χ(G×H)=min{χ(G),χ(H)}.     

Local coloring of Kneser graphs

A local coloring of a graph G is a function c:V(G)→N having the property that for each set S⊆V(G) with 2≤|S|≤3, there exist vertices u,v∈S such that |c(u)−c(v)|≥m_S, where m_S is the number of edges of the induced subgraph 〈S〉. The maximum color assigned by a local coloring c to a vertex of G is called the value of c and is denoted by χ_?(c). The local chromatic number of G is χ_?(G)=min{χ_?(c)}, where the minimum is taken over all local colorings c of G. The local coloring of graphs was introduced by Chartrand et al. [G. Chartrand, E. Salehi, P. Zhang, On local colorings of graphs, Congressus Numerantium 163 (2003) 207-221]. In this paper the local coloring of Kneser graphs is studied and the local chromatic number of the Kneser graph K(n,k) for some values of n and k is determined.     

Equivariant collapses and the homotopy type of iterated clique graphs

The clique graph K(G) of a simple graph G is the intersection graph of its maximal complete subgraphs, and we define iterated clique graphs by K⁰(G)=G, Kⁿ⁺¹(G)=K(Kⁿ(G)). We say that two graphs are homotopy equivalent if their simplicial complexes of complete subgraphs are so. From known results, it can be easily inferred that Kⁿ(G) is homotopy equivalent to G for every n if G belongs to the class of clique-Helly graphs or to the class of dismantlable graphs. However, in both of these cases the collection of iterated clique graphs is finite up to isomorphism. In this paper, we show two infinite classes of clique-divergent graphs that satisfy G?Kⁿ(G) for all n, moreover Kⁿ(G) and G are simple-homotopy equivalent. We provide some results on simple-homotopy type that are of independent interest.     

The equivariant topology of stable Kneser graphs

The stable Kneser graph SG_n,k, n?1, k?0, introduced by Schrijver (1978) [19], is a vertex critical graph with chromatic number k+2, its vertices are certain subsets of a set of cardinality m=2n+k. Björner and de Longueville (2003) [5] have shown that its box complex is homotopy equivalent to a sphere, Hom(K₂,SG_n,k)?Sk. The dihedral group D2m acts canonically on SG_n,k, the group C₂ with 2 elements acts on K₂. We almost determine the (C₂×D2m)-homotopy type of Hom(K₂,SG_n,k) and use this to prove the following results.The graphs SG_2s,4 are homotopy test graphs, i.e. for every graph H and r?0 such that Hom(SG_2s,4,H) is (r−1)-connected, the chromatic number χ(H) is at least r+6.If k∉{0,1,2,4,8} and n?N(k) then SG_n,k is not a homotopy test graph, i.e. there are a graph G and an r?1 such that Hom(SG_n,k,G) is (r−1)-connected and χ(G)<r+k+2.     

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.     

CLASSIFICATION OF COMPLETE 5-PARTITE GRAPHS AND CHROMATICITY OF 5-PARTITE GRAPHSWITH 5n VERTICES

For a graph G,P(G,λ)denotes the chromatic polynomial of G. Two graphs G and H are said to be chromatically equivalent,denoted by G-H,if P(G,λ)=p(H,λ). Let[G]= {H|H-G}. If [G]={G},then G is said to be chromatically unique. For a complete 5-partite graph G with 5n vertices, define θ(G)=(a(G,6)-2^n 1-2^n-1 5)/2n-2,where a(G,6) denotes the number of 6-independent partitions of G. In this paper, the authors show that θ(G)≥0 and determine all graphs with θ(G)= 0, 1, 2, 5/2, 7/2, 4, 17/4. By using these results the chromaticity of 5-partite graphs of the form G-S with θ(G)=0,1,2,5/2,7/2,4,17/4 is investigated,where S is a set of edges of G. Many new chromatically unique 5-partite graphs are obtained.     

Degree conditions for the partition of a graph into cycles, edges and isolated vertices

Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{d_G(x),d_G(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H₁,…,H_k such that V(H₁)∪?∪V(H_k)=V(G) and H_i is a cycle or K₁ or K₂ for each 1≤i≤k, unless k=2 and G=C₅, or k=3 and G=K₁∪C₅.     

Balanced decomposition of a vertex-colored graph

A balanced vertex-coloring of a graph G is a function c from V(G) to {−1,0,1} such that ∑{c(v):v∈V(G)}=0. A subset U of V(G) is called a balanced set if U induces a connected subgraph and ∑{c(v):v∈U}=0. A decomposition V(G)=V₁∪?∪V_r is called a balanced decomposition if V_i is a balanced set for 1≤i≤r.In this paper, the balanced decomposition number f(G) of G is introduced; f(G) is the smallest integer s such that for any balanced vertex-coloring c of G, there exists a balanced decomposition V(G)=V₁∪?∪V_r with |V_i|≤s for 1≤i≤r. Balanced decomposition numbers of some basic families of graphs such as complete graphs, trees, complete bipartite graphs, cycles, 2-connected graphs are studied.     

Bipartite rainbow numbers of matchings

Given two graphs G and H, let f(G,H) denote the maximum number c for which there is a way to color the edges of G with c colors such that every subgraph H of G has at least two edges of the same color. Equivalently, any edge-coloring of G with at least rb(G,H)=f(G,H)+1 colors contains a rainbow copy of H, where a rainbow subgraph of an edge-colored graph is such that no two edges of it have the same color. The number rb(G,H) is called the rainbow number ofHwith respect toG, and simply called the bipartite rainbow number ofH if G is the complete bipartite graph K_m,n. Erd?s, Simonovits and Sós showed that rb(K_n,K₃)=n. In 2004, Schiermeyer determined the rainbow numbers rb(K_n,K_k) for all n≥k≥4, and the rainbow numbers rb(K_n,kK₂) for all k≥2 and n≥3k+3. In this paper we will determine the rainbow numbers rb(K_m,n,kK₂) for all k≥1.     

The Ramsey number of paths with respect to wheels

For graphs G and H, the Ramsey numberR(G,H) is the smallest positive integer n such that every graph F of order n contains G or the complement of F contains H. For the path P_n and the wheel W_m, it is proved that R(P_n,W_m)=2n-1 if m is even, m?4, and n?(m/2)(m-2), and R(P_n,W_m)=3n-2 if m is odd, m?5, and n?(m-1/2)(m-3).     

Multicoloring and Mycielski construction

The generalized Mycielskians of graphs (also known as cones over graphs) are the natural generalization of the Mycielskians of graphs (which were first introduced by Mycielski in 1955). Given a graph G and any integer p?0, one can transform G into a new graph μ_p(G), the p-Mycielskian of G. In this paper, we study the kth chromatic numbers χ_k of Mycielskians and generalized Mycielskians of graphs. We show that χ_k(G)+1?χ_k(μ(G))?χ_k(G)+k, where both upper and lower bounds are attainable. We then investigate the kth chromatic number of Mycielskians of cycles and determine the kth chromatic number of p-Mycielskian of a complete graph K_n for any integers k?1, p?0 and n?2. Finally, we prove that if a graph G is a/b-colorable then the p-Mycielskian of G, μ_p(G), is (at+b^p+1)/bt-colorable, where . And thus obtain graphs G with m(G) grows exponentially with the order of G, where m(G) is the minimal denominator of a a/b-coloring of G with χ_f(G)=a/b.     

On graphs with equal domination and 2-domination numbers

Let G be a simple graph, and let p be a positive integer. A subset D⊆V(G) is a p-dominating set of the graph G, if every vertex v∈V(G)-D is adjacent to at least p vertices in D. The p-domination numberγ_p(G) is the minimum cardinality among the p-dominating sets of G. Note that the 1-domination number γ₁(G) is the usual domination numberγ(G). This definition immediately leads to the inequality γ(G)?γ₂(G).In this paper we present some sufficient as well as some necessary conditions for graphs G with the property that γ₂(G)=γ(G). In particular, we characterize all cactus graphs H with γ₂(H)=γ(H).     

Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs

Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by d_G(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, d_H(S)=d_G(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed.