𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Complexity and Algorithms for Graph and Hypergraph Sandwich Problems

✍ Scribed by Yair Caro; Raphael Yuster

Publisher
Springer Japan
Year
1998
Tongue
English
Weight
231 KB
Volume
14
Category
Article
ISSN
0911-0119

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Digraph extremal problems, hypergraph ex
Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures
✍ W.G Brown; M Simonovits πŸ“‚ Article πŸ“… 1984 πŸ› Elsevier Science 🌐 English βš– 747 KB

We consider extremal problems 'of Tur~ type' for r-uniform ordered hypergraphs, where multiple oriented edges are permitted up to multiplicity q. With any such '(r, q)-graph' G" we associate an r-linear form whose maximum over the standard (n -1)-simplex in R" is called the (graph-) density g(G ") o

Multipartite TurΓ‘n problem for connected
Multipartite TurΓ‘n problem for connected graphs and hypergraphs
✍ Zsolt Tuza πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 561 KB

Tuza, Z., Multipartite Turan problem for connected graphs and hypergraphs, Discrete Mathematics 112 (1993) 199-206. Giving a partial solution to a problem of Bialostocki and Dierker, we determine the maximum number of edges in a k-chromatic graph G with color classes of given cardinalities n,, , n,,

Improved bounds and algorithms for hyper
Improved bounds and algorithms for hypergraph 2-coloring
✍ Jaikumar Radhakrishnan; Aravind Srinivasan πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 259 KB πŸ‘ 2 views

We show that for all large n, every n-uniform hypergraph with at most 0 7 n/ ln n Γ— 2 n edges can be 2-colored. This makes progress on a problem of ErdΕ‘s [Nordisk Mat. Tidskrift 11, 5-10 (1963)], improving the previous-best bound of n 1/3-o 1 Γ— 2 n due to Beck [Discrete Math. 24, 127-137 (1978)]. We