Generalized Majority Colourings of Digraphs

DOI10.1017/S096354831700044XMaRDI QIDQ5373832zbMATH OpenOpenAlexFDO

Authors António Girão, Teeradej Kittipassorn, Kamil Popielarz

Publication date 27 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.03780

Mathematics Subject Classification ID

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

Abstract: The purpose of this note is to draw attention to problems related to a concept called majority colouring recently studied by Kreutzer, Oum, Seymour, van der Zypen and Wood. They raised a 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 $1/k$ proportion of its out-neighbours. We show that $m(k)in2k-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.

Recommendations

• Majority colourings of digraphs
• Majority colorings of sparse digraphs
• Linear bound for majority colourings of digraphs
• Majority edge-colorings of graphs
• scientific article; zbMATH DE number 3912409
• On generalized graph colorings
• scientific article; zbMATH DE number 1052826
• Generalized total colorings of graphs
• Generalised colouring sums of graphs
• scientific article; zbMATH DE number 3918396

Cites work

• scientific article; zbMATH DE number 4144774 (Why is no real title available?)
• Majority choosability of digraphs
• Majority colourings of digraphs
• Splitting digraphs

Cited in

(19)

• Linear bound for majority colourings of digraphs
• Majority coloring game
• Majority colorings of sparse digraphs
• Majority choosability of digraphs
• Majority colourings of digraphs
• Majority edge-colorings of graphs
• Majority digraphs
• Coloring the vertices of a graph with majority restrictions on colors
• Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties
• Majority choosability of 1-planar digraph
• Majority choosability of countable graphs
• Majority coloring of infinite digraphs
• Partitioning problems via random processes
• On generalised majority edge-colourings of graphs
• A note on digraph splitting
• On list extensions of the majority edge colourings
• Mrs. Correct and majority colorings
• Countable graphs are majority 3-choosable
• Some new results on majority coloring of digraphs

This page was built for publication: Generalized Majority Colourings of Digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5373832)