On acyclic b-chromatic number of cubic graphs

Basic Information

• Paper ID: 2511.01532
• Title: On acyclic b-chromatic number of cubic graphs
• Authors: Marcin Anholcer (Poznań University of Economics and Business), Sylwia Cichacz (AGH University), Iztok Peterin (University of Maribor)
• Classification: math.CO (Combinatorics), cs.DM (Discrete Mathematics)
• Publication Date: November 4, 2025
• Paper Link: https://arxiv.org/abs/2511.01532

Abstract

This paper investigates the properties of the acyclic b-chromatic number on cubic graphs. An acyclic k-coloring requires that adjacent vertices have different colors and the subgraph induced by any two colors is a forest. The acyclic b-chromatic number $A_b(G)$ is the maximum number of colors used in an acyclic coloring from which no acyclic recoloring step can be performed. The paper proves that for all cubic graphs except one exception, the acyclic b-chromatic number is either 4 or 5, and provides detailed investigations of the acyclic b-chromatic number for generalized Petersen graphs and (0,j)-prism graphs.

Research Background and Motivation

Research Problem

This paper investigates the acyclic b-chromatic number problem, which combines two classical graph coloring concepts:

1. b-coloring: Introduced by Irving and Manlove in 1999, maximizing the number of colors in the final coloring through iterative recoloring steps starting from a trivial coloring
2. Acyclic coloring: Proposed by Grünbaum, requiring that the subgraph induced by any two colors is acyclic (forest)

Significance

This problem has the following important implications:

• Theoretical value: Connects two important graph coloring variants, forming a new graph invariant
• Regular graph research: For d-regular graphs, whether the b-chromatic number equals d+1 is a central question. Cubic graphs (3-regular graphs) represent the simplest non-trivial case
• Combinatorial optimization: Provides new optimization perspectives for graph coloring problems

Limitations of Existing Research

• For the b-chromatic number φ(G), all cubic graphs except four exceptions are known to have φ(G)=4 (Jakovac and Klavžar, 2010)
• For the acyclic b-chromatic number $A_b(G)$, previous work 3 only established the basic theoretical framework, lacking systematic investigation of specific graph classes
• The relationship between $A_b(G)$ and other graph parameters (such as $\Delta(G)$, φ(G), A(G)) remains unclear

Research Motivation

The authors aim to systematically investigate the acyclic b-chromatic number of cubic graphs, which is an important step toward general results for regular graphs. As the simplest non-trivial class of regular graphs, cubic graphs provide insights applicable to more general cases.

Core Contributions

1. Establishes the fundamental range of acyclic b-chromatic number for cubic graphs: Proves that for all cubic graphs G except the prism $K_2\Box K_3$, we have $4 \leq A_b(G) \leq 5$
2. Reveals essential differences from b-chromatic number: Proves that there exist infinitely many cubic graphs G satisfying $A_b(G)=4$, contrasting sharply with the finiteness results for b-chromatic number
3. Completely determines the acyclic b-chromatic number for special graph classes:
   • Generalized Petersen graphs G(n,k): When $k \geq 3$ and n is sufficiently large, $A_b(G(n,k))=5$
   • Prisms G(n,1): For $n \geq 4$, $A_b(G(n,1))=4$; $A_b(K_2\Box K_3)=3$
   • (0,j)-prisms: When $j > 0$ and $n \geq 5(j+2)$, $A_b(\text{Pr}_n(0,j))=5$
4. Constructive proof methods: Provides explicit 5-colorings, demonstrating two types of acyclic b-vertices (Type A and Type B)
5. Proposes open problems: Including computational complexity, acyclic b-chromatic number of snark graphs, etc.

Detailed Methodology

Task Definition

Acyclic coloring: A k-coloring $c: V(G) \to [k]$ of graph G is called an acyclic coloring if:

• Adjacent vertices have different colors (proper coloring condition)
• For any $i,j \in [k]$, the subgraph $G[V_i \cup V_j]$ induced by colors i and j is a forest

