# The AVD-total chromatic number of fullerene molecular graphs

Mariana da Cruz, Diana Sasaki, Mauro Nigro, Celina M. H. de Figueiredo

► To cite this version:

Mariana da Cruz, Diana Sasaki, Mauro Nigro, Celina M. H. de Figueiredo. The AVD-total chromatic number of fullerene molecular graphs. 2026. hal-04850028v3

HAL Id: hal-04850028

https://hal.science/hal-04850028v3

Preprint submitted on 8 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The AVD-total chromatic number of fullerene molecular graphs

Mariana da Cruz<fnref n="1" />* Celina de Figueiredo<fnref n="1" /> Mauro Nigro<fnref n="2" /> Diana Sasaki<fnref n="2" />

revisions 26th Dec. 2024, 4th Nov. 2025; accepted 28th Dec. 2025.

An AVD-k-total coloring of a simple graph G is a mapping $\pi : V(G) \cup E(G) \rightarrow \{1, \dots, k\}$, with $k \ge 1$ such that: for each pair of adjacent or incident elements $x, y \in V(G) \cup E(G)$, $\pi(x) \neq \pi(y)$; and for each pair of adjacent vertices $x, y \in V(G)$, sets $\{\pi(x)\} \cup \{\pi(xv) \mid xv \in E(G)\}$ and $\{\pi(y)\} \cup \{yv \in E(G)\}$ and $v \in V(G)$} are distinct. The AVD-total chromatic number, denoted by $\chi_a''(G)$ is the smallest k for which G admits an AVD-k-total-coloring. In 2010, Hulgan conjectured that any graph G with maximum vertex degree 3 has $\chi_a''(G) \le 5$. As positive evidence, we prove that several molecular graphs known as fullerene graphs have AVD-total chromatic number equal to 5.

**Keywords:** Fullerenes, Nanotubes, AVD-total chromatic number.

## 1 Introduction

The discovery of the Buckminsterfullerene in 1985 by Curl et al. (1985) marked the birth of fullerene chemistry and nanotechnology. The discovered molecule $C_{60}$ is comprised of 60 carbon atoms, was pronounced in 1991 “Molecule of the year” by the *Science* journal, and was awarded the Nobel Prize in Chemistry in 1996. The experimental work was paralleled by theoretical investigations, applying the methods of graph theory to the mathematical models of fullerene molecules called fullerene graphs, searching for invariants that will correlate with their stability as a chemical compound in order to predict their physical and chemical properties. Graph theory invariants that have been considered as stability predictors are: bipartite edge frustration, independence number, saturation number, number of perfect matchings, and chromatic number. Theoretical aspects of the chemistry and physics of fullerenes are discussed in *An Atlas of Fullerenes* by Fowler and Manolopoulos (1995).

Let $G = (V, E)$ be a simple connected graph and $\Delta(G)$ be the maximum vertex degree of $G$, for definitions and notation in Graph Theory we refer to Bondy and Murty (2008). A *k*-total coloring of *G* is an assignment of *k* colors to the vertices and edges of *G* so that adjacent or incident elements have different colors. The *total chromatic number* of *G*, denoted by $\chi''(G)$, is the smallest *k* for which *G* has a *k*-total coloring, and so satisfies $\chi''(G) \ge \Delta(G) + 1$. The Total Coloring Conjecture (TCC) states that the

<footnote n="1">¹ PESC, Federal University of Rio de Janeiro (UFRJ), Rio de Janeiro, Brazil</footnote>

<footnote n="2">² Rio de Janeiro State University (UERJ), Rio de Janeiro, Brazil.</footnote>

<footnote>*Corresponding author</footnote>
total chromatic number of any graph $G$ is at most $\Delta(G)+2$ (Behzad (1965); Vizing (1964)). Graphs with $\chi''(G) = \Delta(G)+1$ are called *Type 1*, and graphs with $\chi''(G) = \Delta(G)+2$ are called *Type 2*. McDiarmid and Sánchez-Arroyo (1994) determined that the total chromatic number is an NP-complete problem even for cubic graphs, that are graphs with all vertices with the same vertex degree 3.

Let $\pi$ be a $k$-total coloring of $G$ and let $C_{\pi}(u) := \{\pi(u)\} \cup \{\pi(uv) \mid uv \in E(G), v \in V(G)\}$ be the set of colors that occur in a vertex $u \in V(G)$. If it is clear from the context that $\pi$ is a $k$-total coloring of $G$, then $C_{\pi}(u)$ is written simply as $C(u)$. Two vertices $u$ and $v$ are distinguishable when $C(u) \neq C(v)$. If this property is true for every pair of adjacent vertices, then $\pi$ is a *Adjacent-Vertex-Distinguishing-k-Total-Coloring*, or simply *AVD-k-total coloring*. The *AVD-total chromatic number* of $G$, denoted by $\chi_a''(G)$, is the smallest $k$ for which $G$ admits an *AVD-k-total coloring*.

In 2005, Chen et al. (2005) introduced the AVD-total coloring problem, determined the AVD-total chromatic number for families of graphs and noted that all of them admit an AVD-total coloring with at most $\Delta(G)+3$ colors, proposing the AVD-total Coloring Conjecture (AVD-TCC).

**Conjecture 1** (Chen et al. (2005)). If $G$ is a simple graph, then $\chi_a''(G) \le \Delta(G)+3$.

