Majority choosability of countable graphs

DOI10.1016/J.EJC.2023.103829MaRDI QIDQ6181996zbMATH OpenOpenAlexFDO

Authors Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk

Publication date 23 January 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

majority coloringproper coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30)

Abstract: In any vertex coloring of a graph some edges have differently colored ends (emph{good} edges) and some are monochromatic (emph{bad} edges). In a proper coloring all edges are good. In a emph{majority coloring} it is enough that for every vertex $v$, the number of bad edges incident to $v$ does not exceed the number of good edges incident to $v$. A well known result of Lov'{a}sz cite{Lovasz} asserts that every finite graph has a majority $2$-coloring. A similar statement for countably infinite graphs is a challenging open problem, known as the emph{Unfriendly Partition Conjecture}. We consider a natural list variant of majority coloring. A graph is emph{majority $k$-choosable} if it has a majority coloring from any lists of size $k$ assigned arbitrarily to the vertices. We prove that every countable graph is majority $4$-choosable. We also consider a natural analog of majority coloring for directed graphs. We prove that every countable digraph is also majority $4$-choosable. We pose list and directed analogs of the Unfriendly Partition Conjecture, stating that every countable graph is majority $2$-choosable and every countable digraph is majority $3$-choosable.

Recommendations

• Majority choosability of digraphs
• Majority coloring of infinite digraphs
• Majority colorings of sparse digraphs
• Generalized Majority Colourings of Digraphs

Cites work

• Every rayless graph has an unfriendly partition
• scientific article; zbMATH DE number 4191687 (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
• Majority colorings of sparse digraphs
• On a theorem about vertex colorings of graphs
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• Unfriendly partitions for graphs not containing a subdivison of an infinite cycle
• Unfriendly partitions of a graph

Cited in

(5)

• Majority coloring of infinite digraphs
• Partitioning problems via random processes
• Mrs. Correct and majority colorings
• Countable graphs are majority 3-choosable
• All graphs are majority 3-choosable

This page was built for publication: Majority choosability of countable graphs

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