[Discrete-math-seminar] Talk tomorrow at 11am

[Michael Pelsmajer]

Hi.  Tomorrow I'll give the first talk of the semester, at 11am.  We
don't have a room reserved yet, so please let's meet outside my office,
E1 206, and I'll have figured something out by then.

Title:
An open problem in graph theory for students

Abstract:
A "feedback vertex set" in a graph G is a subset of vertices S such that
G-S is acyclic a forest.  A somewhat famous conjecture: "Any n-vertex
planar graph has a feedback vertex set of size at most n/2."  (If true,
this would be sharp).  There are other similar statements, some open,
some well-known, where "planar graphs" are replaced by some other class
of graphs G1, and where the requirement that "G-S is a forest" is
replaced by G-S having to be in some class of graphs G2.

Glenn Chappell and I have a not-at-all famous conjecture of this sort:
"Any n-vertex k-tree has a set S of size at most kn/(k+2) such that G-S
has maximum degree 1."  On Wednesday I will introduce k-trees and other
definitions, and discuss methods that worked for related problems, but
don't suffice for this problem.


Thanks.  Hope to see you then.

-------------------------------------------------------------
Michael J. Pelsmajer                    www.iit.edu/~pelsmaje
Applied Mathematics, E1 Room 206          pelsmajer at iit.edu
Illinois Institute of Technology            (312)567-5344
Chicago, IL 60616