Uniform Hypergraphs under Certain Intersection Constraints between Hyperedges

A hypergraph H is an(n,m)-hypergraph if it contains n vertices and m hyperedges,where n≥1 and m≥ 0 are two integers.Let k be a positive integer and let L be a set of nonnegative integers.A hyper graph H is k-uniform if all its hyperedges have the same size k,and H is L-intersecting if the number of common vertices of every two hyperedges belongs to L.In this paper,we propose and investigate the problem of estimating the maximum k among all k-uniform L-intersecting(n,m)-hypergraphs for fixed n,m ...     

Some Properties of Chromatic Coefficients of Linear Uniform Hypergraphs

In this paper a formula for the coefficient of λ ^n-gh+g-1 in the chromatic polynomial of a linear h-uniform hypergraph H of order n and girth g is proposed provided (g,  h) ≠ (3, 3). This formula involves 13 types of spanning subhypergraphs of H for 3 ≤ h ≤ 5.     

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.     

Recognizing Berge Graphs

A graph is Berge if no induced subgraph of G is an odd cycle of length at least five or the complement of one. In this paper we give an algorithm to test if a graph G is Berge, with running time O(|V (G)|⁹). This is independent of the recent proof of the strong perfect graph conjecture.* Currently this author is a Clay Mathematics Institute Research Fellow.** Supported by NSF grant DMI-0352885 and ONR grant N00014-97-1-0196. Supported by ONR grant N00014-01-1-0608, and NSF grant DMS-0070912. Supported by EPSRC grant GR/R35629/01.     

随机一致超图的关于H-因子的门槛函数

假设H和H（分别是具有h个顶点和n个顶点的r一致超图．我们称一个具有n/h个分支，且每个分支都同构于H的H的生成子图为H的一个H-因子．记α（H） = max{｜E′｜/｜V′｜-1 ｜}，其中的最大值取遍H的所有满足｜V’｜〉1的子超图（V’，E′）．δ（H）表示超图H的最小度．在本文中，我们证明了如果δ（H）〈α（H），那么P=p（n）=n-1／α（H）就是随机超图Hr（n，P）包含．H-因子的一个紧的门槛函数．也就是说，存在两个常数c和C使得对任意P=p（n）=cn-1／α（H），几乎所有的随机超图Hr（n，P）都不包含一个H-因子，对任意P=p（n）=cn-1／α（H），几乎所有的随机超图Hr（n，P）都包含一个H-因子．     

Recognizing Planar Strict Quasi-Parity Graphs

 A graph is a strict-quasi parity (SQP) graph if every induced subgraph that is not a clique contains a pair of vertices with no odd chordless path between them (an “even pair”). We present an O(n ³) algorithm for recognizing planar strict quasi-parity graphs, based on Wen-Lian Hsu's decomposition of planar (perfect) graphs and on the (non-algorithmic) characterization of planar minimal non-SQP graphs given in [9]. Received: September 21, 1998 Final version received: May 9, 2000     

Recognizing String Graphs Is Decidable

Abstract. A graph is called a string graph if its vertices can be represented by continuous curves (``strings') in the plane so that two of them cross each other if and only if the corresponding vertices are adjacent. It is shown that there exists a recursive function f(n) with the property that every string graph of n vertices has a representation in which any two curves cross at most f(n) times. We obtain as a corollary that there is an algorithm for deciding whether a given graph is a string graph. This solves an old problem of Benzer (1959), Sinden (1966), and Graham (1971).     

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.     

Recognizing String Graphs Is Decidable

   Abstract. A graph is called a string graph if its vertices can be represented by continuous curves (``strings') in the plane so that two of them cross each other if and only if the corresponding vertices are adjacent. It is shown that there exists a recursive function f(n) with the property that every string graph of n vertices has a representation in which any two curves cross at most f(n) times. We obtain as a corollary that there is an algorithm for deciding whether a given graph is a string graph. This solves an old problem of Benzer (1959), Sinden (1966), and Graham (1971).     

Tiling 3‐Uniform Hypergraphs With

Let denote the hypergraph consisting of two triples on four points. For an integer n, let denote the smallest integer d so that every 3‐uniform hypergraph G of order n with minimum pair‐degree contains vertex‐disjoint copies of . Kühn and Osthus (J Combin Theory, Ser B 96(6) (2006), 767–821) proved that holds for large integers n. Here, we prove the exact counterpart, that for all sufficiently large integers n divisible by 4, A main ingredient in our proof is the recent “absorption technique” of Rödl, Ruciński, and Szemerédi (J. Combin. Theory Ser. A 116(3) (2009), 613–636).     

Choosability with Separation of Complete Multipartite Graphs and Hypergraphs

For a hypergraph G and a positive integer s, let be the minimum value of l such that G is L‐colorable from every list L with for each and for all . This parameter was studied by Kratochvíl, Tuza, and Voigt for various kinds of graphs. Using randomized constructions we find the asymptotics of for balanced complete multipartite graphs and for complete k‐partite k‐uniform hypergraphs.