pith. sign in

arxiv: 2605.23828 · v1 · pith:JJS6NBGNnew · submitted 2026-05-22 · 🧮 math.CO

Strong majority colorings of graphs

Rafa{\l} Kalinowski , Mateusz Kamyczura , Monika Pil\'sniak , Mariusz Wo\'zniak This is my paper

Pith reviewed 2026-05-25 03:45 UTC · model grok-4.3

classification 🧮 math.CO
keywords strong majority coloringmajority vertex-coloringmajority edge-coloringgraph coloringmaximum degreependant verticesedge coloring
0
0 comments X

The pith

The strong majority number Maj(G) is at most 2Δ(G)+1 for graphs without pendant vertices, with the bound tight, while Maj(G) itself can be arbitrarily large.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper defines strong majority vertex-colorings as vertex color assignments where, for every vertex and every color, at most half the neighbors receive that color. It proves that the fewest colors needed for such a coloring, Maj(G), can be made arbitrarily large yet satisfies Maj(G) ≤ 2Δ(G)+1 for every graph without pendant vertices. The paper likewise defines strong majority edge-colorings under an analogous local condition on adjacent edges and shows that the fewest colors needed, Maj'(G), admits some constant upper bound for all admissible graphs while conjecturing that the constant equals 4.

Core claim

A strong majority vertex-coloring of G is a mapping c from vertices to colors such that for every vertex v and color α at most half the neighbors of v receive color α. The authors prove that Maj(G), the smallest size of the color set admitting such a mapping, can be arbitrarily large, yet Maj(G) ≤ 2Δ(G)+1 holds for every graph G without pendant vertices and the bound is attained for some graphs. A strong majority edge-coloring is defined by the same half-neighbor restriction applied to edges incident to a given edge, and Maj'(G) is shown to be bounded above by an absolute constant for admissible graphs, with the conjecture that 4 suffices for all such graphs.

What carries the argument

The strong majority condition: for every vertex (or edge) and every color, the color appears on at most half the adjacent vertices (or edges). This local density restriction determines both the vertex parameter Maj(G) and the edge parameter Maj'(G).

If this is right

  • Maj(G) exceeds any fixed number for suitable choices of G.
  • The inequality Maj(G) ≤ 2Δ(G)+1 is tight for graphs without pendant vertices.
  • Maj'(G) is bounded above by some constant independent of the graph for all admissible G.
  • The conjecture Maj'(G) ≤ 4 holds for the numerous graph classes verified in the paper.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The contrast between a linear-in-Δ bound for vertices and a constant bound for edges suggests the two parameters may scale differently with graph size.
  • Testing the edge-coloring conjecture on further families such as bipartite graphs of high degree or random regular graphs would provide additional confirmation or a counterexample.
  • If the vertex bound extends to graphs containing pendant vertices, the additive term or the treatment of degree-1 vertices would require separate analysis.

Load-bearing premise

The upper bound Maj(G) ≤ 2Δ(G)+1 is proved only for graphs that have no pendant vertices.

What would settle it

A graph with minimum degree at least two for which every strong majority vertex-coloring requires more than 2Δ(G)+1 colors would falsify the bound.

Figures

Figures reproduced from arXiv: 2605.23828 by Mariusz Wo\'zniak, Mateusz Kamyczura, Monika Pil\'sniak, Rafa{\l} Kalinowski.

Figure 1
Figure 1. Figure 1: Edge v1v2 of K4 replaced by a diamond 4 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: STS(7) represented by the Fano plane (where each line xi is a triple of points) and the block-point incidence graph G of STS(7) 3 Strong majority edge-colorings In this section, we introduce an analog of the strong majority vertex-colorings for edge-colorings. Given an edge-coloring c of a graph G = (V, E), we say that an edge e ∈ E is majority colored if there is no color α such that e is adjacent to more… view at source ↗
read the original 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)$ is a mapping $c:V\rightarrow C$ such that for every vertex $v\in V$ and every color $\alpha\in C$, at most half of the neighbors of $v$ have color $\alpha$. The strong majority number of $G$, denoted Maj$(G)$, is the least number of colors in such a coloring. We show that Maj$(G)$ can be arbitrarily large and prove a tight upper bound Maj$(G)\le 2\Delta(G)+1$ for every graph $G$ without pendant vertices. A strong majority edge-coloring of a graph $G$ is a mapping $c:E\rightarrow C$ such that for every edge $e\in E$ and every color $\alpha\in C$, at most half of the edges adjacent to $e$ have color $\alpha$. The strong majority index of $G$, denoted Maj'$(G)$, is the least number of colors in such a coloring. It is shown that there is an upper constant bound for Maj'$(G)$ of all admissible graphs $G$. We conjecture that this constant is as small as 4 and confirm this conjecture for numerous graph classes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript defines strong majority vertex-colorings of a graph G, requiring that for every vertex v and color α at most half the neighbors of v have color α, with Maj(G) the minimum number of colors needed. It shows Maj(G) can be arbitrarily large and proves the tight bound Maj(G) ≤ 2Δ(G)+1 for graphs without pendant vertices. It defines strong majority edge-colorings analogously for edges, with Maj'(G) the minimum colors, proves a constant upper bound exists for admissible graphs, conjectures the bound is 4, and verifies the conjecture on numerous graph classes.

