•  
  •  
 

Turkish Journal of Mathematics

DOI

10.3906/mat-1301-60

Abstract

Given a graph G with an induced subgraph H and a family F of graphs, we introduce a (hyper)graph H_H(G;F)=(V_H, E_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,\ldots,H_r\} \in E_H if and only if the induced subgraph of G by the set \cup_{i=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_{K_k}(G;F) and H_{P_k}(G;F) to H_k(G;F) and HP_k(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 \leq n. As a generalization of the Lovász--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\leq \lfloor \omega(G)/2\rfloor. We determine the clique and fractional chromatic numbers of H_k(G;\{K_{2k}\}), and we consider the generalized Johnson graphs H_r(H;\{K_{r+1}\}) and show that \chi(H_r(H;\{K_{r+1}\}))\leq \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 HP_k(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.

Keywords

Kneser graphs and hypergraphs, chromatic and fractional chromatic numbers, hypercomplete and hyperpath (hyper)graphs

First Page

1

Last Page

15

Download

Included in

Mathematics Commons

Share

COinS