If the AVD-TCC holds, then we can classify any graph according the AVD-total chromatic number. If $\chi_a''(G) = \Delta(G)+1$, then $G$ is called *AVD-Type 1*. If $\chi_a''(G) = \Delta(G)+2$, then $G$ is called *AVD-Type 2*. If $\chi_a''(G) = \Delta(G)+3$, then $G$ is called *AVD-Type 3*. Clearly, any *AVD-Type 1* graph is *Type 1* graph. However, the converse is not true, for instance the complete graph $K_n$ with $n$ odd is *Type 1* and *AVD-Type 3* (see Yap (1996); Chen et al. (2005)).

Since the proposal of the AVD-TCC, in the past twenty years, several studies have been conducted. In 2008, Chen (2008) proved the AVD-TCC to graphs with maximum vertex degree 3. In the same year, Chen and Zhang (2008) determined the AVD-total chromatic number of some graph classes with maximum vertex degree at least 6. In 2009, Chen and Guo (2009) determined the AVD-total chromatic number of the hypercubes $Q_n$. In the same year, Hulgan (2009) presented concise proofs of the AVD-total chromatic number of cycles and of complete graphs, and provided an adjacent vertex distinguishing total coloring with 6 colors for graphs with maximum degree 3. Furthermore, Hulgan conjectured that the obtained upper bound for the AVD-total chromatic number of graphs with maximum degree 3 was not sharp.

**Conjecture 2** (Hulgan (2009, 2010)). If $G$ is a simple graph with $\Delta(G) = 3$, then $\chi_a''(G) \le 5$.

Since then, recent studies have been conducted involving some other graph classes in order to investigate Conjecture 1, such as equipartite graphs, split graphs, corona graphs and 4-regular graphs (see Campos et al. (2015); Papaioannou and Raftopoulou (2014); Panda and Verma (2024); Fu et al. (2022)). For the purpose of investigating Conjecture 2, we highlight the work carried out by Campos et al. (2017) in 2017, who proved that Conjecture 2 holds for graphs with maximum degree 3, where vertices with maximum vertex degree are not adjacent, and for infinite families of bridgeless cubic graphs known as snarks.

Conjecture 2 inspires us to investigate the AVD-total coloring problem considering cubic planar graphs with only pentagonal and hexagonal faces that model chemical structures: the smallest fullerene graphs and two infinite families of fullerene graphs: the fullerene nanodiscs and nanotubes.
## 2 Fullerene molecular graphs

Molecular graphs of fullerenes are called fullerene graphs. Fullerene graphs are cubic, 3-connected, planar graphs with only pentagonal and hexagonal faces. It follows from the Euler's Polyhedron Formula that any fullerene graph has exactly 12 pentagonal faces.

A survey on fullerene graphs is presented in Andova et al. (2016). Various graph invariants are of interest to chemists, such as independent sets, matchings and colorings (see Ashrafi et al. (2018)). It is known that fullerene graphs with $n$ vertices exist for all even $n \ge 24$ and for $n = 20$ (see Grünbaum and Motzkin (1963)). Usually in chemistry the fullerene molecule with $n$ atoms is denoted by $C_n$ (see Andova et al. (2016)). Although the number of pentagonal faces is negligible compared to the number of hexagonal faces, their layout is crucial for the shape of the corresponding fullerene molecule. As the number of vertices grows, the number of non isomorphic fullerenes increases as well. The three smallest fullerenes $C_{20}$ (dodecahedron), $C_{24}$ and $C_{26}$ are unique, $C_{28}$ has two isomers and $C_{30}$ has three isomers (see Fowler and Manolopoulos (1995)).

Petersen's theorem states that every cubic graph with no bridges has a perfect matching (see Petersen (1891)). A perfect matching is, in chemistry, called a Kekulé structure (see Došlić (1998); Zhang and Zhang (2002)). Consider a fullerene graph $G$. We say that $G$ has a circular embedding if $G$ admits a perfect matching $M$ whose removal leaves a disjoint union of cycles $G \setminus M$, denoted by $C^1, C^2, \dots, C^p$ and called auxiliary cycles such that each edge $vu \in M$ satisfies that $v \in C^i$ and $u \in C^{i-1}$ with $i \in \{2, 3, \dots, p-1, p\}$. In addition, we say that $v$ is a connection vertex in relation to cycle $C^i$ and it is denoted by $v^i$. By definition of connection vertex, the outermost auxiliary cycle $C^1$ does not have connection vertices and all vertices of the innermost cycle are connection vertices. We denote the set of connection vertices in relation to cycle $C^i$ by $X^i$. Since $M$ provides an edge covering with $\frac{n}{2}$ edges, the number of connection vertices in $G$ is $\frac{n}{2}$. We say that the outermost face defined by cycle $C^1$ is the first and outermost layer of $G$, the subgraph induced by vertices of cycles $C^i \cup C^{i-1}$ is defined as layer $i$, with $i \in \{2, 3, \dots, p-1, p\}$, and the innermost face defined by cycle $C^p$ is the last and innermost layer $p+1$. The edges belonging to the perfect matching $M$ are called radial edges. In this paper, we will focus on three infinite families of fullerene graphs that admit such circular embedding.

### 2.1 Nanodiscs

The nanodisc $D_r$, $r \ge 2$, is a collection of $\lfloor \frac{r}{2} \rfloor$ fullerene graphs with circular embedding containing $2r+1$ layers. The key property is that the 12 pentagonal faces lie in the layer $r$, called central layer. The distance between the innermost (outermost) layer and the central layer is given by the radius parameter $r \ge 2$. Figure 1 shows the smallest nanodiscs $D_2$ and $D_3$, where the 12 pentagonal faces are shaded in the central layer and the $\frac{n}{2}$ connection vertices are highlighted in dark gray.

