
Summary: A proper total coloring of a graph \(G\) is an assignment of colors to the vertices and edges of \(G\) (together called the elements of \(G\)) such that neighbored elements -- two adjacent vertices or two adjacent edges or a vertex and an incident edge -- are colored differently. The total chromatic number \(\chi^{\prime\prime}(G)\) of \(G\) is defined as the minimum number of colors in a proper total coloring of \(G\). In this paper, we study the stability of the total chromatic number of a graph with respect to two operations, namely removing edges and subdividing edges, which leads to the following two invariants. (i) The total chromatic edge stability number or \(\chi^{\prime\prime}\)-edge stability number \(es_{\chi^{\prime\prime}}(G)\) is the minimum number of edges of \(G\) whose removal results in a graph \(H\subseteq G\) with \(\chi^{\prime\prime}(H)\neq \chi^{\prime\prime}(G)\) or with \(E(H) = \emptyset \). (ii) The total chromatic subdivision number or \(\chi^{\prime\prime}\)-subdivision number \(sd_{\chi^{\prime\prime}}(G)\) is the minimum number of edges of \(G\) whose subdivision results in a graph \(H\subseteq G\) with \(\chi^{\prime\prime}(H)\neq \chi^{\prime\prime}(G)\) or with \(E(H) = \emptyset\). We prove general lower and upper bounds for \(es_{\chi^{\prime\prime}}(G)\). Moreover, we determine \(es_{\chi^{\prime\prime}}(G)\) and \(sd_{\chi^{\prime\prime}}(G)\) for some classes of graphs.
Coloring of graphs and hypergraphs, total chromatic number, total coloring, total chromatic subdivision number, QA1-939, Mathematics, total chromatic edge stability number
Coloring of graphs and hypergraphs, total chromatic number, total coloring, total chromatic subdivision number, QA1-939, Mathematics, total chromatic edge stability number
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
