February 28, 2020
Summary
Wei Meng (William & Mary): Linear connectivity for tournaments to be highly linked - AND - Yue Wang (William & Mary): Enhancing Erdos-Lovasz Tihany conjecture for line graphs of multigraphs
Full Description
Abstract: A digraph is k-linked if for any two disjoint sets of vertices x_1,..., x_k and y_1,...,y_k there are vertex disjoint paths P_1,...,P_k such that P_i is directed from x_i to y_i for i=1, ..., k. Pokrovskiy in 2015 proved that every strongly 452k-connected tournament is k-linked. In this paper, we significantly reduce this connectivity bound and show that any (24k-19)-connected tournament is k-linked. This is joint work with Martin Rolek, Yue Wang, and Gexin Yu.
Abstract: let s,t be integers. A graph G is (s,t)-splittable if the vertices of G can be partitioned into two sets S and T such that the chromatic number of subgraph induced by S (denoted by G[S]) is at least s and the chromatic number of subgraph induced by T (denoted by G[T]) is at least t. The well-known Erdos-Lovasz Tihany Conjecture from 1968 states that every graph G whose chromatic index equals s+t-1 and larger than its clique number is (s,t)-splittable. This conjecture is hard, and only known to be true for line graphs, quasi-lines, and graphs with independent number 2. In this paper, we prove an enhanced version of the conjecture for line graphs of multigraphs.
