Coloring hypercomplete and hyperpath graphs

Given a graph G with an induced subgraph H and a family F of graphs, we introduce a (hyper)graph HH(G;F)=(VH, EH), the hyper-H (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 HKk(G;F) and HPk(G;F) to Hk(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 Hk(Kn;\{K2k\}) 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 c(Hk(G;\{K2k\}))=c(G)-2k+2 for any graph G with w(G)=c(G) and any integer k\leq \lfloor w(G)/2\rfloor. We determine the clique and fractional chromatic numbers of Hk(G;\{K2k\}), and we consider the generalized Johnson graphs Hr(H;\{Kr+1\}) and show that c(Hr(H;\{Kr+1\}))\leq c(H) for any graph H and any integer r< w(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;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.

Anahtar Kelimeler:

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

Coloring hypercomplete and hyperpath graphs

Keywords:

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

PDF

___

Alon N, Frankl P, Lov´ asz L. The chromatic number of Kneser hypergraphs. Trans Amer Math Soc 1986; 298: 359–370.
Alon N, Lubetzky E. Independent sets in tensor graph powers. J Graph Theory 2007; 54: 73–87.
Brandstadt A, Le VB, Spinrad JP. Graph Classes: A Survey. Philadelphia, PA, USA: SIAM Monographs on Discrete Mathematics and Applications, 1999.
Erd¨ os P. Problems and results in combinatorial analysis. In: International Colloquium on Combinatorial Theory 19 Rome: Acad Naz Lincei, 1976; 3–17.
Hamburger P, Por A, Walsh M. Kneser representations of graphs. SIAM J Discrete Math 2009; 23: 1071–1081.
Hilton AJW, Spencer CL. A graph-theoretical generalizations of Berge’s analogue of the Erd¨ os-Ko-Rado theorem. Trends in Math 2006; 225–242.
Katona GOH. A simple proof of the Erd¨ os-Chao Ko-Rado theorem. J Combin Theory Ser B 1972; 13: 183–184. Kneser M. Jahresbericht der Deuctschen Mathematiker-Vereinigung. Aufgabe 360, Ableilung 1978; 58:2: S 27.
Kriz I. Equivariant cohomology and lower bounds for chromatic numbers. Trans Amer Math Soc 1992; 333: 567–577.
Lange C, Ziegler G. On generalized Kneser hypergraph colorings. J Combin Theory Ser A 2007; 114: 159–166.
Lov´ asz L. Kneser’s conjecture, chromatic number, and homotopy. J Combin Theory Ser A 1978; 25: 319–324.
Matou ˇ s ek J. Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. Heidelberg: Springer-Verlag, 2003.
Sarkaria K. A generalized Kneser conjecture. J Combin Theory Ser B 1990; 49: 236–240.
Scheinerman E, Ullman D. Fractional Graph Theory. New York: Wiley-Interscience, 1997.
Schrijver A. Vertex-critical subgraphs of Kneser graphs. Nieuw Arch Wiskd III Ser 1978; 26: 454–461.
Stahl S. n-tuple colorings and associated graphs. J Combin Theory Ser B 1976; 20: 185–203.
Ziegler G. Generalized Kneser coloring theorems with combinatorial proofs. Inventiones Math 2002; 147: 671–691.