超图中的着色问题

本文是近三十年来有关超图中涉及的着色问题的综述。它包含了有关超图着色中的基本结果,临界可着色性,２－可着色性,非２－可着色性以及在超图中与顶点着色、边着色和其它着色相关的极值问题。     

线图泛圈性的一个充分条件

本文证明了如果Ｇ是２连通线图,Ｇ不是圈,ｎ＝｜Ｖ（Ｇ）｜≥９且Ｇ的每个同构于Ａ的导出子图都满足（ａ１,ａ２）,则Ｇ是泛圈图     

Uniform Mixed Hypergraphs: The Possible Numbers of Colors

For a mixed hypergraph , where and are set systems over the vertex set X, a coloring is a partition of X into ‘color classes’ such that every meets some class in more than one vertex, and every has a nonempty intersection with at least two classes. The feasible set of , denoted , is the set of integers k such that admits a coloring with precisely k nonempty color classes. It was proved by Jiang et al. [Graphs and Combinatorics 18 (2002), 309–318] that a set S of natural numbers is the feasible set of some mixed hypergraph if and only if either or S is an ‘interval’ for some integer k ≥ 1. In this note we consider r-uniform mixed hypergraphs, i.e. those with |C| = |D| = r for all and all , r ≥ 3. We prove that S is the feasible set of some r-uniform mixed hypergraph with at least one edge if and only if either for some natural number k ≥ r − 1, or S is of the form where S′′ is any (possibly empty) subset of and S′ is either the empty set or {r − 1} or an ‘interval’ {k, k + 1, ..., r − 1} for some k, 2 ≤ k ≤ r − 2. We also prove that all these feasible sets can be obtained under the restriction , i.e. within the class of ‘bi-hypergraphs’. Research supported in part by the Hungarian Scientific Research Fund, OTKA grant T-049613.     

Enumeration of Maximum Acyclic Hypergraphs

Abstract Acyclic hypergraphs are analogues of forests in graphs.They are very useful in the design ofdatabases. In this article,the maximum size of an acvclic hypergraph is determined and the number of maximumγ-uniform acyclic hypergraphs of order n is shown to be (_(r-1)~n)(n(r-1)-r~2 2r)~(n-r-1).     

无标号真严格(d)-连通无圈超图的计数

本文得到了无标号真严格(d)-连通无圈超图的计数公式,并得到了无标号真严格(d)-连通同胚k不可约无圈超图的计数公式.     

4一致(ξ)-超图的最小边数的上界

主要讨论了4一致l-超图的最小边数与最小上色数的关系,给出了上色数为3的4一致l-超图的最小边数的一个上界.     

Forbidding Complete Hypergraphs as Traces

Let 2 ≤q ≤min{p, t − 1} be fixed and n → ∞. Suppose that is a p-uniform hypergraph on n vertices that contains no complete q-uniform hypergraph on t vertices as a trace. We determine the asymptotic maximum size of in many cases. For example, when q = 2 and p∈{t, t + 1}, the maximum is , and when p = t = 3, it is for all n≥ 3. Our proofs use the Kruskal-Katona theorem, an extension of the sunflower lemma due to Füredi, and recent results on hypergraph Turán numbers. Research supported in part by NSF grants DMS-0400812 and an Alfred P. Sloan Research Fellowship. Research supported in part by NSA grant H98230-06-1-0140. Part of the research conducted while his working at University of Illinois at Chicago as a NSF VIGRE postdot.     

Super-Magic Complete k-Partite Hypergraphs

 We deal with complete k-partite hypergraphs and we show that for all k≥2 and n≠2,6 its hyperedges can be labeled by consecutive integers 1,2,…,n ^k such that the sum of labels of the hyperedges incident to (k−1) particular vertices is the same for all (k−1)-tuples of vertices from (k−1) independent sets. Received: December 8, 1997 Final version received: July 26, 1999     

r-一致超图Ramsey函数的渐近下界(英文)

本文利用Lovasz局部引理的Spencer形式和对称形式给出r-一致超图Ramsey函数的渐近下界.证明了:对于任意取定的正整数f0,使得当n→∞时,有R~((r))(m~l,n~(k-l))≥(c-o(1))(n~(r-1)/logn)~■.特别地,R~((r))_k(n)≥(1-o(1))n/e k~■(n→∞).对于任意取定的正整数s≥r+1和常数δ>0,α≥0,如果F表示阶为s的r-一致超图,■表示阶为t的r-一致超图,且■的边数满足m(■)≥(δ-o(1))t~r/(logt)α(t→∞),则存在c=c(s,δ,α)>0,使得R~((r))(F,■)≥(c-o(1))(t~(r-1)/(logt)~l+(r-l)α)~(m(F)-l/s-r).     

