zbMATH — the first resource for mathematics

On the total-neighbor-distinguishing index by sums. (English) Zbl 1312.05054
Summary: 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.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Bondy, J.A., Murty, U.S.R.: Graph theory with applications. Macmillan, London (1976) · Zbl 1226.05083
[2] Chen, X.: On the adjacent vertex distinguishing total coloring numbers of graphs with \({Δ = 3}\). Discret. Math. 308-17, 4003-4007 (2008) · Zbl 1203.05052
[3] Flandrin, E., Marczyk, A., Przybyło, J., Saclé, J.F., Woźniak, M.: Neighbor sum distinguishing index. Graphs Comb. 29, 1329-1336 (2013) · Zbl 1272.05047
[4] Hulgan, J., Concise proofs for adjacent vertex-distinguishing total coloring, Discret. Math., 309, 2548-2550, (2009) · Zbl 1221.05143
[5] Kostochka, A.V, The total coloring of a multigraph with maximal degree 4, Discret. Math., 17-2, 161-163, (1977) · Zbl 0411.05038
[6] Kostochka, A.V.: Upper bounds of chromatic functions of graph (in Russian). Ph.D. Thesis, Novosibirsk (1978) · Zbl 1221.05143
[7] 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) · Zbl 1209.05087
[8] Karoński, M.; Łuczak, T.; Thomason, A., Edge veights and vertex colours, J. Combin. Theory Ser. B, 91, 151-157, (2004) · Zbl 1042.05045
[9] Przybyło, J.; Woźniak, M., On a 1, 2 conjecture, Discret. Math. Theor. Comput. Sci., 12, 101-108, (2010) · Zbl 1250.05093
[10] Rosenfeld, M., On the total coloring of certain graphs, Israel J. Math., 9-3, 396-402, (1970) · Zbl 0211.56604
[11] 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) · Zbl 1080.05036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.