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$.

Review text

Summary: Given \(\eta \in [0, 1]\), a colouring \(C\) of \(V(G)\) is an \textit{\(\eta\)-majority colouring} if at most \(\eta d^+(v)\) out-neighbours of \(v\) have colour \(C(v)\), for any \(v \in V(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 \textit{M. Anholcer} et al. [ibid. 24, No. 3, Research Paper P3.57, 5 p. (2017; Zbl 1375.05079)], who proved the cases \(k=3\) and \(k=4\) and claim 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)