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