[KAIST Discrete Math Seminar] FYI: 7/15 (THU) 10:30AM *SNU* (Refael Hassin, Closed colorings: a conjecture and its implications)

[Sang-il Oum]

* Note: I'm forwarding a seminar announcement that may be interesting
to you. This is a seminar organized by Prof. Sung-Pil Hong, Department
of Industrial Engineering, Seoul National Univ.

DATE: July 15, Thursday

TIME: 10:30AM-11:45AM

PLACE: Room 309, Bldg. 39, College of Engineering,
       Seoul National University, Seoul

SPEAKER: Refael Hassin, Tel Aviv University
       http://www.math.tau.ac.il/~hassin/

TITLE: Closed colorings: a conjecture and its implications

We define closed edge colorings of directed graphs, and state a
conjecture about the maximum size of a tournament graph that can be
arc colored with m colors and contain no closed subgraphs. We show
that if this conjecture is correct then for any (undirected) graph
with positive edge lengths and a given subset V_0 of nodes, covering
all the shortest paths between pairs of nodes of V_0 requires at least
|V_0| ? 1 edges. We use the latter property to improve a result of Li,
McCormick, and Simchi-Levi (1992) about approximating the diameter or
the radius of an unweighted graph by adding to it a given number of
new edges.