[KAIST Discrete Math Seminar] Reminder: TODAY (TUE) 4PM (Ken-ichi Kawarabayashi, National Institute of Informatics)

[Sang-il Oum]

***** KAIST Discrete Math Seminar *****

DATE: Nov 24, Tuesday ***UNUSUAL TIME***

TIME: 4PM-5PM

PLACE: E6-1, ROOM 1409

SPEAKER: Ken-ichi Kawarabayashi, National Institute of Informatics, Tokyo

TITLE: Graphs without subdivisions

http://mathsci.kaist.ac.kr/~sangil/seminar/entry/20091124/

Hajos' conjecture is false, and it seems that graphs without a
subdivision of a big complete graph do not behave as well as
those without a minor of a big complete graph.

In fact, the graph minor theorem (a proof of Wagner's
conjecture) is not true if we replace the minor relation by the
subdivision relation. I.e, For every infinite sequence
$G_1,G_2, \dots$ of graphs, there exist distinct integers $i <
j$ such that $G_i$ is a minor of $G_j$, but if we replace
''minor" by ''subdivision", this is no longer true.

This is partially because we do not really know what the graphs
without a subdivision of a big complete graph look like.

In this talk, we shall discuss this issue. In particular,
assuming some moderate connectivity condition, we can say
something, which we will present in this talk.

Topics also include coloring graphs without a subdivision of a
large complete graph, and some algorithmic aspects. Some of the
results are joint work with Theo Muller.