Acyclic total coloring of graphs with large girths
A proper total coloring of a graph \( G \) such that there are at least 4 colors on those vertices and edges incident with a cycle of \( G \), is called an acyclic total coloring. The acyclic total chromatic number of \( G \), denoted by \( \chi^{''}_{a}(G) \), is the smallest number of colors such that \( G \) has an acyclic total coloring. In this article, we prove that for any graph \( G \) with \( \Delta(G)=\Delta \) which satisfies \( \chi^{''}(G)\leq A \) for some constant \( A \), and for any integer \( r \), \( 1\leq r \leq 2\Delta \), there exists a constant \( c>0 \) such that if \( g(G)\geq\frac{c\Delta}{r}\log\frac{\Delta^{2}}{r} \), then \( \chi^{''}_{a}(G)\leq A+r \).
Authors
- Wenyao Song
- Xiaoya Li (ORCID: https://orcid.org/0000-0001-8660-454X)
- Lianying Miao
Publication Details
- Journal
- Ars Combinatoria
- Published
- 2025-03-22
- DOI
- https://doi.org/10.61091/ars162-01
- Primary Topic
- Graph Labeling and Dimension Problems
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Natural Science Foundation of China