Locally Irregular Total Colorings of Graphs

Abstract

A total graph is an ordered triple $(V_0,V_1,E)$, where $V_0,V_1$ are the sets of empty and full vertices, respectively, $V_0\cap V_1=\varnothing$, and the set of edges $E$ is a subset of \(\binom{V_0 \cup V_1}{2}\) $(E\cap (V_0\cup V_1)=\varnothing )$. A simple graph is a total graph in which all vertices are full. We say that a total graph $G$ is locally irregular if every two adjacent vertices have different total degrees, where by the total degree of a vertex $v$ in $G$ we mean the number of edges in $G$ that contain $v$ plus 1 if $v$ is full, or plus 0 if $v$ is empty. A total coloring of a graph $G$ whose colors induce locally irregular total subgraphs is called locally irregular total coloring, and the minimum number of colors required in such a coloring of $G$ is denoted by $\mathrm{tlir}(G)$. In 2015, Baudon, Bensmail, Przybyło, and Woźniak conjectured that $\mathrm{tlir}(G)\le 2$ for every graph $G$. In this paper, we prove this conjecture for cacti, subcubic graphs, and split graphs. We also provide a general upper bound for $\mathrm{tlir}(G)$ depending on the chromatic number of $G$, and a constant upper bound if $G$ is planar or outerplanar. In our proofs, we utilize special decompositions of graphs and the connection between acyclic vertex coloring and locally irregular total coloring.

arXiv comment14 pages, 7 figures