Structural and computational aspects of majority coloring games

1.1 Coloring games on graphs

• Coloring games vary the rule for legal moves; the majority condition limits each vertex’s same-colored neighbors to at most half its degree.Strong majority coloring instead bounds every monochromatic subset of a vertex’s neighborhood by half its degree.Source: §1.1 · p. 2, §1.2 · pp. 2–3

1.3 Majority and relaxed (defective) coloring games: known results

• The majority game chromatic number is bounded above by the game coloring number, but it is unbounded on bipartite and 2-degenerate graph classes.Earlier work established a 3-color bound for 1-subdivisions and raised the general subdivision question.Source: The majority coloring game · p. 5

1.4 Our results

• Every subdivision of a finite simple graph has majority game chromatic number at most 3.The theorem permits a different positive number of subdivisions on each edge.Source: §1.4 · p. 6
• Rooted trees whose leaves all have depth k ≤ 4 have majority game chromatic number at most 3.Source: §1.4 · p. 6
• Natural three-color strategies for general trees can fail, and the paper examines why resolving the open bound μ_g(T) ≤ 3 is difficult.It also explains why strategies from marking and relaxed coloring games do not directly transfer.Source: The majority coloring game · p. 5, §1.4 · p. 6
• For infinite acyclic graphs with every degree between 2m and 2m + 1 for m ≥ 2, the majority game chromatic number is at most 2.Source: §1.4 · p. 7
• For cycles C_n of length n ≥ 3, Maj(C_n) = 3 when n ≠ 4, and Maj_g(C_n) = 2 when n = 4.Source: §1.4 · p. 7
• The Strong Majority Game Chromatic Number decision problem is PSPACE-complete for k ≥ 3, and Strong Majority 2-Coloring is NP-complete on Eulerian graphs.Source: §1.4 · p. 7

• An uncolored vertex is critical if it has three majority-colored neighbors of distinct colors, or two of distinct colors plus more than half its neighbors in the third color.Source: §2 · p. 7
• Alice must prevent both configurations; in the cited bounded-degree tree strategy, a rooted play order lets her prevent a majority-colored vertex from having an uncolored parent.The degree constraint already rules out the second configuration in that setting.Source: §2 · p. 7
• Subdivisions, low depth, and 2-caterpillars can let Alice focus on one critical configuration, while natural extensions of such strategies to general trees can fail.Source: §2 · p. 8

3 Subdivided graphs are game majority 3-colorable

• Every graph formed by subdividing each edge at least once has μ_g(G′) ≤ 3.Alice prioritizes old vertices; subdivision vertices of degree 2 cannot be critical, while potentially critical vertices are independent.Source: §3 · pp. 8–10

3.1 1-Subdivision of Claw

• The claw’s 1-subdivision needs 3 colors, although the unsubdivided claw needs 2.The proof gives Bob a strategy that leaves Alice with no legal two-color move.Source: §3 · p. 10, §3.1 · p. 11

3.2 2-Subdivision of Claw

• The claw’s 2-subdivision has μ_g(G) = 2, reversing the increase seen after one subdivision.The example illustrates non-monotone behavior under successive edge subdivisions.Source: §3 · p. 10, §3.2 · p. 12

Depth 1

• When all leaves have depth 1, the tree is a star and μ_g(T) = 2.Thus the stated depth range covers rooted trees with leaves at depths 1 through 4.Source: §4 · p. 12

Depth 2

• For trees whose leaves are at depth 2, μ_g(T) ≤ 3, and the bound is tight.The 1-subdivision of the claw is such a tree and has μ_g(G) = 3.Source: §4 · p. 13

Depth 3

• For trees whose leaves are at depth 3, three colors suffice.Alice avoids critical configurations at levels 1 and 2 by prioritizing internal vertices and responding when Bob colors a leaf whose parent is uncolored.Source: §4 · pp. 13–14

Depth 4

• For trees whose leaves are at depth 4, μ_g(T) ≤ 3.The strategy responds to majority-colored vertices and avoids critical configurations at the remaining levels, including near the root.Source: §4 · pp. 12–15

