BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: A majority coloring of a directed graph is a vertex-coloring i
 n which every vertex has the same color as at most half of its out-neighbor
 s. Kreutzer\, Oum\, Seymour\, van der Zypen and Wood proved that every digr
 aph has a majority 4-coloring and conjectured that every digraph admits a m
 ajority 3-coloring.  We verify this conjecture for digraphs with chromatic 
 number at most 6 or dichromatic number at most 3. We obtain analogous resul
 ts for list coloring: We show that every digraph with list chromatic number
  at most 6 or list dichromatic number at most 3 is majority 3-choosable. We
  deduce that digraphs with maximum out-degree at most 4 or maximum degree a
 t most 7 are majority 3-choosable.  On the way to these results we investig
 ate digraphs admitting a majority 2-coloring. We show that every digraph wi
 thout odd directed cycles is majority 2-choosable. We answer an open questi
 on posed by Kreutzer et al. negatively\, by showing that deciding whether a
  given digraph is majority 2-colorable is NP-complete.  Finally we deal wit
 h a fractional relaxation of majority coloring proposed by Kreutzer et al. 
 and show that every digraph has a fractional majority 3.9602-coloring. We s
 how that every digraph D with sufficiently large minimum out-degree has a f
 ractional majority-(2+ε)-coloring.    Joint work with Michael Anastos\, And
 er Lamaison and Tibor Szabó. 
DTSTAMP:20191106T131200
DTSTART:20191111T160000
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9 
 \n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Raphael Steiner (Technische Universität Berlin): Majority Colorings
  of Sparse Digraphs
UID:95692405@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20191111-C-Steiner.html
END:VEVENT
END:VCALENDAR