Abstract
We consider a proper coloring c of edges and vertices in a simple graph and the sum f(v) of colors of all the edges incident to v and the color of a vertex v. We say that a coloring c distinguishes adjacent vertices by sums, if every two adjacent vertices have different values of f. We conjecture that \({\Delta +\,3}\) colors suffice to distinguish adjacent vertices in any simple graph. In this paper we show that this holds for complete graphs, cycles, bipartite graphs, cubic graphs and graphs with maximum degree at most three.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bondy, J.A., Murty, U.S.R.: Graph theory with applications. Macmillan, London (1976)
Chen, X.: On the adjacent vertex distinguishing total coloring numbers of graphs with \({\Delta = 3}\). Discret. Math. 308–17, 4003–4007 (2008)
Flandrin, E., Marczyk, A., Przybyło, J., Saclé, J.F., Woźniak, M.: Neighbor sum distinguishing index. Graphs Comb. 29, 1329–1336 (2013)
Hulgan J.: Concise proofs for adjacent vertex-distinguishing total coloring. Discret. Math. 309, 2548–2550 (2009)
Kostochka A.V: The total coloring of a multigraph with maximal degree 4. Discret. Math. 17–2, 161–163 (1977)
Kostochka, A.V.: Upper bounds of chromatic functions of graph (in Russian). Ph.D. Thesis, Novosibirsk (1978)
Kalkowski M., Karoński M., Pfender F.: Vertex-coloring edge-weightings: towards 1-2-3-conjecture. J. Combin. Theory Ser. B 100–3, 347–349 (2010)
Karoński M., Łuczak T., Thomason A.: Edge veights and vertex colours. J. Combin. Theory Ser. B 91, 151–157 (2004)
Przybyło J., Woźniak M.: On a 1, 2 Conjecture. Discret. Math. Theor. Comput. Sci. 12, 101–108 (2010)
Rosenfeld M.: On the total coloring of certain graphs. Israel J. Math. 9–3, 396–402 (1970)
Zhang Z., Chen X., Li J., Yao B., Lu X., Wang J.: On adjacent-vertex-distinguishing total coloring of graphs. Sci. China Ser. A Math. 48–3, 289–299 (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
The research partially supported by the Polish Ministry of Science and Higher Education by a grant N201 1247/33.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
About this article
Cite this article
Pilśniak, M., Woźniak, M. On the Total-Neighbor-Distinguishing Index by Sums. Graphs and Combinatorics 31, 771–782 (2015). https://doi.org/10.1007/s00373-013-1399-4
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-013-1399-4
Keywords
- Total proper coloring
- Adjacent-vertex-distinguishing index
- Neighbor-sum-distinguishing coloring
- Total-neighbor-distinguishing index