𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Some recent problems and results in graph theory

✍ Scribed by Paul Erdös

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
230 KB
Volume
164
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

I will mention two of my favourite problems in which recently important progress was made. The other questions I will mention are perhaps less well known.

  1. Faber, Lowisz and I conjectured more than 20 years ago that if Gi, 1 <<.i~n are n G n edge disjoint complete graphs of size n then Ui=l i has chromatic number n.

The conjecture turned out to be quite difficult and I offered many years ago 500 dollars for a proof or disproof. About three years ago Jeff Kahn proved that the chromatic number of Uin=lGi is ~<n(1 + o(1)). I gave him a consolation prize of 100 dollars, perhaps he will eventually prove that the chromatic number is n.

Perhaps one could ask: How large can the chromatic number of Ui=lGin be if we assume that Gi N Gj is triangle free? or that Gin Gj has at most one edge? 2. A family of sets Ai, 1 ~<i <~t is called a strong A-system if the sets Ai n A j, 1 ~< i < j ~ t are all identical. It is called a weak A-system if all the sets Ai n A j,

📜 SIMILAR VOLUMES

Some recent results in hamiltonian graph
Some recent results in hamiltonian graphs
✍ L. Lesniak-Foster 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 505 KB

## Abstract A variety of recent developments in hamiltonian theory are reviewed. In particular, several sufficient conditions for a graph to be hamiltonian, certain hamiltonian properties of line graphs, and various hamiltonian properties of powers of graphs are discussed. Furthermore, the concept

Some problems in topological graph theor
Some problems in topological graph theory
✍ Jonathan L. Gross; Frank Harary 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 504 KB

## Abstract A list of 31 problems presented here reflects some of the main trends in topological graph theory.

Problems and results in combinatorial an
Problems and results in combinatorial analysis and graph theory
✍ Paul Erd'́os 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 764 KB

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

Recent problems and results about kernel
Recent problems and results about kernels in directed graphs
✍ C. Berge; P. Duchet 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 355 KB

In Section 1, we survey the existence theorems for a kernel; in Section 2, we discuss a new conjecture which could constitute a bridge between the kernel problems and the perfect graph conjecture. In fact, we believe that a graph is 'quasi-perfect' if and only if it is perfect. ## Proposition 1.1.