Majority colourings of digraphs

MaRDI QIDQ2628255zbMATH OpenFDO

Authors Stephan Kreutzer, Sang-Il Oum, Dominic van der Zypen, David R. Wood, Paul Seymour

Publication date 13 June 2017

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

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

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

digraphsgraph colouringgraph theorymajority colouring

Mathematics Subject Classification ID

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

Abstract: We prove that every digraph has a vertex 4-colouring such that for each vertex $v$, at most half the out-neighbours of $v$ receive the same colour as $v$. We then obtain several results related to the conjecture obtained by replacing 4 by 3.

Review text

Summary: We prove that every digraph has a vertex 4-colouring such that for each vertex \(v\), at most half the out-neighbours of \(v\) receive the same colour as \(v\). We then obtain several results related to the conjecture obtained by replacing 4 by 3.

Recommendations

• Generalized Majority Colourings of Digraphs
• Majority colorings of sparse digraphs
• Linear bound for majority colourings of digraphs
• Out-colourings of digraphs
• A note on total colourings of digraphs
• Majority edge-colorings of graphs
• Majority choosability of digraphs
• Set colorings of digraphs
• The diachromatic number of digraphs
• Colouring non-even digraphs

Cites work

• Bounded degree acyclic decompositions of digraphs.
• Disjoint directed cycles
• Generalized Majority Colourings of Digraphs
• Graph colouring and the probabilistic method
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• Linear bound for majority colourings of digraphs
• Majority choosability of digraphs
• ON THE TWO-COLOURING OF HYPERGRAPHS
• Splitting digraphs

Cited in

(23)

• Linear bound for majority colourings of digraphs
• Out-degree reducing partitions of digraphs
• Majority colorings of sparse digraphs
• From the 1-2-3 conjecture to the Riemann hypothesis
• Majority choosability of digraphs
• Combinatorics. Abstracts from the workshop held January 5--11, 2020
• Majority edge-colorings of graphs
• Coloring the vertices of a graph with majority restrictions on colors
• Generalized Majority Colourings of Digraphs
• Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties
• Majority choosability of 1-planar digraph
• 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
• Introduction to majority additive coloring
• Majority dominator colorings of graphs
• Mrs. Correct and majority colorings
• Countable graphs are majority 3-choosable
• Some new results on majority coloring of digraphs
• Unfriendly partition conjecture holds for line graphs
• All graphs are majority 3-choosable

This page was built for publication: Majority colourings of digraphs

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