The face sequence $\{1, 6, 12, 18, \dots, 6(r-1), 6r, 6(r-1), \dots, 18, 12, 6, 1\}$ gives the amount of faces on each layer and the cycle sequence $\{C_6, C_{18}, \dots, C_{12r-18}, C_{12r-6}, C_{12r-6}, C_{12r-18}, \dots, C_{18}, C_6\}$ gives the sizes of the auxiliary cycles that define the layers of $D_r$.

Nicodemos and Stehlík (2017) proved that there are $\lfloor \frac{r}{2} \rfloor$ non-isomorphic fullerene nanodiscs $D_r$ by considering a new parameter $t$, $0 \le t \le r-2$, which gives the arrangement in the central layer of the balanced hexagons (hexagonal faces with three vertices in each auxiliary cycle) among two consecutive pentagons. Pentagons partitioned in the same way (that is, the pentagons contain two vertices in the same auxiliary cycle) are homogeneously distributed in the central layer and there are $r-1$ faces between two of them, one of which is a pentagon. Each pentagon defines a chain of unbalanced hexagons (that is,
the hexagons contain four vertices in the same auxiliary cycle) as we highlighted in Figure 2 for each non-isomorphic nanodisc of radius 7. Thus, $D_{r,t}$, $0 \le t < \lfloor \frac{r}{2} \rfloor$, is the nanodisc of radius $r$ such that for two consecutive pentagons partitioned in the same way we have, in clockwise, $t$ balanced hexagons, a pentagon partitioned in a distinct way, and $r - 2 - t$ balanced hexagons.

<figure><img src="image_2.png" /><figcaption>Fig. 1: The smallest nanodiscs $D_2$ and $D_3$. The 12 pentagonal faces are shaded in the central layer, and the $\frac{n}{2}$ connection vertices are highlighted in dark gray, so that each radial edge is incident to a distinct connection vertex.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2: The three non-isomorphic of fullerene nanodiscs $D_7$. A pentagon defines a shaded chain of unbalanced hexagons.</figcaption></figure>

For fullerene nanodiscs $D_r$, considering the circular embedding containing $2r+1$ layers, we explicit the cardinality of the set of connection vertices $X^i$ in relation to auxiliary cycle $C^i$ recursively by equation (1). Observe that by definition $X^1$ is empty. Figure 1 shows the connection vertices of the smallest nanodisc $D_2$ and $D_3$.

$$|X^{i+1}| = \begin{cases} 6, & \text{if } i = 1, \\ 12i - 6 - |X^i|, & \text{if } i \in \{2, 3, \dots, r+1\}, \\ 12(2r+1-i) - 6 - |X^i|, & \text{if } i \in \{r+2, \dots, 2r\}. \end{cases} \quad (1)$$
## 2.2 Nanotubes

There is an important class of fullerene graphs with tubular shapes, that includes the Buckminsterfullerene, called *nanotubical graphs* or simply *nanotubes*. From a mathematical perspective, they are not well-defined, since one can find (infinitely) many caps for an $(a, b)$-nanotube Brinkmann et al. (2002), where $(a, b)$ is a Goldberg vector which is used to obtain these graph classes. The Buckminsterfullerene is the smallest nanotube of type (5, 5). In addition, they have a cylindrical shape, obtained from an infinite hexagonal grid with the two ends capped by a subgraph containing six pentagonal faces and possibly some hexagonal faces. Let $k$ be a positive integer such that $k \ge 4$. For our purposes, we shall focus on two infinite families mathematically well defined: the (0, 5)-nanotubes and (0, 6)-nanotubes.

<figure><img src="image_4.png" /><figcaption>Fig. 3: In the first row, the dodecahedron, a degenerate (0, 5)-nanotube followed by the smallest (0, 5)-nanotubes $\mathcal{N}(C_5, 4)$ and $\mathcal{N}(C_5, 5)$; in the second row, the fullerene $C_{24}$, a degenerate (0, 6)-nanotube followed by the smallest (0, 6)-nanotubes $\mathcal{N}(C_6, 4)$ and $\mathcal{N}(C_6, 5)$. The connection vertices of each graph are highlighted in dark gray.</figcaption></figure>

### The (0, 5)-nanotubes and the (0, 6)-nanotubes

Similarly to nanodiscs, the (0, 5)-nanotubes and (0, 6)-nanotubes, denoted by $\mathcal{N}(C_5, k)$ and $\mathcal{N}(C_6, k)$, respectively with $k \ge 4$, are fullerene graphs with circular embedding containing $k + 1$ layers, but the 12 pentagonal faces are not in the same layer.

The parameters $C_5$ and $C_6$ refer to the shape of the outermost and innermost faces. These cycles define the structure of the hexagonal grid of the nanotubes, and the parameter $k \ge 4$ specifies the number of auxiliary cycles in each nanotube. The face sequences $\{1, 5, \dots, 5, 1\}$ and $\{1, 6, \dots, 6, 1\}$ provide the number of faces on each layer of the graphs $\mathcal{N}(C_5, k)$ and $\mathcal{N}(C_6, k)$, respectively.