Acyclic recoloring step: For a color class $V_i$, if each vertex $v \in V_i$ is missing some color $\ell_v$ in its closed neighborhood, and recoloring all $v \in V_i$ to $\ell_v$ maintains an acyclic coloring, this is called an acyclic recoloring step.

Acyclic b-chromatic number $A_b(G)$: Starting from a trivial coloring (each vertex has a distinct color), iteratively applying acyclic recoloring steps, the maximum number of colors when no further recoloring is possible.

Acyclic b-vertex: In a coloring where no acyclic recoloring can be performed, if any recoloring of vertex v produces a bichromatic cycle, then v is an acyclic b-vertex.

Theoretical Framework

Key properties:

1. For cubic graphs, $A_b(G) \leq 5$ (derived from the general upper bound $A_b(G) \leq \frac{1}{2}\Delta(G)^2 + 1$)
2. $A(G) \leq A_b(G)$ (acyclic chromatic number is a lower bound)
3. Classification of acyclic b-vertices:
   • Type A: Three neighbors have the same color
   • Type B: Neighbors have two different colors

Blocking cycle: For an acyclic b-vertex v (color i), if color j is missing from its closed neighborhood, the shortest bichromatic cycle preventing v from being recolored to j is called a $j_v$-cycle.

Main Technical Methods

1. Reachability of Acyclic Colorings (Theorem 3.2)

Core idea: Any 4-coloring of a cubic graph can be transformed into an acyclic 4-coloring through local adjustments that eliminate all bichromatic cycles.

Algorithm flow:

Input: 4-coloring c of cubic graph G (possibly with bichromatic cycles)
Output: Acyclic 4-coloring of G

while there exists a bichromatic cycle C do:
    Let C = v₁v₂...vₖv₁ with alternating colors 1 and 2
    Let uᵢ be the third neighbor of vᵢ
    
    Case 1: There exists uⱼ such that c(uⱼ) ∈ {1,2}
        Based on colors of uⱼ₋₁ and uⱼ₊₁, recolor vⱼ to color 3 or 4
        
    Case 2: All uᵢ have colors not in {1,2}
        Assume c(u₂)=3, recolor v₂ to 4
        If a new bichromatic cycle is created, further adjust colors of v₁,v₂,v₃

Key property: Each operation strictly decreases the number of bichromatic cycles, guaranteeing algorithm termination.

2. Lower Bound Construction for Cubic Graphs (Theorem 3.3)

Strategy: Utilize the proof framework of Jakovac and Klavžar for b-chromatic number, correcting bichromatic cycles within.

Steps:

1. Begin coloring on the shortest cycle C
2. Extend to vertices near C, ensuring each color has a b-vertex
3. For the four configurations in 18 where bichromatic cycles appear (see Figure 3), provide corrected colorings
4. Use greedy coloring for the remaining part, applying Theorem 3.2 to eliminate bichromatic cycles

3. Tightness of Upper Bound 5

Constructing infinitely many cubic graphs with $A_b(G)=4$ (Theorem 3.5):

Construct cubic graph C(T) from cubic tree T:

• Replace each internal vertex v (degree 3) of T with a triangle abc
• Attach copies of subgraph $H_3$ at each leaf of T

Key Lemma 3.4: A degree-2 vertex w in $H_3$ cannot be an acyclic b-vertex in any 5-coloring.

Proof strategy:

• w as a cut vertex has at most 4 colors in its closed neighborhood
• If w is an acyclic b-vertex, it must be Type B (neighbors same color)
• But w's two neighbors in $H_3$ are adjacent, contradiction

Therefore C(T) cannot have an acyclic b-coloring with 5 colors, while a 4-coloring is constructible.

4. 5-Coloring Construction for Generalized Petersen Graphs (Theorem 4.1)

Conditions: $k \geq 3$, $n \geq 5(2k + (-1)^k)$

Construction strategy: Design local configurations such that specific vertices $x_j$ become Type B acyclic b-vertices.

Case of odd k:

