𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Turán type problem for interval graphs

✍ Scribed by Harvey Abbott; Meir Katchalski

Publisher
Elsevier Science
Year
1979
Tongue
English
Weight
313 KB
Volume
25
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the following analogue of a problem of Turin for interval graphs: Let c = c(n, rn) be the largest integer such that any interval graph with n vertices and at least m edges contains a complete subgraph on c vertices. We determine the value of c(n, m) explicitly.

📜 SIMILAR VOLUMES

Turán problems for integer-weighted grap
Turán problems for integer-weighted graphs
✍ Zoltán Füredi; André Kündgen 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB

## Abstract A multigraph is (__k__,__r__)‐dense if every __k__‐set spans at most __r__ edges. What is the maximum number of edges ex~ℕ~(__n__,__k__,__r__) in a (__k__,__r__)‐dense multigraph on __n__ vertices? We determine the maximum possible weight of such graphs for almost all __k__ and __r__ (e

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,,

A Ramsey-type problem and the Turán numb
A Ramsey-type problem and the Turán numbers
✍ N. Alon; P. Erdős; D. S. Gunderson; M. Molloy 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB

## Abstract For each __n__ and __k__, we examine bounds on the largest number __m__ so that for any __k__‐coloring of the edges of __K~n~__ there exists a copy of __K~m~__ whose edges receive at most __k−__1 colors. We show that for $k \ge \sqrt{n}\;+\,\Omega(n^{1/3})$, the largest value of __m__ i

On Ramsey-Turán type problems in tournam
On Ramsey-Turán type problems in tournaments
✍ A Bialostocki; N Sauer 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 467 KB

Let Tbe a tournament and let c :e(T)--> {1 ..... r} be an r-colouring of the edges of T. The associated reachability graph, denoted by R(T, c) is a directed graph whose vertices are the vertices of T, and a vertex v of R(T, c) dominates a vertex u of R(T, c) iff there is a monochromatic directed pat

Another extremal problem for Turan graph
Another extremal problem for Turan graphs
✍ Bruce Hedman 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 207 KB

We consider only finite, undirected graphs without loops or multiple edges. A clique of a graph G is a maximal complete subgraph of G. The clique number w(G) is the number of vertices in the largest clique of G. This note addresses the foflowing question: Which graphs G on n vertices with w(G) = r h