Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-14T11:16:12.443Z 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: [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])
Get access Rights & Permissions [Opens in a new window]

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.

MSC classification

Primary: 05C15: Coloring of graphs and hypergraphs
Secondary: 05C20: Directed graphs (digraphs), tournaments
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 6 , November 2017 , pp. 850 - 855
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 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