• Construct two cycles $C^1_j$ and $C^2_j$ containing $x_j$
• $C^1_j$: length $k+2$, using colors $c^0_j, c^1_j, c^3_j$
• $C^2_j$: length $2k+2$, using colors $c^0_j, c^2_j, c^3_j$
• Neighbors of $x_j$ colored with $c^3_j$ and $c^4_j$
• $C^1_j$ is a $(c^1_j)_{x_j}$-cycle, $C^2_j$ is a $(c^2_j)_{x_j}$-cycle

Repeating pattern: Place an acyclic b-vertex every $2k-1$ positions, ensuring consistency through color permutations.

Case of even k: Similar construction with interval $2k+1$.

Experimental Setup

This is a pure theoretical mathematics paper with no computational experiments. All results are obtained through rigorous mathematical proofs.

Research Objects

• General cubic graphs: All graphs with vertex degree 3
• Special graph classes:
  • Petersen graph P = G(5,2)
  • Prisms $K_2\Box K_3$, $K_{3,3}$, $G_1$
  • Generalized Petersen graphs G(n,k)
  • (0,j)-prisms $\text{Pr}_n(0,j)$
  • Graphs C(T) constructed from cubic trees

Proof Techniques

• Constructive proofs: Explicit coloring schemes
• Proof by contradiction: Showing certain colorings cannot exist
• Mathematical induction: Algorithm for eliminating bichromatic cycles
• Configuration analysis: Exhaustive analysis of local structure possibilities

Experimental Results

Main Results

Result 1: Fundamental Range for Cubic Graphs (Theorem 3.3)

Theorem: For each cubic graph G, except $K_2\Box K_3$, we have $A_b(G) \geq 4$. Furthermore, $A_b(K_2\Box K_3) = 3$.

Significance: Combined with the upper bound $A_b(G) \leq 5$, this determines the possible values of acyclic b-chromatic number for cubic graphs as {3,4,5}.

Result 2: Contrast with b-Chromatic Number (Corollary 3.6)

Theorem: The number of cubic graphs satisfying $A_b(G) < 5$ is infinite.

Contrast: Cubic graphs with φ(G)<4 number only 4 (Theorem 3.1).

Specific examples: For any cubic tree T, $A_b(C(T)) = 4$ (Theorem 3.5). Since cubic trees are infinite in number, the conclusion holds.

Result 3: Generalized Petersen Graphs (Theorems 4.1, 4.2)

Key findings:

• Petersen graph cannot achieve 5 due to acyclic b-vertex existence constraints
• Regular prisms (k=1) achieve at most 4
• When parameter k≥3 and n is sufficiently large, the upper bound 5 can be achieved

Result 4: (0,j)-Prisms (Theorem 5.1)

Theorem: If $j > 0$ and $n \geq 5(j+2)$, then $A_b(\text{Pr}_n(0,j)) = 5$.

Construction highlights:

• Design local configurations at vertices $v^1_{2i+1}$
• Utilize two cycles $C^1_k$ and $C^2_k$ to block specific colors
• Repeat configuration every $j+2$ positions

Technical Findings

Finding 1: Type Analysis of Acyclic b-Vertices

For non-b-vertices in cubic graphs:

• Type A (three neighbors same color): Difficult to construct, requires special structure
• Type B (neighbors two colors): More common, achieved through bichromatic cycle blocking

Finding 2: Repeatability of Local Configurations

Through carefully designed color permutation schemes, local acyclic b-coloring configurations can be periodically repeated to construct arbitrarily large graphs.

Finding 3: Restrictive Role of Cut Vertices

Lemma 3.4 reveals: A degree-2 cut vertex (such as w in $H_3$) cannot be an acyclic b-vertex in any 5-coloring. This is key to constructing the family of graphs with $A_b(G)=4$.

Case Studies

Case 1: 4-Coloring of Petersen Graph (Figure 2, left)

• Uses colors {1,2,3,4}
• Black vertices are acyclic b-vertices
• Color 1 vertices are Type A (three neighbors same color 2)
• Other color vertices are Type B

Case 2: Construction of $C(K_{1,3})$ (Figure 4)

