Strong majority colorings of graphs

Rafał Kalinowski, Mateusz Kamyczura · 2026

Read Strong majority colorings of graphs by Rafał Kalinowski, Mateusz Kamyczura (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-23828.txt.

Introduction

Rafał Kalinowski and colleagues introduce strong majority colorings. In this scheme, no single color may claim more than half of any vertex neighbors, or more than half of any edge neighbors. They show the vertex version can demand arbitrarily many colors. Yet they prove a tight cap of twice the max degree plus one for graphs without dangling ends. For edges they prove a universal constant cap exists. They conjecture the constant is just four, verifying it across many graph families.

Catalog record

CREATORRafał Kalinowski, Mateusz Kamyczura
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE26448
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.23828

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Strong majority colorings of graphs Rafał Kalinowski, Mateusz Kamyczura Abstract Motivated by majority vertex-colorings of graphs and digraphs and majority edge-colorings of graphs, we introduce two concepts of strong majority colorings. A strong majority vertex-coloring of a graph G = ( V , E ) G=(V,E) is a mapping c : V → C c:V\rightarrow C such that for every vertex v ∈ V v\in V and every color α ∈ C \alpha\in C , at most half of the neighbors of v v have color α \alpha . The strong majority number of G G , denoted Maj ( G ) (G) , is the least number of colors in such a coloring. We show that Maj ( G ) (G) can be arbitrarily large and prove a tight upper bound Maj ( G ) ≤ 2 ​ Δ ​ ( G ) + 1 (G)\leq 2\Delta(G)+1 for every graph G G without pendant vertices. A strong majority edge-coloring of a graph G G is a mapping c : E → C c:E\rightarrow C such that for every edge e ∈ E e\in E and every color α ∈ C \alpha\in C , at most half of the edges adjacent to e e have color α \alpha . The strong majority index of G G , denoted Maj’ ( G ) (G) , is the least number of colors in such a coloring. It is shown that there is an upper constant bound for Maj’ ( G ) (G) of all admissible graphs G G . We conjecture that this constant is as small as 4 and confirm this conjecture for numerous graph classes. 1 Motivation We introduce two graph invariants related to sizes of color classes in the neighborhood of a vertex or an edge. To make this paper more readable, we also give names and notation to analogous invariants previously considered in the literature, which were an inspiration to our research. Let G be a simple undirected graph. We call a vertex-coloring of G majority if for every vertex v at most half its neighbors share the color of v . By {\mathrm{m}aj}(G) we denote the minimum number of colors among all majority vertex-colorings of the graph G . These colorings were first considered in 1966 by Lovász [ 10 ] , who proved the following classical result. Theorem 1 (Lovász [ 10 ] ) . For every finite graph G , {\mathrm{m}aj}(G)=2. Majority vertex-colorings were later investigated for infinite graphs. In this case, for a subset set S of an infinite set \Omega , the condition that the cardinality of S is at most half the elements of \Omega means that the complement of S is of the same cardinality as \Omega . Shelah and Milner [ 12 ] showed that {\mathrm{m}aj}(G)\leq 3 for every graph of arbitrary cardinality, and there exist uncountable graphs with {\mathrm{m}aj}(G)=3 . The renowned Unfriendly Partition Conjecture states that {\mathrm{m}aj}(G)=2 for every countable graph G . This conjecture is often viewed as one of the most intriguing and difficult open problems in infinite graph theory. It has been confirmed only for some classes of graphs, in particular for – graphs with finitely many vertices of infinite degree (Aharoni, Milner, and Prikry [ 1 ] ), – graphs with finitely many vertices of finite degree (Aharoni, Milner, and Prikry [ 1 ] ), – rayless graphs (Bruhn, Diestel, Georgakopoulos, and Sprüssel [ 5 ] ), – graphs without a subdivision of an infinite clique (Berger [ 3 ] ), – line graphs (Kalinowski, Pilśniak, and Stawiski [ 8 ] ). In 2017, Kreutzer, Oum, Seymour, van der Zyphen, and Woods [ 9 ] introduced the following analogous notion for digraphs. A vertex-coloring of a digraph D is majority if for every vertex v at most half its out-neighbors share the color of v . Let us denote the minimum number of colors in such a coloring by \overrightarrow{{\mathrm{m}aj}}(D) . In [ 9 ] it was shown that \overrightarrow{{\mathrm{m}aj}}(D)\leq 4 , and it was conjectured that \overrightarrow{{\mathrm{m}aj}}(D)\leq 3 for every finite digraph D . This conjecture is still open but confirmed in some cases (cf. [ 2 ] and references therein). In 2023, Bock, Kalinowski, Pardey, Pilśniak, and Woźniak [ 4 ] defined majority edge-colorings of graphs. These are edge-colorings such that for every vertex v and every color \alpha , at most half of the edges incident with v have the color \alpha . Clearly, a graph having a vertex of degree 1 does not admit such a coloring. Let us denote the minimum number of colors in a majority edge-coloring of a graph G by {\mathrm{m}aj^{\prime}\,}(G) . The following upper bound for {\mathrm{m}aj^{\prime}\,}(G) was established in [ 4 ] . Theorem 2 ( [ 4 ] ) . Every finite graph G with minimum degree \delta(G)\geq 2 satisfies {\mathrm{m}aj^{\prime}\,}(G)\leq 4. Moreover, if \delta(G)\geq 4 , then {\mathrm{m}aj^{\prime}\,}(G)\leq 3. The first part of the above theorem was extended by Kalinowski, Pilśniak, and Stawiski in [ 8 ] to infinite graphs of arbitrary cardinality, also for the list setting. Moreover, as a consequence of their investigations of majority edge-colorings, they proved the following result for majority vertex-colorings. Theorem 3 ( [ 8 ] ) . If G is an infinite line graph of arbitrary cardinality, then {\mathrm{m}aj}(G)=2. Thus, using the concept of majority edge-colorings, they confirmed the Unfriendly Partition Conjecture for line graphs. Remark 4 . Suppose that for an edge-coloring of a graph G=(V,E) we require that, for every edge e\in E , at most half of the edges adjacent to e have the color of e (analogously to a majority vertex-coloring). Then, this coloring is equivalent to majority vertex-colorings of the line graph of G . Consequently, due to Theorem 1 and Theorem 3 , two colors suffice for such an edge-coloring of arbitrary cardinality. 2 Strong majority vertex-colorings Throughout, graph colorings need not be proper, and graphs are finite and undirected, unless otherwise stated. Let c be a vertex-coloring of a graph G . If for every vertex v and every color \alpha , at most half at most half of the neighbors of v have color \alpha , then c is a strong majority vertex-coloring of G . The minimum number of colors in such a coloring is the strong majority number of G , denoted by {\mathrm{M}aj}(G) . Clearly, {\mathrm{M}aj}(G) is defined only for graphs G without pendant vertices, that is, for graphs G with \delta(G)\geq 2 . Let us start with two easy examples. Observation 5 . For a cycle C_{n} , we have {\mathrm{M}aj}(C_{n})=2 if n\equiv 0\mod{4} , and {\mathrm{M}aj}(C_{n})=3 otherwise. Proof. In a strong majority vertex-coloring of C_{n} , two vertices of distance 2 necessarily have two distinct colors. Color subsequent vertices with colors 1,1,2,2,\ldots . This yields a strong majority vertex-coloring when n\equiv 0\mod{4} . Otherwise, a third color is needed. If n\equiv 1\mod{4} , then we put 3 at the end of the above sequence of colors. If n\equiv 2\mod 4 , we end with 3,3 . For n\equiv 3\mod 4 , we put 1,3,3 on the last three vertices. ∎ Observation 6 . For a complete graph K_{n} with n\geq 3 ,

Read the complete text