Majority colourings of digraphs

Stephan Kreutzer; Sang Il Oum; Paul Seymour; Dominic van der Zypen; David R. Wood

Majority colourings of digraphs

Stephan Kreutzer, Sang Il Oum, Paul Seymour, Dominic van der Zypen, David R. Wood

School of Mathematics

Research output: Contribution to journal › Article › Research › peer-review

19 Citations (Scopus)

Abstract

We prove that every digraph has a vertex 4-colouring such that for each vertex v, at most half the out-neighbours of v receive the same colour as v. We then obtain several results related to the conjecture obtained by replacing 4 by 3.

Original language	English
Article number	#P2.25
Number of pages	9
Journal	Electronic Journal of Combinatorics
Volume	24
Issue number	2
Publication status	Published - 19 May 2017

Access to Document

39787910-oaFinal published version, 287 KB

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p25/pdf

Cite this

@article{f47b2695ee564f6aa6b822036baaac95,

title = "Majority colourings of digraphs",

abstract = "We prove that every digraph has a vertex 4-colouring such that for each vertex v, at most half the out-neighbours of v receive the same colour as v. We then obtain several results related to the conjecture obtained by replacing 4 by 3.",

author = "Stephan Kreutzer and Oum, {Sang Il} and Paul Seymour and {van der Zypen}, Dominic and Wood, {David R.}",

year = "2017",

month = may,

day = "19",

language = "English",

volume = "24",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Clemson University Digital Press",

number = "2",

}

TY - JOUR

T1 - Majority colourings of digraphs

AU - Kreutzer, Stephan

AU - Oum, Sang Il

AU - Seymour, Paul

AU - van der Zypen, Dominic

AU - Wood, David R.

PY - 2017/5/19

Y1 - 2017/5/19

N2 - We prove that every digraph has a vertex 4-colouring such that for each vertex v, at most half the out-neighbours of v receive the same colour as v. We then obtain several results related to the conjecture obtained by replacing 4 by 3.

AB - We prove that every digraph has a vertex 4-colouring such that for each vertex v, at most half the out-neighbours of v receive the same colour as v. We then obtain several results related to the conjecture obtained by replacing 4 by 3.

UR - http://www.scopus.com/inward/record.url?scp=85019963268&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85019963268

SN - 1077-8926

VL - 24

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 2

M1 - #P2.25

ER -

Majority colourings of digraphs

Abstract

Access to Document

Other files and links

Cite this