混合超图的染色理论

混合超图是含有两种超边的超图，一种称为D-超边，一种称为C-超边，它们的区别主要体现在染色要求上．混合超图的染色，要求每-D-超边至少有两个点染不同的颜色，每一C-超边至少有两个点染相同的颜色．用颜色最多的染色所用的颜色数称为该混合超图的上色数，用颜色最少的染色所用的颜色数称为该混合超图的下色数．混合超图的染色理论是目前国际组合学界比较新的研究课题之一．本文主要概括介绍关于混合超图染色理论已经取得的一些成果，其中包含本文作者的研究成果．并提出了一些可供进一步研究的问题．     

Perfect Matchings and K 4 3 -Tilings in Hypergraphs of Large Codegree

For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function $t_{k-1} (kn, 0, K_k^k)For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function (i.e. when we want to guarantee a perfect matching) has been previously determined by Kühn and Osthus [9] (asymptotically) and by R?dl, Ruciński, and Szemerédi [13] (exactly). Here we obtain asymptotic formulae for some other l. Namely, we prove that for any and , . Also, we present various bounds in another special but interesting case: t ₂(n, m, K ₄³) with m = 0 or m = o(n), that is, when we want to tile (almost) all vertices by copies of K ₄³, the complete 3-graph on 4 vertices. Reverts to public domain 28 years from publication. Oleg Pikhurko: Partially supported by the National Science Foundation, Grant DMS-0457512.     

Hypergraphs and the Clar problem in hexagonal systems

We show that for a hypergraph H that is separable and has the Helly property, the perfect matchings of H are the strongly stable sets of the line graph of H. Also, we show that the hypergraph generated by a hexagonal system is separable and has the Helly property. Finally, we note that the Clar problem of a hexagonal system is a minimum cardinality perfect matching problem of the hypergraph generated by the hexagonal system. Hence, the Clar problem of a hexagonal system is a minimum cardinality strongly stable set problem in the line graph of the hypergraph generated by the hexagonal system.     

秩为r的本原超图的指数集(英文)

本文研究了超图的本原性质.运用图论方法,得到了具有秩r(≥3)的所有n阶本原有向超图的指数集,并刻划了其极超图.     

Hypergraphs induced by algebras of fixed type

A characterization of the weak subalgebra lattice of a partial algebra of a fixed type is a natural algebraic problem. In Pióro (2000, 2002) [13] and [15] we have shown that this algebraic problem is equivalent to the following hypergraph question, interesting in itself: When can edges of a hypergraph be directed to form a partial algebra of a fixed type (equivalently, to form a directed hypergraph of a fixed type)? This problem will be solved in the present paper.     

图G为自构线图的充要条件

首次给出自构线图的定义,并证明:简单图G为自构线图的充要条件是图G为2-正则简单图.     

2-边连通图的线图的P3因子

如果图G有一个生成子图使得这个生成子图的每一个分支都是3个点的路,则称G有P3-因子．本文证明了对任何一个2-边连通图G,只要G的边数能被3整除,则G的线图就有P3-因子。     

On the α-spectra of Uniform Hypergraphs and Its Associated Graphs

For 0 ≤α 1 and a k-uniform hypergraph H, the tensor A_α(H) associated with H is defined as A_α(H) = αD(H) +(1-α)A(H), where D(H) and A(H) are the diagonal tensor of degrees and the adjacency tensor of H, respectively. The α-spectra of H is the set of all eigenvalues of A_α(H) and the α-spectral radius ρ_α(H) is the largest modulus of the elements in the spectrum of A_α(H). In this paper we define the line graph L(H) of a uniform hypergraph H and prove that ρ_α(H) ≤■ρ_α(L(H)) + 1 + α(Δ-1-δ~*/k), where Δ and δ~* are the maximum degree of H and the minimum degree of L(H), respectively. We also generalize some results on α-spectra of G~(k,s), which is obtained from G by blowing up each vertex into an s-set and each edge into a k-set where 1 ≤ s ≤ k/2.