The auxiliary cycle sequences $\{C_5, C_{10}, \dots, C_{10}, C_5\}$ and $\{C_6, C_{12}, \dots, C_{12}, C_6\}$ provide the sizes of the auxiliary cycles that define the layers of $\mathcal{N}(C_5, k)$ and $\mathcal{N}(C_6, k)$, respectively. Note that if we consider the construction for $k = 3$, then we obtain $C_{20}$ and $C_{24}$ as degenerate cases of the (0, 5)-nanotube and (0, 6)-nanotube, respectively.

We remark that $\mathcal{N}(C_5, k)$ and $\mathcal{N}(C_6, k)$ for $k \ge 4$ are ways to define the (0, 5)-nanotube and (0, 6)-nanotube, where (0, 5) and (0, 6) are the Goldberg vectors used to obtain these graph classes. Also, note
that $\mathcal{N}(C_6, 5)$ is a nanotubical graph with 48 vertices and it is an isomer of the fullerene nanodisc $\mathcal{D}_2$.

Note that, by the construction of nanotubes, for $1 < i \le k$ the cardinality of the set of connection vertices $X^i$ in $\mathcal{N}(C_5, k)$ is 5, and in $\mathcal{N}(C_6, k)$ is 6. Figure 3 shows the connection vertices of some nanotubical graphs.

## 3 Results

To prove the results of this paper, we will make use of two well known properties, stated as Propositions 1 and 2. In a total coloring, the set of colors that occur in a vertex of maximum vertex degree has size $\Delta(G) + 1$, and the first property says that to ensure the adjacent-vertex-distinguishing condition in a regular graph we need at least $\Delta(G) + 2$ colors, or more generally in a graph with two adjacent vertices of maximum degree we need at least $\Delta(G) + 2$ colors.

**Proposition 1** (Chen et al. (2005)). Let $G$ be a simple graph. If $G$ has two adjacent vertices of maximum degree, then $\chi_a''(G) \ge \Delta(G) + 2$.

Second, the total chromatic number of cycle graphs $C_n$, well-known in the literature due to Yap Yap (1996), is the foundation of our findings, since the sizes of the auxiliary cycles in a nanodisc are divisible by 3.

**Proposition 2** (Yap (1996)). Let $G$ be the cycle graph $C_n$. Then

$$ \chi''(G) = \begin{cases} 3, & \text{if } n \equiv 0 \mod 3; \\ 4, & \text{otherwise.} \end{cases} $$

In the context of the AVD-total coloring of our target fullerene graph classes, the auxiliary cycles and connection vertices play a crucial role in the main results. We can label the auxiliary cycles of each graph class defined in Section 2 as follows.

For fullerene nanodiscs $\mathcal{D}_r$, starting of the outermost cycle, the auxiliary cycles are labeled as follows.

$$ C^i := \begin{cases} C_{12i-6}, & i \in \{1, 2, \dots, r\} \\ C_{12(2r+1-i)-6}, & i \in \{r+1, r+2, \dots, 2r\}. \end{cases} $$

For fullerene nanotubes, starting from the outermost cycle, the auxiliary cycles of nanotubes $\mathcal{N}(C_5, k)$, can be labeled as $C^1 := C_5$, $C^i := C_{10}$, for $i \in \{2, \dots, k-1\}$, and $C^k := C_5$. For $\mathcal{N}(C_6, k)$ we label the auxiliary cycles as $C^1 := C_6$, $C^i := C_{12}$, for $i \in \{2, \dots, k-1\}$, and $C^k := C_6$.

**Theorem 1.** The fullerene nanodiscs $\mathcal{D}_r$, $r \ge 2$ are AVD-Type 2.

**Proof:** We ask the reader to refer to Figures 4 and 5 to understand the coloring procedure defined below. Let $G := \mathcal{D}_r$ be the fullerene nanodisc such that $r \ge 2$. Let $X$ be the union of the sets $X^i$ for all $i \in \{2, \dots, 2r\}$ and $R$ be the set of radial edges of $E(G)$. We label the elements of $X$ and $R$ as follows. For each cycle $C^i$ with $i \in \{2, \dots, 2r\}$, arbitrarily choose a connection vertex $v_1^i$ and then label the remaining connection vertices $v_s^i$ of $C^i$ in clockwise, with $s \in \{2, \dots, |X^i|\}$. Since each $v_s^i$ is incident to precisely one radial edge, we label this radial edge as $e_s^i$. Since $G$ has two adjacent vertices of maximum degree, from Proposition 1, $\chi_a''(G) \ge 5$. In order to prove that $\chi_a''(G) = 5$, we depict an AVD-5-total coloring $\pi: V(G) \cup E(G) \to \{1, 2, 3, 4, 5\}$ of $G$ in two steps, as follows:
1. First, the color assignment to the vertices in $X$ is defined by $\pi : X \to \{4, 5\}$ where $\pi(v_s^i) = 4$, if $s$ is odd and $\pi(v_s^i) = 5$, if $s$ even; and the color assignment to the edges in $R$ is defined by $\pi : R \to \{4, 5\}$ with $\pi(e_s^i) = 4$, if $\pi(v_s^i) = 5$ and $\pi(e_s^i) = 5$, if $\pi(v_s^i) = 4$. Note that the number of connection vertices in the same auxiliary cycle is even.

2. Second, we will assign colors to the elements in $(V(G) \cup E(G)) \setminus (X \cup R)$. Consider the cycle $C^1$, which is the outer cycle containing six vertices. By Proposition 2, there exists a 3-total coloring $\pi : V(C^1) \cup E(C^1) \to \{1, 2, 3\}$ for $C^1$. For each cycle $C^i$, where $i \in \{2, \dots, 2r\}$, observe that the size of $C^i$ is divisible by 3 and the set of its connection vertices $X^i$ is divisible by 3, as described in Equation 1, which implies that the number of remaining elements of $C^i$ to be colored is divisible by 3. We sequentially color these elements of cycle $C^i$ with three colors 1, 2, 3.

