×

The neighbor expanded sum distinguishing total colorings of cactus graphs. (Chinese. English summary) Zbl 1449.05117

Summary: Let \(G\) be a simple graph. A total \(k\)-coloring of \(G\) is an assignment of \(k\) colors \(1, 2, \dots, k\) to all vertices and edges of \(G\). For \(x \in V (G)\) and \(N (x) = \{y\in V (G)\mid xy\in E (G)\}\), the value \(w (x) = \sum\limits_{e \ni x}c (e)+ \sum\limits_{y \in N (x)}c (y)\) is called the expanded sum at \(x\), where \(c\) is a total \(k\)-coloring of \(G\). A total \(k\)-coloring \(c\) of \(G\) is called the neighbor expanded sum distinguishing (NESD for short) if \(w (x)\ne w (y)\), whenever \(xy \in E (G)\). The minimum number \(k\) of an NESD total \(k\)-coloring of \(G\) is called the neighbor expanded sum distinguishing total chromatic number of \(G\) and denoted by \(egndi_{\sum} (G)\). The neighbor expanded sum distinguishing total colorings of cactus graphs are discussed in this paper by using the method of mathematical induction. It is proved that the neighbor expanded sum distinguishing total chromatic number of any cactus graph is less than or equal to 2. This result illustrates that the NESDTC conjecture is true for cactus graphs.

MSC:

05C15 Coloring of graphs and hypergraphs
Full Text: DOI