Neighbor sum distinguishing total coloring of 2-degenerate graphs (Q2410029)

From MaRDI portal
Revision as of 13:19, 14 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Neighbor sum distinguishing total coloring of 2-degenerate graphs
scientific article

    Statements

    Neighbor sum distinguishing total coloring of 2-degenerate graphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    17 October 2017
    0 references
    A proper \(k\)-total coloring of a graph \(G\) is a mapping from \(V(G)\cup E(G)\) to \(\{1,2,\dots,k\}\) such that no two adjacent or incident elements in \(V(G)\cup E(G)\) receive the same color. Let \(f(v)\) denote the sum of the colors on the edges incident with \(v\) and the color on vertex \(v\). A proper \(k\)-total coloring of \(G\) is called neighbor sum distinguishing if \(f(u)\neq f(v)\) for each edge \(uv\in E(G)\). The smallest number \(k\) in the neighbor sum distinguishing \(k\)-total coloring of \(G\) is the neighbor sum distinguishing total chromatic number. \textit{M. Pilśniak} and \textit{M. Woźniak} [Graphs Comb. 31, No. 3, 771--782 (2015; Zbl 1312.05054)] conjectured that for any graph G the neighbor sum distinguishing total chromatic number is at most \(\Delta(G)+3\). In this paper, the authors confirm this conjecture for 2-degenerate graphs. Moreover, they improve this bound for graphs with maximum degree at least 5. They prove that if \(G\) is 2-degenerate with \(\Delta(G)\geq 5\) then the neighbor sum distinguishing total chromatic number is at most \(\Delta(G)+2\). The proof is based on the combinatorial Nullstellensatz. Recently, \textit{L. Ding} et al. [ibid. 33, No. 4, 885--900 (2017; Zbl 1371.05078)] proved that if \(G\) is not a forest and \(\Delta(G)\geq 4\) then the neighbor sum distinguishing total chromatic number of \(G\) is at most \(\Delta (G)+2\mathrm{col}(G)-1\), where col\((G)\) is the coloring number of \(G\), in particular, the neighbor sum distinguishing total chromatic number of 2-degenerate graph \(G\) with \(\Delta(G)\geq 4\) is at most \(\Delta(G)+3\).
    0 references
    neighbor sum distinguishing total coloring
    0 references
    2-degenerate graph
    0 references
    combinatorial Nullstellensatz
    0 references
    lexicographic order
    0 references

    Identifiers