5.1 The coloring game strategy

• The coloring-game strategy lets Alice avoid config2 on any tree, but an example shows it does not work in the majority coloring game: Bob can leave u with no legal color.Red and green are unavailable at u because of the leaf-neighbor majority condition; blue violates the majority condition at degree-three vertex 5.Source: §5.1 · pp. 15–16

5.2 A natural extension of the strategy of Theorem 4(1)

• The strategy of immediately coloring the parent of each majority-colored vertex and using minimum-used colors on siblings fails on arbitrary trees.Across repeated gadgets, Bob forces Alice’s choices to forbid colors at a central vertex, then colors a leaf to eliminate the remaining color.Source: §5.2 · pp. 16–17

5.3 The parametric strategies

• The λ-strategy prioritizes vertices by the moves needed to reach either critical configuration, but can overlook a threatened vertex because λ ignores colors already used in neighbors’ neighborhoods.In the counterexample, λ(4) ties with other vertices, so Alice may choose vertex 6 instead and eventually lose.Source: §5.3 · pp. 18, 20, 21
• The (λ, μ)-strategy adds μ_i(v), the moves needed to make v majority colored with color i, but it also fails to guarantee Alice a win.Its counterexample needs no random tie-breaking, and Bob can repeat a pattern across tree gadgets to create a problematic vertex.Source: The (𝝀, 𝝁)-strategy · pp. 21, 22, 24
• Both parametric strategies miss future threats despite measuring criticality or majority-coloring urgency; the authors suspect bounded-radius move-selection strategies can be defeated on sufficiently large trees.They suggest that a strategy might also measure the impact of a move on neighboring vertices, while suspecting similar gadgets could defeat that approach.Source: The (𝝀, 𝝁)-strategy · p. 24, What do these parametric strategies… · p. 24

5.4 Majority game chromatic number of infinite acyclic graphs

• For such a graph, the majority coloring game is equivalent to the 2-relaxed coloring game; for the graph defined above, μ_g(G) ≤ 2, so Alice has a winning strategy with two colors.The strategy cuts the forest into trunks whose endpoints are colored and selects a trunk vertex for Alice; it extends to infinite locally finite acyclic graphs.Source: §5.4 · pp. 24–25
• Unlike relaxed coloring, where leaves play no significant role, a winning strategy for Bob on a finite tree must exploit leaves.In the majority game, coloring a leaf automatically majority-colors it, so its neighbor cannot receive the same color.Source: §5.4 · p. 25
• A forest with all internal vertices of degree 4 or 5 can have μ_g(F) = 3; a 4-internal-regular tree is given as an example.The example shows that the two-color bound for infinite acyclic graphs does not extend to finite acyclic graphs with the corresponding fixed internal degrees.Source: §5.4 · p. 26
• In the 4-internal-regular example, Bob’s leaf moves force Alice to color their parents, and later both colors are forbidden at v_c.After Bob colors vertex 12 red, three blue neighbors forbid blue at v_c, while two red neighbors of vertex 12 forbid red there.Source: §5.4 · p. 26
• For infinite acyclic graphs with 2m ≤ deg(v) ≤ 2m+1 and m ≥ 2, μ_g(G) ≤ 2.The majority game reduces to an m-relaxed coloring game, for which forests have game chromatic number at most 2.Source: §5.4 · p. 26
• For a sufficiently large 3-internal-regular tree T, μ_g(T) = 3 = χ_1^g(T), so leaves do not guarantee a larger majority game chromatic number than the relaxed game’s.The section also notes that the finite-graph obstruction persists for internal degree 2m, by adjusting the colors assigned to children of v_c and vertex 12.Source: §5.4 · pp. 26–27

6.1 1-Caterpillars

