Coloring hypercomplete and hyperpath graphs

Authors : Yusuf CİVAN, Demet TAYLAN

Pages : 1-15

Doi:10.3906/mat-1301-60

View : 17 | Download : 8

Publication Date : 0000-00-00

Article Type : Research Paper

Abstract :Given a graph G with an induced subgraph H and a family F of graphs, we introduce a insert ignore into journalissuearticles values(hyper);graph HHinsert ignore into journalissuearticles values(G;F);=insert ignore into journalissuearticles values(VH, EH);, the hyper-H insert ignore into journalissuearticles values(hyper);graph of G with respect to F, whose vertices are induced copies of H in G, and \{H1,H2,\ldots,Hr\} \in EH if and only if the induced subgraph of G by the set \cupi=1r Hi 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 HKkinsert ignore into journalissuearticles values(G;F); and HPkinsert ignore into journalissuearticles values(G;F); to Hkinsert ignore into journalissuearticles values(G;F); and HPkinsert ignore into journalissuearticles values(G;F);, respectively. Our motivation to introduce this new insert ignore into journalissuearticles values(hyper);graph operator on graphs comes from the fact that the graph Hkinsert ignore into journalissuearticles values(Kn;\{K2k\}); is isomorphic to the ordinary Kneser graph Kinsert ignore into journalissuearticles values(n;k); whenever 2k \leq n. As a generalization of the Lovász--Kneser theorem, we prove that cinsert ignore into journalissuearticles values(Hkinsert ignore into journalissuearticles values(G;\{K2k\}););=cinsert ignore into journalissuearticles values(G);-2k+2 for any graph G with winsert ignore into journalissuearticles values(G);=cinsert ignore into journalissuearticles values(G); and any integer k\leq \lfloor winsert ignore into journalissuearticles values(G);/2\rfloor. We determine the clique and fractional chromatic numbers of Hkinsert ignore into journalissuearticles values(G;\{K2k\});, and we consider the generalized Johnson graphs Hrinsert ignore into journalissuearticles values(H;\{Kr+1\}); and show that cinsert ignore into journalissuearticles values(Hrinsert ignore into journalissuearticles values(H;\{Kr+1\}););\leq cinsert ignore into journalissuearticles values(H); for any graph H and any integer r< winsert ignore into journalissuearticles values(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 insert ignore into journalissuearticles values(hyper);graphs HPkinsert ignore into journalissuearticles values(G;Pm);, and we provide upper bounds when m=k+1 and m=2k in terms of the k-distance chromatic number of the source graph.
Keywords : Kneser graphs and hypergraphs, chromatic and fractional chromatic numbers, hypercomplete and hyperpath hyper, graphs