On the diameter of generalized Kneser graphs

Let r, k be positive integers, s(<r), a nonnegative integer, and n=2r-s+k. The set of r-subsets of [n]={1,2,…,n} is denoted by [n]^r. The generalized Kneser graph K(n,r,s) is the graph whose vertex-set is [n]^r where two r-subsets A and B are joined by an edge if |A∩B|?s. This note determines the diameter of generalized Kneser graphs. More precisely, the diameter of K(n,r,s) is equal to , which generalizes a result of Valencia-Pabon and Vera [On the diameter of Kneser graphs, Discrete Math. 305 (2005) 383-385].     

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.     

Partial characterizations of coordinated graphs: line graphs and complements of forests

A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color is equal to the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The list of minimal forbidden induced subgraphs for the class of coordinated graphs is not known. In this paper, we present a partial result in this direction, that is, we characterize coordinated graphs by minimal forbidden induced subgraphs when the graph is either a line graph, or the complement of a forest. F. Bonomo, F. Soulignac, and G. Sueiro’s research partially supported by UBACyT Grant X184 (Argentina), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil). The research of G. Durán is partially supported by FONDECyT Grant 1080286 and Millennium Science Institute “Complex Engineering Systems” (Chile), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil).     

On s-hamiltonian line graphs of claw-free graphs

For an integer $s\ge 0$, a graph $G$ is $s$-hamiltonian if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian, and $G$ is $s$-hamiltonian connected if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of $s$-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for $s\ge 2$, a line graph $L\left(G\right)$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected. In this paper we prove the following.(i) For an integer $s\ge 2$, the line graph $L\left(G\right)$ of a claw-free graph $G$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected.(ii) The line graph $L\left(G\right)$ of a claw-free graph $G$ is 1-hamiltonian connected if and only if $L\left(G\right)$ is 4-connected.     

On the Zagreb indices of the line graphs of the subdivision graphs

The aim of this paper is to investigate the Zagreb indices of the line graphs of the tadpole graphs, wheel graphs and ladder graphs using the subdivision concepts.     

Independence number of products of Kneser graphs

We study the independence number of a product of Kneser graph $K(n,k)$ with itself, where we consider all four standard graph products. The cases of the direct, the lexicographic and the strong product of Kneser graphs are not difficult (the formula for $\alpha (K(n,k)⊠K(n,k))$ is presented in this paper), while the case of the Cartesian product of Kneser graphs is much more involved. We establish a lower bound and an upper bound for the independence number of $K(n,2)\square K(n,2)$, which are asymptotically tending to $n^3∕3$ and $3n^3∕8$, respectively. The former is obtained by a construction, which differs from the standard diagonalization procedure, while for the upper bound the $\ell$-independence number of Kneser graphs can be applied. We also establish some constructions in odd graphs $K(2k+1,k)$, which give a lower bound for the 2-independence number of these graphs, and prove that two such constructions give the same lower bound as a previously known one. Finally, we consider the $s$-stable Kneser graphs $K{(ks+1,k)}_{s-stab}$, derive a formula for their $\ell$-independence number, and give the exact value of the independence number of the Cartesian square of $K{(ks+1,k)}_{s-stab}$.     

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.     

A new coloring theorem of Kneser graphs

In 1997, Johnson, Holroyd and Stahl conjectured that the circular chromatic number of the Kneser graphs KG(n,k) is equal to the chromatic number of these graphs. This was proved by Simonyi and Tardos (2006) [13] and independently by Meunier (2005) [10], if χ(KG(n,k)) is even. In this paper, we propose an alternative version of Kneser's coloring theorem to confirm the Johnson-Holroyd-Stahl conjecture.     

On the locating chromatic number of Kneser graphs

Let c be a proper k-coloring of a connected graph G and Π=(C₁,C₂,…,C_k) be an ordered partition of V(G) into the resulting color classes. For a vertex v of G, the color code of v with respect to Π is defined to be the ordered k-tuple c_Π(v):=(d(v,C₁),d(v,C₂),…,d(v,C_k)), where d(v,C_i)=min{d(v,x)|x∈C_i},1≤i≤k. If distinct vertices have distinct color codes, then c is called a locating coloring. The minimum number of colors needed in a locating coloring of G is the locating chromatic number of G, denoted by χ_L(G). In this paper, we study the locating chromatic number of Kneser graphs. First, among some other results, we show that χ_L(KG(n,2))=n−1 for all n≥5. Then, we prove that χ_L(KG(n,k))≤n−1, when n≥k². Moreover, we present some bounds for the locating chromatic number of odd graphs.     

Hamilton decompositions of graphs with primitive complements

A k-factor of a graph is a k-regular spanning subgraph. A Hamilton cycle is a connected 2-factor. A graph G is said to be primitive if it contains no k-factor with 1≤k<Δ(G). A Hamilton decomposition of a graph G is a partition of the edges of G into sets, each of which induces a Hamilton cycle. In this paper, by using the amalgamation technique, we find necessary and sufficient conditions for the existence of a 2x-regular graph G on n vertices which:

1.

has a Hamilton decomposition, and

2.

has a complement in K_n that is primitive.

This extends the conditions studied by Hoffman, Rodger, and Rosa [D.G. Hoffman, C.A. Rodger, A. Rosa, Maximal sets of 2-factors and Hamiltonian cycles, J. Combin. Theory Ser. B 57 (1) (1993) 69-76] who considered maximal sets of Hamilton cycles and 2-factors. It also sheds light on construction approaches to the Hamilton-Waterloo problem.     

Boxicity of series-parallel graphs

We show that there exist series-parallel graphs with boxicity 3.     

Boxicity of Halin graphs

A k-dimensional box is the Cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if G is a Halin graph that is not isomorphic to K₄, then . In fact, we prove the stronger result that if G is a planar graph formed by connecting the leaves of any tree in a simple cycle, then unless G is isomorphic to K₄ (in which case its boxicity is 1).