Mycielski type constructions for hypergraphs associated with fractional colorings

详细信息    查看全文

• 作者：J. Luviano ; A. Montejano ; L. Montejano…
• 关键词：Fractional chromatic number of hypergraphs ; Mycielski construction ; Uniform hypergraphs ; 05C15 ; 05C65
• 刊名：Bolet篓陋n de la Sociedad Matem篓垄tica Mexicana
• 出版年：2014
• 出版时间：April 2014
• 年：2014
• 卷：20
• 期：1
• 页码：1-16
• 全文大小：613 KB
• 参考文献：1.Berge, C.: Hypergraphs: Combinatorics of Finite Sets. In: North-Holland Mathematical Library, vol. 45 (1989)
  2.Chudnovsky, M., Seymour, P.: Claw-free Graphs VI. Coloring claw-free graphs. J. Combin. Theory. Ser B 100, 560-72 (2010)
  3.Danzer, L., Grünbaum, B., Klee, V.: Helly’s theorem and its relatives. In: Proc. Symposia in Pure Math. vol. VII (Convexity), pp. 101-80 (1963)
  4.Erd?s, P.: Graph theory and probability. Can. J. Math. 11, 34-8 (1959)CrossRef
  5.Erd?s, P., Hajnal, A.: On chromatic number of graphs and set systems. Acta Math. Acad. Sei. Hungar. 17, 61-9 (1966)CrossRef
  6.Godsil, C., Royle, G.: Algebraic graph theory. In: Graduate Texts in Mathematics, vol. 207. Springer, Berlin (2001)
  7.Gyárfás, A.: Problems from the world surrounding perfect graphs. Zastosow. Mat. 19, 413-31 (1987)MATH
  8.Hadwiger, H., Debrunner, H.: Kombinatorische Geometrie in der Ebene. In: Monographies de l’Enseignement Mathematique, No. 2, Geneva (1960)
  9.Kierstead, H., Penrice, S.: Radius two trees specify v-bounded classes. J. Graph Theory 18, 119-29 (1994)CrossRef MATH MathSciNet
  10.Larsen, M., Propp, J., Ullman, D.H.: The fractional chromatic number of Mycielski graphs. J. Graph Theory 19, 411-16 (1995)CrossRef MATH MathSciNet
  11.Lovász, L.: On chromatic number of finite set-systems. Acta Math. Acad. Sci. Hungar. 19, 59-7 (1968)CrossRef MATH MathSciNet
  12.Mycielski, J.: Sur le coloriage des graphes. Colloq. Math. 3, 161-62 (1955)MATH MathSciNet
  13.Ne?et?il, J., R?dl, V.: A short proof of the existence of highly chromatic hypergraphs without short cycles. J. Combin. Theory Ser. B 27, 225-27 (1979)CrossRef MATH MathSciNet
  14.Randerath, B., Schiermeyer, I.: Vertex Colouring and Forbidden Subgraphs: A Survey. Graphs Combin. 20, 1-0 (2004)CrossRef MATH MathSciNet
  15.Scheinerman, E.R., Ullman, D.H.: Fractional Graph Theory. Wiley, New York (2008)
  
• 作者单位：J. Luviano (1)
  A. Montejano (2)
  L. Montejano (1)
  D. Oliveros (1)
  
  1. Instituto de Matemáticas, Universidad Nacional Autónoma de México, Juriquilla, Queretaro, México
  2. Facultad de Ciencias, Universidad Nacional Autónoma de Mexico, Juriquilla, Queretaro, México
  
• 刊物类别：Mathematics, general;
• 刊物主题：Mathematics, general;
• 出版者：Springer International Publishing
• ISSN：2296-4495

文摘

It is known that the gap between the clique number and the chromatic number of a graph \(G\) can be arbitrarily large. The fractional chromatic number satisfies \(\omega (G)\le \chi _f(G) \le \chi (G)\). Larsen et al. (J Graph Theory 19:411-16, 1995) use the Mycielski construction to show that the gap in both of those inequalities can also be arbitrarily large. In this work, we prove the analogous result for the fractional versions of both weak and strong chromatic numbers of uniform hypergraphs. We shall remark that for strong fractional colorings the Mycielski construction and the proof of Larsen et al. can be generalized. For weak fractional colorings, however, the same is not true. We then propose an alternative construction to handle weak fractional colorings of uniform hypergraphs. Finally, we describe, by forbidden induced subgraphs, an interesting class of \(r\)-uniform hypergraphs with the property that the chromatic number is bounded by a function of its clique number. Such a family arises from affine planes of dimension \(r-2\) in \(\mathbb {RP}^{d}\). Keywords Fractional chromatic number of hypergraphs Mycielski construction Uniform hypergraphs