pith. sign in

arxiv: 2604.20752 · v1 · submitted 2026-04-22 · 🧮 math.CO

Majority C-coloring of graphs

Csilla Bujtas , Magda Dettlaff , Hanna Furmanczyk , Aleksandra Laskowska This is my paper

Pith reviewed 2026-05-09 23:55 UTC · model grok-4.3

classification 🧮 math.CO
keywords majority coloringC-coloringmajority C-chromatic numbergraph coloringchromatic numberNP-completenessgraph powerscubic graphs
0
0 comments X

The pith

Majority C-colorings require each vertex to share its color with at least half its neighbors, and satisfy mc(G) + chi(G) <= n+1 for any graph on n vertices.

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

The paper defines majority C-coloring as a vertex coloring in which every vertex receives a color shared with at least half its neighbors. It studies the majority C-chromatic number mc(G), the largest number of colors possible under this rule. An upper bound on mc(G) is given in terms of the number of vertices and the minimum and maximum degrees, and this bound is shown to be tight for the k-th powers of paths and cycles as well as for certain cubic graphs containing diamonds. The authors prove that mc(G) and the ordinary chromatic number chi(G) can differ by any integer yet always sum to at most n+1, that deciding whether mc(G) is at least a fixed k is NP-complete, and that mc is not monotone when edges are deleted.

Core claim

A majority C-coloring is a vertex coloring of G in which every vertex has the same color as at least half of its neighbors. The majority C-chromatic number mc(G) is the maximum number of colors that can appear in any such coloring. The paper proves an upper bound on mc(G) expressed using the order n and the minimum and maximum degrees of G, demonstrates equality for powers of paths and cycles, obtains mc(G) = (n - d)/3 for (claw, K4)-free cubic graphs with d diamonds, shows the inequality mc(G) + chi(G) <= n + 1 for every n-vertex graph, determines the extremal numbers of edges in graphs with a prescribed mc value, and establishes NP-completeness of the decision problem mc(G) >= k for each k

What carries the argument

The majority C-chromatic number mc(G), the largest size of a coloring in which each vertex matches at least half its neighbors in color.

If this is right

  • For the k-th power of any path or cycle on n >= k + 1 vertices, mc equals floor(n / (k + 1)).
  • In a (claw, K4)-free cubic graph containing d diamonds, mc(G) equals exactly (n - d)/3.
  • Removing a single edge from G can increase mc by 1 or decrease it by 2.
  • For every n and k the minimum and maximum number of edges in an n-vertex graph with mc(G) = k are determined.
  • While mc(G) and chi(G) are incomparable, their sum never exceeds n + 1.

Where Pith is reading between the lines

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

  • The NP-completeness result for every fixed k >= 2 implies that computing the exact value of mc(G) is NP-hard in general.
  • The observed non-monotonicity under edge deletion sets mc apart from many other coloring parameters that are monotone.
  • The linear-time algorithm for trees raises the possibility of polynomial-time methods for graphs of bounded treewidth.
  • The degree-dependent upper bound on mc(G) may be used to derive concentration results for mc on random graphs.

Load-bearing premise

The phrase 'at least half of its neighbors' is treated as unambiguously defined for vertices of both even and odd degree.

What would settle it

A graph G on n vertices for which mc(G) + chi(G) exceeds n + 1, or a polynomial-time algorithm that decides whether mc(G) >= 3 on arbitrary graphs.

Figures

Figures reproduced from arXiv: 2604.20752 by Aleksandra Laskowska, Csilla Bujtas, Hanna Furmanczyk, Magda Dettlaff.

Figure 1
Figure 1. Figure 1: C⩾-coloring of (a) subdivided star S(S5), (b) complete bipartite graph K2,3, and (c) complete bipartite graph K4,4, using the maximum number of colors. By definition, the color classes of a C⩾-coloring may represent communities in biological or social networks. In general, the notion of majority C-coloring is closely connected to clustering problems. Further applications will be discussed in more detail in… view at source ↗
Figure 2
Figure 2. Figure 2: A schematic drawing of the partition used in the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: An example of a cubic graph G ∈ G and its χ⩾-coloring. Corollary 11. For every positive integer k, there exists a connected cubic graph G with χ⩾(G) = k. 4 Size, order, χ(G), and χ⩾(G) In this section, different types of connections between the four invariants in the title are discussed. First, the maximum and minimum sizes of a graph are determined in terms of the order and C⩾- chromatic number. The secon… view at source ↗
read the original abstract