In order to see that $\pi$ is a 5-total coloring of $G$, first we consider possible color conflicts between adjacent edges. Note that the edges of each auxiliary cycle $C^i$ are properly colored with three colors 1, 2, 3. It remains to check color conflicts among these edges and the radial edges $e_s^i \in R$, with $i \in \{2, \dots, 2r\}$, $s \in \{1, \dots, |X_i|\}$ which connect the cycles $C^i$. By definition of $\pi$, radial edges are colored alternately with colors 4 and 5, which implies that there is no color conflict between adjacent edges of $G$. Next, we consider possible color conflicts between adjacent vertices. Every pair of adjacent vertices that are not connection vertices are contained in the same auxiliary cycle $C^i$, and so are properly colored with colors 1, 2, 3, and every connection vertex $v_s^i \in X$ is colored with color 4 or 5. Thus, every pair of adjacent vertices $u, v_s^i$, where $u \in V(G) \setminus X$ and $v_s^i \in X$, have no color conflict. Finally, we consider possible color conflicts between vertices and incident edges. By the definition of $\pi$, the colors 4, 5 are alternated according to parity between the connection vertices and the incident radial edges, and vertices and incident edges contained in the same auxiliary cycle $C^i$ are properly colored with colors 1, 2, 3. Therefore we conclude that $\pi$ is a 5-total coloring of $G$.

Finally, in order to prove that $\pi$ is an AVD-5-total coloring of $G$, we have to consider three possible cases for each pair of adjacent vertices $u, v \in V(G)$ and their neighborhoods:

a. Precisely one vertex is a connection vertex (see Figure 4a.) Suppose that, without loss of generality, that $v^i := v$ is a connection vertex in relation to cycle $C^i$, $i \in \{2, \dots, 2r\}$. Thus, both colors 4 and 5 occur in $v^i$. Since $u$ is not a connection vertex, precisely one among colors 4 and 5 occur in $u$. Thus, $C(v^i) \neq C(u)$, and so $v^i$ and $u$ are distinguishable.

b. Neither $u$ nor $v$ are connection vertices (see Figure 4b). Vertices $u$ and $v$ are consecutive in the same auxiliary cycle $C^i$. Since $G$ is cubic, there is a radial edge $e_s^i$ incident to $u$ and a radial edge $e_{s+1}^i$ incident to $v$. By the definition of $\pi$, the colors 4 and 5 are assigned alternately to the radial edges. Therefore, color 4 occurs in precisely one of vertices $u$ and $v$, as does color 5. Hence, $C(u) \neq C(v)$, and so $u$ and $v$ are distinguishable.

c. Both vertices $u$ and $v$ are connection vertices (see Figure 4c). Vertices $u$ and $v$ are consecutive in the same auxiliary cycle $C^i$, and may be labeled $v_s^i$ and $v_{s+1}^i$, respectively. The definition of $\pi$ ensures that the edges of cycle $C^i$ incident to the vertices $v_s^i$ and $v_{s+1}^i$ are colored with colors 1, 2, 3, following a circular order, with one of these colors being assigned to the edge $v_s^i v_{s+1}^i$. Two colors remain for the other edges incident to $v_s^i$ and $v_{s+1}^i$ in $C^i$. Note that one of these two colors is assigned to the edge in $C^i$ incident only to $v_s^i$, and the other color is assigned to the edge in $C^i$ incident only to $v_{s+1}^i$. Therefore, $C(v_s^i) \neq C(v_{s+1}^i)$, and so $v_s^i$ and $v_{s+1}^i$ are distinguishable.
<figure><img src="image_5.png" /><figcaption>Fig. 4: Three possible cases for each pair of adjacent vertices in a nanodisc $D_r$: (a) precisely one vertex is a connection vertex, (b) neither vertex is a connection vertex, (c) both vertices are connection vertices.</figcaption></figure>

Having verified the three cases, the result follows.

□

Figure 5a illustrates the uncolored fullerene nanodisc $D_2$, with its labeled connection vertices and radial edges, and Figure 5b exhibits its AVD-5-total coloring, following the procedure described above.

<figure><img src="image_6.png" /><figcaption>Fig. 5: (a) The fullerene nanodisc $D_2$ with its connection vertices and radial edges labeled; (b) An AVD-5-total coloring for $D_2$ obtained by the procedure described in Theorem 1.</figcaption></figure>

As a corollary of Theorem 1, we additionally obtain an AVD-5-total coloring for (0, 6)-nanotubes. See Figure 6.
**Corollary 1.** Let $k$ be a positive integer such that $k \ge 3$. The nanotube $\mathcal{N}(C_6, k)$ is AVD-Type 2.

<figure><img src="image_7.png" /><figcaption>Fig. 6: (a) The fullerene nanotube $\mathcal{N}(C_6, 4)$ with its connection vertices and radial edges labeled; (b) An AVD-5-total coloring for $\mathcal{N}(C_6, 4)$ obtained by the procedure described in Theorem 1.</figcaption></figure>

**Theorem 2.** Let $k$ be a positive integer such that $k \ge 3$. The nanotube $\mathcal{N}(C_5, k)$ is AVD-Type 2.