• For 1-caterpillars, config2 is redundant: Alice needs only to prevent config1.The proof concludes that no critical configuration arises, using an infinite-descent argument.Source: §6.1 · pp. 27, 29
• The strategy ensures an uncolored spine node has at most one colored leg and can be colored differently from its right neighbor.For an internal node with more than one leg, it cannot be majority colored while an uncolored non-leg neighbor remains.Source: §6.1 · pp. 27–28
• Alice responds to Bob coloring a leg by coloring its spine vertex, delays her own leg moves until the spine is colored, and chooses spine colors unlike the right neighbor.When no internal spine node is uncolored, she colors a leg.Source: §6.1 · pp. 27–28

6.2 2-Caterpillars

• Alice wins the majority coloring game on caterpillars with leg lengths at most two using three colors.The strategy postpones coloring leg vertices until the spine is colored and responds to Bob coloring a leg by coloring its spine vertex.Source: §6.2 · p. 30
• On 2-caterpillars, a spine vertex cannot reach config2 because Alice colors it as soon as Bob colors the first of the required leg vertices.Vertices of degree two on length-two legs are left uncolored until the spine is colored.Source: §6.2 · p. 30

7 Strong majority colorings of cycles

• In a strong majority coloring of a cycle, vertices at distance two must have different colors.Each vertex has degree two, so its two neighbors cannot share a color.Source: §7 · p. 31
• Maj_g(C3) = 3, Maj_g(C4) = 2, and Maj_g(Cn) = 3 for n≥5.Thus the strong majority game chromatic number is characterized for all cycles.Source: §7 · pp. 32–33
• On C4, two colors are both necessary and sufficient because Bob cannot forbid both colors at a vertex.Alice’s first move also requires the two neighbors of a vertex to differ.Source: §7 · p. 32
• For cycles of length at least five, Bob can force a loss with two colors by coloring the fifth vertex opposite Alice’s first move, leaving the third vertex without a legal color.Together with the three-color upper bound, this gives Maj_g(Cn) = 3 for n≥5.Source: §7 · pp. 32–33

8.1 Complexity of the decision version of the strong majority coloring game

• For k ≥ 3, deciding whether Alice has a winning strategy in the Strong Majority Coloring Game is PSPACE-complete.The proof establishes PSPACE membership from the polynomial-depth game tree and hardness through a polynomial-time reduction from Game Coloring Problem (2).Source: §8.1 · pp. 33, 38

8.2 Complexity of deciding whether a given graph 𝑮has a strong majority coloring with 2 colors

• Strong Majority 2-Coloring is NP-complete on Eulerian graphs.The paper establishes NP membership and gives a polynomial-time reduction from NAE 3-SAT to an Eulerian graph instance.Source: §8.2 · pp. 39–40
• A strong majority 2-coloring yields a satisfying NAE 3-SAT assignment, with every clause containing both a true and a false literal.Each clause has either two true and one false literal, or two false and one true literal.Source: §8.2 · p. 41
• The Strong Majority 2-Coloring problem is NP-complete on Eulerian graphs.Source: §8.2 · p. 41

9 Concluding Remarks

• The paper proves μ_g(G) ≤ 3 for subdivisions, 2-caterpillars, and rooted trees whose leaves have depth k ≤ 4, and reports exact cycle values and complexity results.The complexity results include PSPACE-completeness for the Strong Majority Game Chromatic Number problem and NP-completeness of Strong Majority 2-Coloring on Eulerian graphs.Source: §9 · pp. 41–42
• The authors ask whether winning with two colors on a tree implies winning with three, and which caterpillars are game majority 2-colorable.They connect the first question to Zhu’s question for the majority coloring game on trees.Source: §9 · pp. 42–43
• Joining the centers of two arbitrary stars by a path gives a game majority 2-colorable tree that can have arbitrarily large degree.The authors add that simple degree conditions do not seem sufficient to characterize game majority 2-colorable trees.Source: §9 · p. 43
• Whether μ_g(T) ≤ 3 for every tree remains open, and the authors discuss difficulties with natural strategies for this question.They note that resolving the question for 3-caterpillars was not straightforward.Source: §9 · p. 43
• Open questions ask whether bounded-move or local strategies can win on trees, and whether Alice can win using only O(1) or o(n) moves of a fourth color.The paper notes that it has no known strategy using a sublinear number of fourth-color uses.Source: §9 · p. 44