User Tools

Site Tools


Ringi Kim (Waterloo)

Coloring Digraphs Containing No Cycles With Two Blocks

Abstract for the Combinatorics Seminar 2017 April 25

A cycle with two blocks c(k,l) is an oriented cycle consisting of two internally disjoint directed paths of lengths at least k and l, respectively, from a vertex to another one. In 2007, Addario-Berry, Havet, and Thomassé asked if every strongly connected digraph D containing no c(k,l) has chromatic number at most k+l−1. In this talk, I show that such a digraph D has chromatic number at most O((k+l)2), improving the previous upper bound O((k+l)4) of Cohen, Havet, Lochet, and Nisse.

This is joint work with Seog-Jin Kim, Jie Ma, and Boram Park.

seminars/comb/abstract.201704kim.txt · Last modified: 2020/01/29 14:03 (external edit)