**Proof:** We ask the reader to refer to Figures 7 and 8 to understand the coloring procedure defined below. Let $G := \mathcal{N}(C_5, k)$ with $k \ge 3$ be the fullerene (0,5)-nanotube. Let $X$ be the union of the sets $X^i$ for all $i \in \{1, \dots, k\}$ and $R$ be the set of radial edges of $E(G)$. For $s \in \{1, 2, 3, 4, 5\}$, considering indices modulo 5, we label the vertices of the cycle $C^1$ as $u_s^1$ such that $u_s^1 u_{s+1}^1 \in E(G)$; the adjacent connection vertex of $u_s^1$ as $v_s^2$; and for each $i \in \{2, \dots, k-1\}$, we label the adjacent vertex to $v_s^i$ and $v_{s+1}^i$ as $u_s^i$ and we label the adjacent connection vertex of $u_s^i$ as $v_s^{i+1}$. Since each $v_s^i$ is incident to precisely one radial edge, we label this radial edge as $e_s^i$. Since $G$ has two adjacent vertices of maximum degree, from Proposition 1, $\chi''(G) \ge 5$. In order to prove that $\chi''_a(G) = 5$, we depict an AVD-5-total coloring $\pi: V(G) \cup E(G) \to \{1, 2, 3, 4, 5\}$ of $G$ in two steps, as follows:

1. First, the color assignment of the connection vertices in $X \setminus \{v_4^k, v_5^k\}$ is defined by $\pi: X \setminus \{v_4^k, v_5^k\} \to \{4, 5\}$, where $\pi(v_s^i) = 4$, if $s$ is odd and $\pi(v_s^i) = 5$, if $s$ is even; and the color assignment to the edges in $R$ is defined by $\pi: R \setminus \{e_4^k, e_5^k\} \to \{4, 5\}$ with $\pi(e_s^i) = 4$, if $\pi(v_s^i) = 5$ and $\pi(e_s^i) = 5$, if $\pi(v_s^i) = 4$. Finally, we will assign $\pi(v_4^k) = 3$, $\pi(v_5^k) = 1$ and $\pi(e_4^k) = \pi(e_5^k) = 5$.

2. Second, we will assign colors to the elements in $(V(G) \cup E(G)) \setminus (X \cup R)$. Consider the outermost cycle $C^1$. Starting from $u_1^1$ we alternate the colors 1, 2 and 3 to the elements of $C^1$, except for the edge $u_1^1 u_5^1$ where we assign the color 4. For each cycle $C^i$, where $i \in \{2, 3, \dots, k-1\}$, observe that the size of $C^i$ is 10. Then, the number of elements of $C^i$ is 20. Since the number of connection
vertices of $C^i$ is 5, the number of remaining elements is 15, which is divisible by 3, which implies that the number of remaining elements of $C^i$ to be colored is divisible by 3. We sequentially color these elements of cycle $C^i$ starting from $v_1^i u_1^i$ with three colors 1, 2 and 3. Finally, we assign colors of edges of cycle $C^k$, which is the inner cycle containing five vertices. Observe that from step 1, $\pi(v_5^k) = 1$ and that all vertices of cycle $C^k$ are connection vertices and have been colored in step 1 as $\pi(v_5^k) = 1$, $\pi(v_1^k) = 4$, $\pi(v_2^k) = 5$, $\pi(v_3^k) = 4$, $\pi(v_4^k) = 3$. So it remains to color the five edges of $C^k$. We sequentially color the edges of $C^k \setminus \{v_4^k v_5^k\}$ starting $v_5^k v_1^k$ with color $\pi(v_5^k v_1^k) = 2$ and then using the three colors 2, 3 and 1 as $\pi(v_5^k v_1^k) = 2$, $\pi(v_1^k v_2^k) = 3$, $\pi(v_2^k v_3^k) = 1$, $\pi(v_3^k v_4^k) = 2$. Finally, we assign color 4 to the edge $v_4^k v_5^k$.

<figure><img src="image_8.png" /><figcaption>Fig. 7: (a) The dodecahedron, a fullerene graph with 20 vertices; (b) An AVD-5-total coloring for $C_{20}$.</figcaption></figure>

In order to see that $\pi$ is a 5-total coloring of $G$, note that by step 2, the auxiliary cycle $C^1$ has its 10 elements properly colored with colors 1, 2, 3 and 4. Next, note that each $C^i$, $i \in \{2, \dots, k-1\}$ has 20 elements, its five connection vertices are colored with colors 4 and 5, and the remaining 15 elements are sequentially colored with colors 1, 2 and 3. Finally, the auxiliary cycle $C^k$ has its 10 elements properly colored with colors 1, 2, 3, 4 and 5. To check that there is no color conflict between remaining adjacent edges, we check possible color conflicts between the edges belonging to auxiliary cycles $C^i$, $i \in \{1, \dots, k\}$ and the radial edges in $R$. By definition of $\pi$, note that $\pi(u_5^1 u_1^1) = \pi(v_4^k v_5^k) = 4$, the radial edges that are adjacent to these edges are colored with color 5, and the edges in $R \setminus \{u_1^1 v_1^2, u_5^1 v_5^2, u_4^{k-1} v_4^k, u_5^{k-1} v_5^k\}$ are colored alternately with colors 4 and 5.

