Majority colourings of digraphs

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

doi:10.37236/6410

Majority colourings of digraphs

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

Mathematics

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

23 Scopus citations

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 (US)
Article number	#P2.25
Journal	Electronic Journal of Combinatorics
Volume	24
Issue number	2
DOIs	https://doi.org/10.37236/6410
State	Published - May 19 2017

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.37236/6410

Cite this

@article{33132f2a6cb34a13bd293935a72158ac,

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",

doi = "10.37236/6410",

language = "English (US)",

volume = "24",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

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 - https://www.scopus.com/pages/publications/85019963268

UR - https://www.scopus.com/pages/publications/85019963268#tab=citedBy

U2 - 10.37236/6410

DO - 10.37236/6410

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

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this