• Central triangle colored with {1,2,3}
• Three $H_3$ copies colored with {1,2,3,4}
• Each $H_3$ contains a Type B acyclic b-vertex
• Overall achieves $A_b=4$ but cannot reach 5

Related Work

b-Coloring Research

1. Irving & Manlove (1999): Introduced b-chromatic number concept, proved NP-hardness
2. Kratochvíl, Tuza, Voigt (2002): Proved NP-hardness remains on connected bipartite graphs
3. Jakovac & Klavžar (2010): Proved all cubic graphs except four exceptions have φ(G)=4
4. El Sahili & Kouider Conjecture: d-regular graphs with girth at least 5 (except Petersen graph) have φ(G)=d+1

Acyclic Coloring Research

1. Grünbaum (1973): Introduced acyclic coloring, proved planar graphs have A(G)≤9
2. Borodin (1979): Proved planar graphs have A(G)≤5
3. Alon, McDiarmid, Reed (1991): Proved $A(G) \leq \lceil 50\Delta^{4/3}\rceil$
4. Gonçalves et al. (2020): Improved to $A(G) \leq \frac{3}{2}\Delta^{4/3} + O(\Delta)$

Acyclic b-Coloring Research

1. Anholcer, Cichacz, Peterin (2023): Introduced acyclic b-chromatic number, established basic theory
   • Proved problem is well-defined (finite termination)
   • Gave general upper bound $A_b(G) \leq \frac{1}{2}\Delta^2 + 1$
   • Proved $A_b(G)$ can be arbitrarily larger than $\Delta(G)$, φ(G), A(G)

Positioning of This Paper

This paper is the first systematic investigation of acyclic b-chromatic number for a specific regular graph class (cubic graphs), filling the gap between theory and concrete graph classes.

Conclusions and Discussion

Main Conclusions

1. Fundamental range determined: For all cubic graphs G except $K_2\Box K_3$, we have $4 \leq A_b(G) \leq 5$
2. Essential differences from b-chromatic number:
   • b-chromatic number: Only 4 cubic graphs have φ(G)<4 (finiteness)
   • Acyclic b-chromatic number: Infinitely many cubic graphs have $A_b(G)=4$ (infiniteness)
3. Complete characterization of special graph classes:
   • Generalized Petersen graphs: Achieve upper bound 5 when parameters are sufficiently large
   • Prisms: Achieve at most 4
   • Cubic tree constructions: Exactly 4
4. Construction techniques: Provides systematic 5-coloring construction methods based on periodic repetition of local configurations

Limitations

1. Incompletely resolved problems:
   • Complete characterization of when $A_b(G)=4$ vs. $A_b(G)=5$ for general cubic graphs remains unknown
   • Cases of generalized Petersen graphs G(n,k) with small n or k=2 not fully covered
2. Method limitations:
   • Construction methods depend on special graph structures (e.g., symmetry)
   • Lack of universal determination method for irregular or complex cubic graphs
3. Unknown computational complexity: The computational complexity of determining whether a cubic graph has $A_b(G)=4$ or 5 remains an open problem

Future Directions

The paper proposes three open problems:

Problem 6.1 (Computational Complexity): What is the computational complexity of determining whether a cubic graph G satisfies $A_b(G)=4$ or $A_b(G)=5$?

Problem 6.2 (Snark Graphs): What is the acyclic b-chromatic number of snark graphs (cubic graphs with no 3-edge coloring)?

Problem 6.3 (Acyclic Cubic Graphs): Find more graph classes of "acyclic cubic graphs" (where each vertex also has acyclic degree 3).

Conjecture 6.4 (Girth and b-Chromatic Number Relationship): If $g(G) > 2\phi(G)$, then $A_b(G) \geq \phi(G)$.

Speculation: When girth is sufficiently large, b-colorings are naturally acyclic, so acyclic b-chromatic number should equal b-chromatic number.

In-Depth Evaluation

Strengths

1. Theoretical completeness:
   • Systematically establishes the basic theoretical framework for acyclic b-chromatic number of cubic graphs
   • Rigorous proofs with clear logic; each theorem has complete proof
   • Cleverly utilizes existing b-chromatic number results (Jakovac & Klavžar)