Next, to check that there is no color conflict between remaining adjacent vertices, we note that every vertex $u_s^i$ in $C^i$, $i \in \{2, \dots, k-1\}$ that is not a connection vertex has all of its neighbors as connection vertices. Observe that since there are three elements between two connection vertices $v_s^i$ and $v_{s+1}^i$ in $C^i$,
the vertices $u_s^i$ have the same color 2. Thus, every pair of adjacent vertices have no color conflict. Finally, we consider possible color conflicts between remaining vertices and incident edges. By definition of $\pi$, the colors 4, 5 are alternated between the connection vertices and their incident radial edges, except $v_4^k$ that is colored 3 and $v_5^k$ that is colored 1 and their incident radial edges that are colored 5. Therefore we conclude that $\pi$ is a 5-total coloring of $G$.

<figure><img src="image_9.png" /><figcaption>Fig. 8: Three possible cases for each pair of adjacent vertices in a nanotube $N(C_5, k)$: (a) precisely one vertex is a connection vertex, (b) neither vertex is a connection vertex, (c) both vertices are connection vertices.</figcaption></figure>

In order to prove that $\pi$ is an AVD-5-total coloring of $G$, we have to consider three possible cases for each pair of adjacent vertices:

a. Precisely one vertex is a connection vertex (see Figure 8a.) Let $v_s^i$ be a connection vertex in relation to cycle $C^i$, $i \in \{2, \dots, k\}$. Thus, both colors 4 and 5 occur in $v_s^i$. Let $u$ be a non-connection vertex adjacent to $v_s^i$. Suppose that $u$ is not $u_5^1$ nor $u_1^1$. Then $u \in \{u_{s-1}^i, u_s^i, u_s^{i-1}\}$.

Observe that $u_5^1$ and $u_1^1$ are the only non-connection vertices such that both colors 4 and 5 belong to $C(u_1^1)$ and $C(u_5^1)$. Since $u$ is not a connection vertex and $u$ is not $u_1^1$ nor $u_5^1$, precisely one among colors 4 and 5 occurs in $u$. Thus, $C(u) \neq C(v_s^i)$ and so $u$ and $v_s^i$ are distinguishable. Else, suppose that $u_s^{i-1}$ is either $u_1^1$ or $u_5^1$. Since $3 \notin C(u_1^1)$ and $3 \in C(v_1^2)$, $C(u_1^1) \neq C(v_1^2)$. Similarly, since $1 \notin C(u_5^1)$ and $1 \in C(v_5^2)$, $C(u_5^1) \neq C(v_5^2)$.

b. None of the vertices is a connection vertex (see Figure 8b.) Let $u$ and $u'$ be two adjacent non-connection vertices. Observe that both vertices belong to the cycle $C^1$. Suppose that $u = u_1^1$ and $u' = u_5^1$, then $\{4, 5\}$ is a subset of $C(u)$ and $C(u')$, but color 1 $\in C(u)$ and color 1 $\notin C(u')$. Else, suppose that $u = u_s^1$ and $u' = u_{s+1}^1$ for $s \in \{1, 2, 3, 4\}$. Observe that if color 4 $\in C(u)$, then color 4 $\notin C(u')$ or if 5 $\in C(u)$, then 5 $\notin C(u')$. Therefore, $C(u) \neq C(u')$.
c. Both vertices are connection vertices (see Figure 8c.) Let $v$ and $v'$ be two adjacent connection vertices. Observe that both vertices belong to the cycle $C^k$. Furthermore, $\{4, 5\}$ is a subset of $C(v)$ and $C(v')$. Since color $i \notin C(v_i^k)$ and color $i \in C(v_{i+1}^k)$ for $i \in \{1, 2, 3\}$, $C(v_i^k) \neq C(v_{i+1}^k)$. Since color 1 does not belong to $C(v_4^k)$ and $C(v_1^k)$, but color 1 $\in C(v_5^k)$, we have $C(v_5^k) \neq C(v_4^k)$ and $C(v_5^k) \neq C(v_1^k)$.

Thus, $\pi$ is an AVD-5-total coloring of $G$. $\square$

<figure><img src="image_10.png" /></figure>

**3.1 Final Remarks**

In this paper, we verify Conjecture 2 for fullerene nanodiscs and for (0, 5) and (0, 6)-nanotubes. All these fullerene graphs admit a circular embedding. However, we prove in the remark below that some fullerene graphs do not admit a circular embedding. The coloring strategy employed for all three infinite families of fullerene graphs leads us to state that graphs admitting a circular embedding might provide classes of graphs where Conjecture 2 holds. Furthermore, from Proposition 3, it is known that fullerene graphs admit an exponential number of perfect matchings, which motivates us to propose the following question.

**Question.** Is there a polynomial-time algorithm to determine if an arbitrary fullerene graph admits a circular embedding?

**Proposition 3** (Kardoš et al. (2009)). Let $G$ be a fullerene graph with $n$ vertices that has no non-trivial cyclic 5-edge-cut. The number of perfect matchings of $G$ is at least $2^{\frac{n-380}{61}}$.

<figure><img src="image_11.png" /><figcaption>Fig. 9: An AVD-5-total coloring of $C_{26}$ and $C_{26+12}$, respectively.</figcaption></figure>

**Remark.** The fullerene $C_{26}$ does not admit a circular embedding.

