Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T04:01:39.761Z Has data issue: false hasContentIssue false
  • English
  • Français

Generalized Majority Colourings of Digraphs

Part of: Graph theory

Published online by Cambridge University Press:  14 August 2017

ANTÓNIO GIRÃO ,
TEERADEJ KITTIPASSORN  and
KAMIL POPIELARZ
ANTÓNIO GIRÃO
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: A.Girao@dpmms.cam.ac.uk)
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: ping41@mat.puc-rio.br)
KAMIL POPIELARZ
Affiliation:
Department of Mathematics, University of Memphis, Memphis, TN 38152, USA (e-mail: kamil.popielarz@gmail.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

MSC classification

Primary: 05C15: Coloring of graphs and hypergraphs
Secondary: 05C20: Directed graphs (digraphs), tournaments

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 6 , November 2017 , pp. 850 - 855
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Alon, N. (2006) Splitting digraphs. Combin. Probab. Comput. 15 933–937.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. 61–107.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