Preskoči na glavno vsebino

Bojan Mohar: On a problem of Erdos and Neumann-Lara

Datum objave: 12. 5. 2015
Seminar za teorijo grafov in algoritme
Četrtek 14. maj 2015 ob 12:15 v PS na Jadranski 19.
Abstract. The dichromatic number of a graph G is the maximum integer k such that there exists an orientation of the edges of G such that for every partition of the vertices into fewer than k parts, at least one of the parts must contain a directed cycle under this orientation. In 1979, Erdos and Neumann-Lara conjectured that if the dichromatic number of a graph is bounded, so is its chromatic number. We make the first significant progress on this conjecture by proving a fractional version of the conjecture.
This is a joint work with Hehui Wu (University of Mississippi).