Inspired by the majority colorings and C-colorings, we introduce and study the majority C-coloring of graphs. In such a vertex coloring, every vertex shares its color with at least half of its neighbors. The maximum number of colors that can be used in a majority C-coloring of a graph $G$ is called the majority C-chromatic number and denoted by $\mc(G)$. An upper bound on $\mc(G)$ is proved in terms of the order, minimum, and maximum degree. Its sharpness is demonstrated by several results over different graph classes. In particular, $\mc(P_n^k)= \mc(C_n^k)= \lfloor n/(k+1)\rfloor$ is true for the $k$-th power of a path and a cycle if $n \ge k+1$. Further, $\mc(G) = (n-d)/3$ holds if $G$ is a $(\mbox{claw}, K_4)$-free cubic graph and contains $d$ diamonds. %claw-free cubic graph on $n \ge 6$ vertices and contains $d$ diamonds. It is further shown that the majority C-chromatic number is not monotone under edge deletion. In fact, both the lower and upper bounds are sharp in the inequality chain $\mc(G)-2 \leq \mc(G-e) \leq \mc(G) +1$. The minimum and maximum number of edges in an $n$-vertex graph $G$ with $\mc(G)=k$ are determined for every $n$ and $k$. It is also pointed out that the classical chromatic number $\chi(G)$ and $\mc(G)$ are incomparable, and the difference $\mc(G)-\chi(G)$ can take any positive or negative integer. On the other hand, $\mc(G)+\chi(G) \leq n+1$ holds for every graph $G$ of order $n$. The decision problem of whether $\mc(G) \ge k$ holds is NP-complete for every fixed $k\ge 2$. In contrast, some sufficient conditions for $\mc(G) \ge 2$ are proved, and a linear-time algorithm is presented that determines $\mc(T)$ if $T$ is a tree.

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

1 major / 2 minor

Summary. The paper introduces majority C-coloring, a vertex coloring where every vertex shares its color with at least half its neighbors, and defines mc(G) as the maximum number of colors in such a coloring of G. It proves an upper bound on mc(G) in terms of order n, minimum degree, and maximum degree; shows sharpness via exact values mc(P_n^k) = mc(C_n^k) = floor(n/(k+1)) for n >= k+1 and mc(G) = (n-d)/3 for (claw, K4)-free cubic graphs with d diamonds; establishes that mc is not monotone under edge deletion with sharp inequalities mc(G)-2 <= mc(G-e) <= mc(G)+1; determines the minimum and maximum edges in n-vertex graphs with mc(G)=k; shows mc(G) and chi(G) are incomparable but satisfy mc(G) + chi(G) <= n+1; proves NP-completeness of deciding mc(G) >= k for each fixed k >= 2; and gives sufficient conditions for mc(G) >= 2 together with a linear-time algorithm to compute mc(T) for trees.

Significance. If the definition is clarified and proofs hold under a consistent convention, the work contributes to the literature on constrained graph colorings by merging majority and C-coloring concepts. Strengths include the sharpness demonstrations over multiple graph families, the NP-completeness result for the decision problem, and the linear-time algorithm for trees, all of which provide concrete, falsifiable statements that could support further algorithmic and extremal investigations.

major comments (1)
  1. [Definition and Introduction] Definition of majority C-coloring (Introduction and §2): the requirement that a vertex 'shares its color with at least half of its neighbors' is ambiguous for odd degree d(v)=2m+1. It is unclear whether this means at least m+1 same-color neighbors (strictly more than half) or at least m (floor(d(v)/2)). This convention is load-bearing for the cubic-graph formula mc(G)=(n-d)/3, the NP-completeness reductions for k>=2, and the tree algorithm, all of which depend on exact neighbor-counting arguments; without an explicit statement and consistent use throughout the proofs, the claimed bounds and complexity results cannot be verified.
minor comments (2)
  1. [Abstract] The abstract states mc(G)=(n-d)/3 for (claw,K4)-free cubic graphs containing d diamonds, but the parenthetical remark in the full text appears to contain a minor wording inconsistency with the abstract; align the statements for clarity.
  2. [Introduction] Notation for the majority C-chromatic number is introduced as mc(G) but could benefit from an explicit formal definition paragraph immediately after the informal description to aid readers.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need for greater precision in the definition. We address the major comment below and will incorporate the necessary clarification in the revised manuscript.

