Asymptotically optimal neighbor sum distinguishing total colorings of graphs

preprint2016arXivOpen access

Abstract

Given a proper total kk-coloring c:V(G)∪E(G)→{1,2,…,k}c:V(G)\cup E(G)\to\{1,2,\ldots,k\} of a graph GG, we define the value of a vertex vv to be c(v)+∑uv∈E(G)c(uv)c(v) + \sum_{uv \in E(G)} c(uv). The smallest integer kk such that GG has a proper total kk-coloring whose values form a proper coloring is the neighbor sum distinguishing total chromatic number of GG, χ"Σ(G)χ"_Σ(G). Pilśniak and Woźniak (2013) conjectured that χ"Σ(G)≤Δ(G)+3χ"_Σ(G)\leq Δ(G)+3 for any simple graph with maximum degree Δ(G)Δ(G). In this paper, we prove this bound to be asymptotically correct by showing that χ"Σ(G)≤Δ(G)(1+o(1))χ"_Σ(G)\leq Δ(G)(1+o(1)). The main idea of our argument relies on Przybyło's proof (2014) regarding neighbor sum distinguishing edge-colorings.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.