On acyclic b-chromatic number of cubic graphs

Marcin Anholcer, Sylwia Cichacz, Iztok Peterin · 2025

Read On acyclic b-chromatic number of cubic graphs by Marcin Anholcer, Sylwia Cichacz, Iztok Peterin (2025) 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-2511-01532.txt.

Introduction

Marcin Anholcer, Sylwia Cichacz, and Iztok Peterin study a graph coloring parameter for cubic graphs, networks where every vertex has exactly three neighbors. The coloring is acyclic: adjacent vertices differ, and any two color classes together form a forest, with no cycles. A coloring is maximal in their sense when no vertex can be recolored to drop a color while staying acyclic.

The acyclic b-chromatic number counts the most colors such a stuck coloring can use, framed formally through a recoloring relation and its transitive closure. Pinning down this number for cubic graphs is the paper's aim, a step in understanding how local recoloring rules limit global colorings of regular networks.

Catalog record

CREATORMarcin Anholcer, Sylwia Cichacz, Iztok Peterin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-01532

Browse the full library · About the Tower of Babel

Full text

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

On acyclic b-chromatic number of cubic graphs Marcin Anholcer, Sylwia Cichacz, Iztok Peterin Abstract Let G G be a graph. An acyclic k k -coloring of G G is a map c : V ⁡ ( G ) → { 1 , … , k } c:V(G)\rightarrow\{1,\dots,k\} such that c ⁡ ( u ) ≠ c ⁡ ( v ) c(u)\neq c(v) for any u ​ v ∈ E ⁡ ( G ) uv\in E(G) and the subgraph induced by the vertices of any two colors i , j ∈ { 1 , … , k } i,j\in\{1,\dots,k\} is a forest. If every vertex v v of a color class V i V_{i} misses a color ℓ v ∈ { 1 , … , k } \ell_{v}\in\{1,\dots,k\} in its closed neighborhood, then every v ∈ V i v\in V_{i} can be recolored with ℓ v \ell_{v} and we obtain a ( k − 1 ) (k-1) -coloring of G G . If a new coloring c ′ c^{\prime} is also acyclic, then such a recoloring is an acyclic recoloring step and c ′ c^{\prime} is in relation ⊲ a \triangleleft_{a} with c c . The acyclic b-chromatic number A b ​ ( G ) A_{b}(G) of G G is the maximum number of colors in an acyclic coloring where no acyclic recoloring step is possible. Equivalently, it is the maximum number of colors in a minimum element of the transitive closure of ⊲ a \triangleleft_{a} . In this paper, we consider A b ​ ( G ) A_{b}(G) of cubic graphs. Keywords : acyclic b-chromatic number; acyclic coloring; b-coloring; cubic graph AMS subject classification (2020) : 05C15 1 Introduction A possible heuristic approach to properly color a graph is the one that starts with a trivial proper coloring, i.e., a coloring in which every vertex has its own color from \{1,\dots,|V(G)|\} . Then, given a color class V_{i} of color i , a vertex v\in V_{i} is called a b-vertex if it has all the colors other than i in its neighborhood. If there is no b-vertex in V_{i} , then for every v\in V_{i} there is at least one color \ell_{v} other than i not used in the neighbors of v , so each v\in V_{i} can be recolored with \ell_{v} to obtain a new proper coloring of G using all colors except i . This removal of a color class is referred to as the recoloring step. Recoloring steps are performed until each color class has at least one b-vertex. The number of colors in the resulting coloring is an upper bound for \chi(G) . Its highest possible value is called the b-chromatic number \varphi(G) of G . It was introduced by Irving and Manlove in 1999 [ 17 ] , who have shown, among others, that determining the b-chromatic number of a graph is an NP-hard problem. As demonstrated by Kratochvíl, Tuza, and Voigt [ 21 ] , the problem is still NP-hard for connected bipartite graphs. The most interesting results of the research on b-chromatic numbers for the present work are d -regular graphs. The main question for them is whether equality \varphi(G)=d+1 holds or not. It was proved in [ 21 ] that this holds for all graphs on at least d^{4} vertices. This was later improved to 2d^{3} vertices by Cabello and Jakovac [ 6 ] by the use of Hall’s Marriage Theorem and later to 2d^{3}+2d-2d^{2} by El Sahili et al. [ 11 ] . In particular, this means that there exists only a finite number of d -regular graphs with \varphi(G)<d+1 and for d=3 there exists only four such graphs as shown by Jakovac and Klavžar [ 18 ] . This was later tested for small graphs and d\in\{3,4,5,6,7\} by a hybrid evolutionary algorithm by Fister et al. [ 13 ] . The most famous conjecture on the topic was posted by El Sahili and Kouider [ 10 ] and later reformulated by Blidia et al. [ 4 ] (excluding the Petersen graph) and states that for every d -regular graph with girth at least five, except the Petersen graph, we have \varphi(G)=d+1 . The latest improvement on it is by Detlaff et al. [ 9 ] . We refer the reader to the survey [ 19 ] for additional topics related to b-coloring. In the current paper, we consider an analogous problem, where the base is the acyclic coloring. In this case, one assumes not only the absence of monochromatic edges but also that every two color classes induce a forest. The minimum number of colors in such a coloring of graph G is its acyclic chromatic number , denoted by A(G) . Obviously, A(G)\geq\chi(G) since every acyclic coloring is also a coloring of G . This kind of coloring was introduced by Grünbaum [ 15 ] , who proved that A(G)\leq 9 for any planar graph G and conjectured that A(G)\leq 5 in this case, which was finally proved by Borodin [ 5 ] . A conjecture attributed to Erdös (see [ 20 , p.89] ), stated that A(G)=o(\Delta^{2}) , where \Delta=\Delta(G) . It was proved by Alon, McDiarmid and Reed [ 1 ] , who showed that A(G)\leq\lceil 50\Delta^{4/3}\rceil . This result was recently improved to A(G)\leq\frac{3}{2}\Delta^{4/3}+O(\Delta) by Gonçalves, Montassier and Pinlou [ 14 ] . On the other hand, in [ 1 ] the existence of graphs satisfying A(G)=\Omega(\Delta^{4/3}/(\log\Delta)^{1/3}) has been proved. Other important and interesting results on acyclic colorings can be found in particular in the papers [ 22 ] ( A(G) of subdivisions of graphs and NP-completeness results), [ 2 ] , where, in particular, the authors disproved a conjecture of Borodin (see [ 20 , p.70] ) about the equality A(G)=\chi(G) for graphs embeddable on all surfaces other than a plane and [ 12 , 16 , 24 ] (graphs with bounded degrees). Motivated in particular by considerations about b-colorings, the authors introduced in [ 3 ] acyclic b-colorings, i.e., the colorings produced in the same way as b-colorings, with the extra condition that the recoloring step (called acyclic recoloring step) must produce an acyclic coloring. In particular, it was demonstrated that the problem is well-defined, i.e., for each finite graph G , every acyclic coloring of G can be obtained by starting with a trivial coloring and performing a finite number of acyclic recoloring steps. The value of the respective graph invariant, the acyclic b-chromatic number A_{b}(G) , has been presented for several special graph families. Beside that, it was shown that the difference between A_{b}(G) and the acyclic chromatic number A(G) , acyclic m -degree m_{a}(G) (see [ 3 ] for detailed definition), maximum degree \Delta(G) and \varphi(G) , respectively, can be arbitrary big. We continue to develop the topic by analyzing the cubic graphs in this work. We believe that it is an important step on the way to obtaining more general results for regular graphs. The paper is organized as follows. In the next section, we present basic notations and concepts; among others, we recall the necessary terms and results from [ 3 ] . In Section 3 we show that all cubic graphs, besides one exception, have acyclic b-chromatic number

Read the complete text