2. Method innovation:
   • Local configuration design: Achieves acyclic b-vertices through carefully designed bichromatic cycle blocking mechanisms
   • Color permutation technique: Enables periodic repetition of local configurations to construct arbitrarily large graphs
   • Classification discussion: Type A and Type B classification of acyclic b-vertices simplifies analysis
3. Result profundity:
   • Reveals essential differences: Proves $A_b(G)$ and φ(G) behave fundamentally differently on cubic graphs (finiteness vs. infiniteness)
   • Constructive proofs: Not only proves existence but provides explicit constructions
   • Complete characterization of special classes: Gives exact values for multiple important graph classes
4. Writing clarity:
   • Numerous figures (Figures 1-11) intuitively display coloring schemes
   • Concepts introduced progressively from simple to complex
   • Clear distinction between different cases (odd/even k, different parameter ranges)

Weaknesses

1. Coverage scope:
   • For generalized Petersen graphs G(n,k), cases with k=2 or small n not fully resolved
   • Lacks necessary and sufficient conditions for general cubic graphs
   • No discussion of other important cubic graph classes (Cayley graphs, cage graphs)
2. Algorithmic perspective:
   • No determination algorithm or heuristic methods provided
   • Computational complexity completely open
   • Lacks discussion of practical computation (though this is a theoretical paper)
3. Gap between bounds:
   • For many cubic graphs, still unknown whether $A_b(G)=4$ or 5
   • Lacks easily verifiable sufficient conditions
4. Relationships with other parameters:
   • Beyond contrast with φ(G), lacks deep exploration of relationships with girth g(G), chromatic number χ(G), acyclic chromatic number A(G)
   • Conjecture 6.4 is proposed but not verified

Impact

1. Theoretical contribution:
   • Establishes foundation for acyclic b-chromatic number research on regular graphs
   • Construction techniques may apply to other regular graph classes
   • Revealed finiteness vs. infiniteness difference is important theoretical insight
2. Research directions:
   • Opens new research direction in cubic and regular graph coloring theory
   • Proposed open problems have clear research value
   • May inspire research on special cubic graphs like snarks and cage graphs
3. Practical value:
   • As pure theoretical research, direct applications are limited
   • Graph coloring has application background in scheduling, channel assignment, register allocation
   • Acyclic constraints have practical meaning in some applications (deadlock avoidance, circular dependency prevention)
4. Reproducibility:
   • All proofs are complete and verifiable
   • Construction methods are explicit and can be manually verified for small graphs
   • Suitable as starting point for further research

Applicable Scenarios

1. Theoretical research:
   • Researchers in graph coloring theory
   • Study of regular graph properties
   • Coloring problems in combinatorial optimization
2. Potential applications:
   • Network design (avoiding circular dependencies)
   • Scheduling problems (task grouping avoiding conflict cycles)
   • Compiler optimization (register allocation)
3. Educational value:
   • Demonstrates techniques of constructive proofs
   • Good case study for combinatorics and graph theory
   • Example of local-to-global construction

References

This paper cites 24 references, with key references including:

1. 17 Irving & Manlove (1999): Original paper on b-chromatic number
2. 18 Jakovac & Klavžar (2010): Key result on b-chromatic number of cubic graphs
3. 3 Anholcer, Cichacz, Peterin (2023): Introduction of acyclic b-chromatic number
4. 1 Alon, McDiarmid, Reed (1991): Classical upper bound for acyclic coloring
5. 5 Borodin (1979): Acyclic coloring of planar graphs
6. 21 Kratochvíl, Tuza, Voigt (2002): Complexity of b-chromatic number

Overall Assessment: This is a high-quality theoretical mathematics paper that systematically investigates the acyclic b-chromatic number problem for cubic graphs. The proofs are rigorous, results are profound, and particularly notable is the revelation of essential differences between acyclic b-chromatic number and b-chromatic number on cubic graphs. Although many open problems remain, this paper establishes a solid foundation for further research in this field. Recommended for researchers in graph theory and combinatorial optimization.