Title    name Lastest   |   Most hits   년도선택 최근 50건201120102009200820072006200520042003200220012000     KAIST Graph Theory Day 2011 Colouring Tournaments Paul Seymour (Princeton University) 2011-05-10   A tournament is a digraph obtained from a complete graph by directing its edges, and colouring a tournament means partitioning its vertex set into acyclic subsets (acyclic means the subdigraph induced on the subset has no directed cycles). This concept is quite like that for graph-colouring, but different. For instance, there are some tournaments H such that every tournament not containing H as a subdigraph has bounded chromatic number. We call them heroes; for example, all tournaments with at most four vertices are heroes. It turns out to be a fun problem to figure out exactly which tournaments are heroes. We have recently managed to do this, in joint work with Berger, Choromanski, Chudnovsky, Fox, Loebl, Scott and Thomassé, and this talk is about the solution.   KAIST Graph Theory Day 2011 On the chromatic number of digraphs  Bojan Mohar (Simon Fraser University) 2011-05-10   Several reasons will be presented why the natural extension of the notion of undirected graph colorings is to partition the vertex set of a digraph into acyclic sets. Additionally, some recent results in this area, the proofs of which use probabilistic techniques, will be outlined.   KAIST Graph Theory Day 2011 A separator theorem in minor-closed class of graphs Kenichi-Kawarabayashi (National Institute of Informatics) 2011-05-10     KAIST Graph Theory Day 2011 Coloring some perfect graphs Maria Chudnovsky (Columbia University) 2011-05-10   A graph G is called perfect if for every induced subgraph H of G, the chromatic number and the clique number of H are equal. After the recent proof of the Strong Perfect Graph Theorem, and the discovery of a polynomial-time recognition algorithm, the central remaining open question about perfect graphs is finding a combinatorial polynomial-time coloring algorithm. (There is a polynomial-time algorithm known, using the ellipsoid method). Recently, we were able to find such an algorithm for a certain class of perfect graphs, that includes all perfect graphs admitting no balanced skew-partition. The algorithm is based on finding special “extremal” decompositions in such graphs; we also use the idea of “trigraphs”. This is joint work with Nicolas Trotignon, Theophile Trunck and Kristina Vuskovic.

Information Center for Mathematical Sciences KAIST 335 Gwahangno (373-1 Guseong-dong), Yuseong-gu, Daejeon 305-701, Republic of Korea TEL +82-42-869-8195~6, FAX +82-42-869-5722, e-mail : mathnet@mathnet.or.kr Copyright (c) 2009 by ICMS. All Rights Reserved