Significance. The work extends majority coloring concepts with new 'strong' variants. The degree-linear bound for vertices and the conjectured constant bound for edges, if established, would provide useful parameters in graph theory with potential applications in combinatorial optimization.

minor comments (2)
  1. [Abstract] The claim that the upper bound is 'tight' requires explicit examples or a reference to a theorem showing equality cases to support the descriptor.
  2. Define 'admissible graphs' explicitly in the introduction or preliminaries section, as it is used without prior definition in the abstract.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the review and the recommendation of minor revision. The report does not list any specific major comments.

Circularity Check

0 steps flagged

No significant circularity; results are direct combinatorial proofs from definitions

full rationale

The paper defines strong majority vertex-colorings and edge-colorings from first principles, then proves existence of arbitrarily large Maj(G), the bound Maj(G) ≤ 2Δ(G)+1 (conditioned on no pendant vertices), and an unspecified constant upper bound on Maj'(G) via combinatorial arguments. No equations reduce a claimed result to a fitted parameter, self-citation chain, or renamed input by construction. The conjecture on the constant 4 is explicitly separated from the proven statements. The derivation chain is self-contained against external benchmarks and does not invoke any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the newly introduced definitions of strong majority colorings plus standard combinatorial assumptions about finite undirected graphs and proper mappings; no free parameters or invented entities are introduced.

axioms (1)
  • standard math Standard axioms of graph theory including finite undirected simple graphs and color mappings from vertices or edges to a finite set
    The paper invokes conventional graph-theoretic background without stating new axioms.

pith-pipeline@v0.9.0 · 5785 in / 1246 out tokens · 53216 ms · 2026-05-25T03:45:00.217344+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    Aharoni, E

    R. Aharoni, E. Milner, and K. Prikry. Unfriendly partitions of a graph. J. Combin. Theory Ser. B, 50(1):1–10, 1990

    work page 1990

  2. [2]

    Anholcer, B

    M. Anholcer, B. Bosek, J. Grytczuk, G. Gutowski, J. Przybyło, and M. Zając. Mrs. correct and majority colorings.Discrete Math., 348(11):114577, 2025. 12

    work page 2025

  3. [3]

    E. Berger. Unfriendly partitions for graphs not containing a subdivision of an infinite clique.Combinatorica, 37(2):157–166, 2017

    work page 2017

  4. [4]

    F. Bock, R. Kalinowski, J. Pardey, M. Pilśniak, D. Rautenbach, and M. Woźniak. Majority Edge-Colorings of Graphs.Electron. J. Combin., 30:#P1.42, 2023

    work page 2023

  5. [5]

    Bruhn, R

    H. Bruhn, R. Diestel, A. Georgakopoulos, and P. Sprüssel. Every rayless graph has an unfriendly partition.Combinatorica, 30(5):521–532, 2010

    work page 2010

  6. [6]

    de Werra

    D. de Werra. A few remarks about chromatic scheduling.Combinatorial Programming: Methods and Applications” (B. Roy, Ed.), pages 337–342, 1975

    work page 1975

  7. [7]

    Hilton, D

    A. Hilton, D. Stirling, and T. Slivnik. A vertex-splitting lemma, de werra’s theorem, and improper list colourings.J. Combin. Theory, Ser. B, 72(1):91–103, 1998

    work page 1998

  8. [8]

    Kalinowski, M

    R. Kalinowski, M. Pilśniak, and M. Stawiski. Unfriendly Partition Con- jecture holds for line graphs.Combinatorica, 45(1):art. no. 3, 2025

    work page 2025

  9. [9]

    Kreutzer, S

    S. Kreutzer, S. Oum, P. Seymour, D. van der Zyphen, and D. R. Wood. Majority colourings of digraphs.Electron. J. Combin., 24:#P2.25, 2017

    work page 2017

  10. [10]

    L. Lovász. On decomposition of graphs.Stud. Sci. Math. Hungar., 1:237–238, 1966

    work page 1966

  11. [11]

    Pękała and J

    P. Pękała and J. Przybyło. On List Extensions of the Majority Edge Colourings.Electron. J. Combin., 32(4):#P4.38, 2025

    work page 2025

  12. [12]

    Shelah and E

    S. Shelah and E. Milner. Graphs with no unfriendly partitions.in A. Baker, B. Bollobás, A. Hajnal, (eds.), A Tribute to Paul Erdős, Cam- bridge University Press, page 373–384, 1990. 13

    work page 1990