Akademik Veri Yönetim Sistemi
TURKISH JOURNAL OF MATHEMATICS, cilt.38, sa.1, ss.1-15, 2014 (SCI-Expanded)
Given a graph G with an induced subgraph H and a family F of graphs, we introduce a (hyper)graph H-H(G; F) = (nu(H), epsilon(H)), the hyper- H (hyper) graph of G with respect to F, whose vertices are induced copies of H in G, and {H-1, H-2, ... , H-r} is an element of epsilon(H) if and only if the induced subgraph of G by the set U-iota=1(r) H-i is isomorphic to a graph F in the family F, and the integer r is the least integer for F with this property. When H is a k-complete or a k-path of G, we abbreviate H-Kk (G; F) and H-Pk (G; F) to H-k (G; F) and HPk(G; F), respectively. Our motivation to introduce this new (hyper)graph operator on graphs comes from the fact that the graph H-k(K-n; {K-2k}) is isomorphic to the ordinary Kneser graph K (n; k) whenever 2k <= n. As a generalization of the Lovasz-Kneser theorem, we prove that chi(H-k(G; {K-2k})) = chi(G) - 2k + 2 for any graph G with omega(G) = chi(G) and any integer k <= left perpendicular omega(G)/2right perpendicular. We determine the clique and fractional chromatic numbers of lik(G; {K2k}), and we consider the generalized Johnson graphs H-r(H; {Kr+1}) and show that chi(H-r (H; {Kr+1})) <= chi(H) for any graph H and any integer r < omega(H). By way of application, we construct examples of graphs such that the gap between their chromatic and fractional chromatic numbers is arbitrarily large. We further analyze the chromatic number of hyperpath (hyper)graphs HPk(G; P-m), and we provide upper bounds when m = k + 1 and m = 2k in terms of the k-distance chromatic number of the source graph.