Linear bound for majority colourings of digraphs

MaRDI QIDQ1671650zbMATH OpenFDO

Authors Fiachra Knox, Robert Šámal

Publication date 7 September 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.05715, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p29

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

colouringsdigraphs

Mathematics Subject Classification ID

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

Abstract: Given $etain[0,1]$, a colouring $C$ of $V(G)$ is an $eta$-majority colouring if at most $eta{d}^{+}(v)$ out-neighbours of $v$ have colour $C(v)$, for any $vinV(G)$. We show that every digraph $G$ equipped with an assignment of lists $L$, each of size at least $k$, has a $2/k$-majority $L$-colouring. For even $k$ this is best possible, while for odd $k$ the constant $2/k$ cannot be replaced by any number less than $2/(k+1)$. This generalizes a result of Anholcer, Bosek and Grytczuk, who proved the cases $k=3$ and $k=4$ and gave a weaker result for general $k$.

Recommendations

• Majority choosability of digraphs
• Generalized Majority Colourings of Digraphs
• Majority colourings of digraphs
• Majority colorings of sparse digraphs
• Majority edge-colorings of graphs

Cites work

• Generalized Majority Colourings of Digraphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• Majority choosability of digraphs
• Majority colourings of digraphs

Cited in

(18)

• Majority coloring game
• Majority colorings of sparse digraphs
• Majority choosability of digraphs
• Majority colourings of digraphs
• Majority edge-colorings of graphs
• Majority digraphs
• scientific article; zbMATH DE number 29786 (Why is no real title available?)
• Generalized Majority Colourings of Digraphs
• Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties
• Majority choosability of 1-planar digraph
• Majority choosability of countable graphs
• 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: Linear bound for majority colourings of digraphs

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