**Proof:** Suppose that by contradiction $C_{26}$ admits a circular embedding. So, there is a perfect matching $M$ whose removal leaves a disjoint union of cycles such that each edge $vu \in M$ satisfies that $v \in C^i$ and $u \in C^{i-1}$ with $i \in \{2, 3, \dots, p-1, p\}$, and every edge $uv \in M$ is a radial edge. Since any fullerene graph has only pentagonal and hexagonal faces, the size of $C^1$ is either 5 or 6. Since the faces in the
layer defined by auxiliary cycles $C^1$ and $C^2$ are pentagons or hexagons, there are at least 10 vertices in $C^2$, there are at least 5 radial edges joining $C^1$ and $C^2$, and so there are at least 5 radial edges joining the auxiliary cycles $C^2$ and $C^3$. Since $|M| = 13$, there are at most 3 radial edges joining the auxiliary cycles $C^3$ and $C^4$, there is a face which is not pentagonal nor hexagonal, a contradiction. □

Similarly, the fullerene $C_{28}$ does not admit a circular embedding. Figure 9 presents AVD-5-total colorings for $C_{26}$ and $C_{26+12}$ that are inspired by the colorings obtained through a circular embedding.

## Acknowledgment

This research was supported by CAPES Finance Code 001, FAPERJ (grant no. E-26/010.002674/2019, E-26/201.360/2021, E-26/204.143/2024), and CNPq (grant no. 404613/2023-3, 305356/2021-6, 313797/2020-0).

## References

V. Andova and R. Škrekovski. Diameter of fullerene graphs with full icosahedral symmetry. *MATCH Commun. Math. Comput. Chem.*, 70:205–220, 2013.

V. Andova, F. Kardős, and R. Škrekovski. Mathematical aspects of fullerenes. *Ars Math. Contemp.*, 11: 353–379, 2016.

A. Ashrafi, S. Bakaein, M. Tavakoli, and O. Ori. Coloring of fullerenes. *Fuller. Nanotub. Carbon Nanos- tructures*, 26:705–708, 2018.

M. Behzad. *Graphs and their chromatic numbers*. PhD thesis, Michigan State University, 1965.

J. Bondy and U. Murty. *Graph Theory*. Springer, New York, 2008.

G. Brinkmann, U. v. Nathusius, and A. H. R. Palser. A constructive enumeration of nanotube caps. *Discrete Appl. Math.*, 116:55–71, 2002.

C. N. Campos, A. G. Luiz, and C. P. de Mello. Avd-total-colouring of complete equipartite graphs. *Discrete Appl. Math.*, 184:189–195, 2015.

C. N. Campos, A. G. Luiz, and C. P. de Mello. Avd-total-chromatic number of some families of graphs with $\Delta(G) = 3$. *Discrete Appl. Math.*, 217:628–638, 2017.

M. Chen and X. Guo. Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes. *Inf. Process. Lett.*, 109:599–602, 2009.

X. Chen. On the adjacent vertex distinguishing total coloring numbers of graphs with $\Delta = 3$. *Discrete Math.*, 308:4003–4007, 2008.

X. Chen and Z. Zhang. Avdtc numbers of generalized halin graphs with maximum degree at least 6. *Acta Math. Appl. Sin. Engl. Ser.*, 24:55–58, 2008.

X. Chen, J. Li, and Z. Zhang. On adjacent-vertex-distinguishing total coloring of graphs. *Sci. China Ser. A-Math.*, 48:289–299, 2005.
R. F. Curl, J. R. Heath, H. W. Kroto, S. C. O'Brien, and R. E. Smalley. C60: Buckminsterfullerene. *Nature*, 318:162, 1985.

T. Došlić. On lower bounds of number of perfect matchings in fullerene graphs. *J. Math. Chem.*, 24: 359–364, 1998.

P. Fowler and D. Manolopoulos. *An Atlas of Fullerenes*. Oxford University Press, 1995.

H. Fu, B. S. Panda, and S. Verma. Adjacent vertex distinguishing total coloring in split graphs. *Discrete Math.*, 345:113061, 2022.

B. Grünbaum and T. S. Motzkin. The number of hexagons and the simplicity of geodesics on certain polyhedra. *Canad. J. Math.*, 15:744–751, 1963.

J. Hulgan. Concise proofs for adjacent vertex-distinguishing total colorings. *Discrete Math.*, 309:2548–2550, 2009.

J. Hulgan. *Graph Coloring with Constraints*. PhD thesis, University of Memphis, Electronic Theses and Dissertations, available at https://digitalcommons.memphis.edu/etd/21, 2010.

F. Kardoš, D. Kráľ, J. Miškuf, and J.-S. Sereni. Fullerene graphs have exponentially many perfect matchings. *J. Math. Chem.*, 46:443–447, 2009.

C. J. H. McDiarmid and A. Sánchez-Arroyo. Total colouring regular bipartite graphs is NP-hard. *Discrete Math.*, 124:155–162, 1994.

D. Nicodemos and M. Stehlík. Fullerene graphs of small diameter. *MATCH Commun. Math. Comput. Chem.*, 77:725–728, 2017.

S. Panda and S. Verma. Adjacent vertex distinguishing total coloring of the corona product of graphs. *Discuss. Math. Graph Theory*, 44:317, 2024.

A. Papaioannou and C. Raftopoulou. On the AVDTC of 4-regular graphs. *Discrete Math.*, 330:20–40, 2014.

J. Petersen. Die Theorie der regulären graphs. *Acta Math.*, 15:193–200, 1891.

V. Vizing. On an estimate of the chromatic class of a p-graph. *Metody Diskret. Analiz.*, pages 25–30, 1964.

H. P. Yap. *Total colourings of graphs*. Springer, 1996.

H. Zhang and F. Zhang. New lower bound on the number of perfect matchings in fullerene graphs. *J. Math. Chem.*, 30:343–347, 2002.