Problems and results in combinatorial analysis and graph theory

✍ Scribed by Paul Erd'́os

• Publisher: Elsevier Science
• Year: 1988
• Tongue: English
• Weight: 764 KB
• Volume: 72
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(88)90196-3

✦ Synopsis

I wrote many papers with this and similar titles. In my lecture I stated several of my old solved and unsolved problems some of which have already been published elsewhere. To avoid overlap as much as possible, I state here only relatively new problems.

First I state two recent problems of Nesetril and myself.

1. Let G be a graph each vertex of which has degree not exceeding n. It is true that if our G has more than 5n2/4 edges then G contains two strongly independent edges? (i.e. two edges, which are vertex disjoint and for which the subgraph of G induced by the vertices of these two edges contains only these two edges).

Very recently Fan Chung and Trotter and independently and simultaneously GyBrftis and Tuza proved this conjecture. The proofs are quite complicated. It is easy to see that the result is best possible.

We also formulated the following much more difficult and interesting Vizing type conjecture: Let G be a graph each vertex of which has degree not exceeding n. Is it then true that G is the union of at most 5n2/4 sets of strongly independent edges? If this conjecture fails one can try to determine the smallest f(n) so that every G each vertex of which has degree <n is the union of f(n) sets of strongly