Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Journal of Combinato...arrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Journal of Combinatorial Optimization
Article . 2016 . Peer-reviewed
License: Springer TDM
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2017
Data sources: zbMATH Open
versions View all 2 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Neighbor sum distinguishing total coloring of 2-degenerate graphs

Authors: Yao, Jingjing; Yu, Xiaowei; Wang, Guanghui; Xu, Changqing;

Neighbor sum distinguishing total coloring of 2-degenerate graphs

Abstract

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\).

Related Organizations
Keywords

2-degenerate graph, Coloring of graphs and hypergraphs, neighbor sum distinguishing total coloring, lexicographic order, combinatorial Nullstellensatz

  • BIP!
    Impact byBIP!
    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).
    13
    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.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Top 10%
Powered by OpenAIRE graph
Found an issue? Give us feedback
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).
BIP!Citations provided by BIP!
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.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
13
Top 10%
Top 10%
Top 10%
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!