read point-by-point responses

  1. Referee: Definition of majority C-coloring (Introduction and §2): the requirement that a vertex 'shares its color with at least half of its neighbors' is ambiguous for odd degree d(v)=2m+1. It is unclear whether this means at least m+1 same-color neighbors (strictly more than half) or at least m (floor(d(v)/2)). This convention is load-bearing for the cubic-graph formula mc(G)=(n-d)/3, the NP-completeness reductions for k>=2, and the tree algorithm, all of which depend on exact neighbor-counting arguments; without an explicit statement and consistent use throughout the proofs, the claimed bounds and complexity results cannot be verified.

    Authors: We agree that the phrasing 'at least half' requires an explicit convention for odd degrees. Our intended meaning throughout the paper is that v must have at least ceil(d(v)/2) neighbors of the same color (i.e., at least m+1 when d(v)=2m+1). This is the natural reading of 'at least half' and is the convention used in all proofs. In the revision we will add the following sentence immediately after the definition: 'Equivalently, every vertex v has at least ceil(d(v)/2) neighbors of the same color as v.' We have re-checked the cubic-graph formula, the NP-completeness reductions, and the tree algorithm; each argument remains valid and unchanged under this explicit convention. The referee's concern is therefore resolved by the added clarification. revision: yes

Circularity Check

0 steps flagged

No circularity: bounds and complexity results derive from direct graph-theoretic counting and reductions.

full rationale

The paper defines majority C-coloring via the explicit neighbor-sharing condition and proves upper bounds on mc(G) using order, minimum degree, and maximum degree together with explicit constructions for sharpness on paths, cycles, and (claw, K4)-free cubic graphs. The NP-completeness reduction for mc(G) >= k and the tree algorithm are presented as standard decision-problem reductions without any fitted parameters, self-referential definitions, or load-bearing self-citations. No equation or claim reduces a derived quantity to an input by construction; all results remain independent of the target mc(G) values.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard definitions of graphs, degrees, and neighbors with no fitted numerical parameters, no new postulated entities, and only background graph axioms.

axioms (1)
  • standard math Standard definitions of simple undirected graphs, vertex degrees, and neighbor sets.
    Invoked throughout the definition of majority C-coloring and all bounds.

pith-pipeline@v0.9.0 · 5724 in / 1394 out tokens · 39739 ms · 2026-05-09T23:55:21.580510+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

