[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

157.0. "A graph containment conjecture" by HARE::STAN () Mon Sep 24 1984 16:09

20 years ago, Wagner made the following conjecture:

Any list of graphs with no graph contained in any other must be finite.

The conjecture is still open.

			Reference
			---------

Gina Kolata, Graph Theory Result Proved, Science 224 (4 May 1984) 480-481.

T.R Title User Personal
Name Date Lines

157.1 HARE::STAN Mon Sep 24 1984 16:17 10

T.R	Title	User	Personal Name	Date	Lines
157.1		HARE::STAN		`Mon Sep 24 1984 16:17`	10
	The term "contained in" was not defined, but I think they must mean more than set containment. I think they mean the same thing as when you say any nonplanar graph "contains" a copy of K or K . 5 3,3 For otherwise, the infinite set of cycles, of lengths 3,4,5,6, etc. is such that none contains another. However, in the broader sense, the cycle of length 4 "contains" a cycle of length 3 by coalescing two vertices.

The term "contained in" was not defined, but I think they must
mean more than set containment.  I think they mean the same thing
as when you say any nonplanar graph "contains" a copy of
K  or K   .
 5     3,3

For otherwise, the infinite set of cycles, of lengths 3,4,5,6, etc.
is such that none contains another.  However, in the broader sense,
the cycle of length 4 "contains" a cycle of length 3 by coalescing
two vertices.