Neighbor sum distinguishing total coloring of planar graphs without 4-cycles

Hongjie Song and Changqing Xu ()
Additional contact information
Hongjie Song: Hebei University of Technology
Changqing Xu: Hebei University of Technology

Journal of Combinatorial Optimization, 2017, vol. 34, issue 4, No 10, 1147-1158

Abstract: Abstract Let $$G=(V,E)$$ G = ( V , E ) be a graph and $$\phi : V\cup E\rightarrow \{1,2,\ldots ,k\}$$ ϕ : V ∪ E → { 1 , 2 , … , k } be a proper total coloring of G. Let f(v) denote the sum of the color on a vertex v and the colors on all the edges incident with v. The coloring $$\phi $$ ϕ is neighbor sum distinguishing if $$f(u)\ne f(v)$$ f ( u ) ≠ f ( v ) for each edge $$uv\in E(G)$$ u v ∈ E ( G ) . The smallest integer k in such a coloring of G is the neighbor sum distinguishing total chromatic number of G, denoted by $$\chi _{\Sigma }''(G)$$ χ Σ ′ ′ ( G ) . Pilśniak and Woźniak conjectured that $$\chi _{\Sigma }''(G)\le \Delta (G)+3$$ χ Σ ′ ′ ( G ) ≤ Δ ( G ) + 3 for any simple graph. By using the famous Combinatorial Nullstellensatz, we prove that $$\chi _{\Sigma }''(G)\le \max \{\Delta (G)+2, 10\}$$ χ Σ ′ ′ ( G ) ≤ max { Δ ( G ) + 2 , 10 } for planar graph G without 4-cycles. The bound $$\Delta (G)+2$$ Δ ( G ) + 2 is sharp if $$\Delta (G)\ge 8$$ Δ ( G ) ≥ 8 .

Keywords: Neighbor sum distinguishing total coloring; Combinatorial Nullstellensatz; Planar graph (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0137-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:34:y:2017:i:4:d:10.1007_s10878-017-0137-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0137-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().