28 extracted references · 28 canonical work pages

  1. [1]

    Arocha, J

    J.L. Arocha, J. Bracho, and V. Neumann-Lara, On the minimum size of tight hypergraphs. J. Graph Theory16(1992) 319–326

    work page 1992

  2. [2]

    Bacs´ o and Zs

    G. Bacs´ o and Zs. Tuza, Upper chromatic number of finite projective planes.J. Combin. Des. 16(2008) 221–230

    work page 2008

  3. [3]

    Bazgan, Zs

    C. Bazgan, Zs. Tuza, and D. Vanderpooten,On the existence and determination of satisfac- tory partitions in a graph.in: Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003), LNCS 2906, 444–453

    work page 2003

  4. [4]

    Bazgan, Zs

    C. Bazgan, Zs. Tuza, and D. Vanderpooten, The satisfactory partition problem.Discrete Appl. Math.154(2006), 1236–1245

    work page 2006

  5. [5]

    Bl´ azsik, A

    Z.L. Bl´ azsik, A. Blokhuis, ˇS. Miklaviˇ c, Z.L. Nagy, and T. Sz˝ onyi, On the balanced upper chromatic number of finite projective planes.Discrete Math.344(2021) 1–8. 20

    work page 2021

  6. [6]

    Bujt´ as, E

    Cs. Bujt´ as, E. Sampathkumar, Zs. Tuza, L. Pushpalatha, and R.C. Vasundhara, Improper C-colorings of graphs.Discrete Appl. Math.159(2010) 174–186

    work page 2010

  7. [7]

    Bujt´ as and Zs

    Cs. Bujt´ as and Zs. Tuza, C-perfect hypergraphs.J. Graph Theory64(2009) 132–149

    work page 2009

  8. [8]

    Bujt´ as and Zs

    Cs. Bujt´ as and Zs. Tuza, Maximum number of colors: C-coloring and related problems.J. Geom.101(2011) 83–97

    work page 2011

  9. [9]

    F. Bock, R. Kalinowski, J. Pardey, M. Pli´ sniak, D. Rautenbach and M. Wo´ zniak, Majority edge-colorings of graphs.Electron. J. Combin.30(1)(2023)

    work page 2023

  10. [10]

    J. Cai, W. Xia, and G. Yan, Some new results on majority coloring of digraphs.Acta Math. Appl. Sin. Engl. Ser.41(2025) 337–343

    work page 2025

  11. [11]

    Erd˝ os, A

    P. Erd˝ os, A. R´ enyi, V. T. S´ os, On a problem of graph theory.Studia Sci. Math. Hungar.1 (1966) 215–235

    work page 1966

  12. [12]

    Gerber and D

    M. Gerber and D. Kobler, Partitioning a graph to satisfy all vertices. Technical report, Swiss Federal Institute of Technology, Lausanne, 1998

    work page 1998

  13. [13]

    Gerber and D

    M. Gerber and D. Kobler, Algorithmic approach to the satisfactory graph partitioning prob- lem.European J. Oper. Res.125(2000) 283–291

    work page 2000

  14. [14]

    Gerber and D

    M. Gerber and D. Kobler, Classes of graphs that can be partitioned to satisfy all their vertices.Australas. J. Combin.29(2004) 201–2014

    work page 2004

  15. [15]

    Jiang, D

    T. Jiang, D. Mubayi, Zs. Tuza, V. Voloshin, and D.B. West, The chromatic spectrum of mixed hypergraphs.Graphs Combin.18(2002) 309–318

    work page 2002

  16. [16]

    Kreutzer, S

    S. Kreutzer, S. Oum, P. Seymour, D. van der Zypen, and D.R. Wood, Majority colourings of digraphs.Electron. J. Combin.24(2)(2017)

    work page 2017

  17. [17]

    K¨ undgen, E

    A. K¨ undgen, E. Mendelsohn, and V. Voloshin, Colouring of planar mixed hypergraphs. Electron. J. Combin.7(2000) R60

    work page 2000

  18. [18]

    Lov´ asz, On decomposition of graphs.Studia Sci

    L. Lov´ asz, On decomposition of graphs.Studia Sci. Math. Hungar.1(1966) 237–238

    work page 1966

  19. [19]

    Moshi, Matching cutsets in graphs.J

    A.M. Moshi, Matching cutsets in graphs.J. Graph Theory13(1989) 527–536

    work page 1989

  20. [20]

    Shafique and R.D

    K.H. Shafique and R.D. Dutton, On satisfactory partitioning of graphs.Congressus Numer- antium154(2002) 183–194

    work page 2002

  21. [21]

    Schelling, Models of segregation.Amer

    T.C. Schelling, Models of segregation.Amer. Econ. Rev.59(1969) 488–493

    work page 1969

  22. [22]

    Staton, Edge deletions and the chromatic number.Ars Combin.10(1980) 103–106

    W. Staton, Edge deletions and the chromatic number.Ars Combin.10(1980) 103–106

    work page 1980

  23. [23]

    Sterboul,A new combinatorial parameter

    F. Sterboul,A new combinatorial parameter. Infinite and Finite Sets. Colloq. Math. Soc. J. Bolyai, Keszthely 1973. Vol. 10, 1387–1404, North-Holland/American Elsevier, 1975

    work page 1973

  24. [24]

    Tur´ an, On an extremal problem in graph theory.Mat

    P. Tur´ an, On an extremal problem in graph theory.Mat. Fiz. Lapok(in Hungarian)48 (1941) 436–452

    work page 1941

  25. [25]

    Voloshin, The mixed hypergraphs.Comput

    V.I. Voloshin, The mixed hypergraphs.Comput. Sci. J. Moldova1(1993) 45–52

    work page 1993

  26. [26]

    Voloshin, On the upper chromatic number of a hypergraph.Australas

    V.I. Voloshin, On the upper chromatic number of a hypergraph.Australas. J. Combin.11 (1995) 25–45

    work page 1995

  27. [27]

    Voloshin,Coloring Mixed Hypergraphs: Theory, Algorithms and Applications

    V.I. Voloshin,Coloring Mixed Hypergraphs: Theory, Algorithms and Applications. Series: Fields Institute Monographs, Vol. 17, Amer. Math. Soc., 2002

    work page 2002

  28. [28]

    West,Introduction to Graph Theory

    D.B. West,Introduction to Graph Theory. Prentice Hall, 2001. 21

    work page 2001