Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-23T23:35:29.523Z Has data issue: false hasContentIssue false

Generalized Majority Colourings of Digraphs

Published online by Cambridge University Press:  14 August 2017

ANTÓNIO GIRÃO
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: [email protected])
TEERADEJ KITTIPASSORN
Affiliation:
Departamento de Matemática, Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio), Rua Marquês de São Vicente 225, Gávea, Rio de Janeiro, RJ 22451-900, Brazil (e-mail: [email protected])
KAMIL POPIELARZ
Affiliation:
Department of Mathematics, University of Memphis, Memphis, TN 38152, USA (e-mail: [email protected])

Abstract

We almost completely solve a number of problems related to a concept called majority colouring recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised the problem of determining, for a natural number k, the smallest number m = m(k) such that every digraph can be coloured with m colours where each vertex has the same colour as at most a 1/k proportion of its out-neighbours. We show that m(k) ∈ {2k − 1,2k}. We also prove a result supporting the conjecture that m(2) = 3. Moreover, we prove similar results for a more general concept called majority choosability.

Type
Paper
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Alon, N. (2006) Splitting digraphs. Combin. Probab. Comput. 15 933937.Google Scholar
[2] Anholcer, M., Bosek, B. and Grytczuk, J. (2016) Majority choosability of digraphs. arXiv:1608.06912 Google Scholar
[3] Bourgain, J. and Tzafriri, L. (1989) Restricted invertibility of matrices and applications. In Analysis at Urbana, Vol. II (Urbana, IL, 1986–1987), Vol. 138 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 61107.Google Scholar
[4] GLPK: GNU Linear Programming Kit. https://www.gnu.org/software/glpk/ Google Scholar
[5] Knox, F. and Šámal, R. (2017) Linear bound for majority colourings of digraphs. arXiv:1701.05715 Google Scholar
[6] Kreutzer, S., Oum, S.-i., Seymour, P., van der Zypen, D. and Wood, D. R. (2017) Majority colourings of digraphs. Electron. J. Combin. 24 P2.25.Google Scholar