Abstract
An assignment of weights to the edges and the vertices of a graph is a vertex-coloring total weighting if adjacent vertices have different total weight sums. Of interest in this paper are vertex-coloring total weightings with weight set of cardinality two, a problem motivated by the conjecture that every graph has such a weighting using the weights 1 and 2. Here we prove the existence of such weightings for certain families of graphs using any two different real weights. A related problem where all vertices have unique weight sums is also discussed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Addario-Berry, L., Dalal, K., McDiarmid, C., Reed, B., Thomason, A.: Vertex-colouring edge-weightings. Combinatorica 27(1), 1–12 (2007)
Bac̆a, M., Jendrol, S., Miller, M., Ryan, : On irregular total labelings. J. Discret. Math. 307, 1378–1388 (2007)
Chartrand, G., Jacobson, M.S., Lehel, J., Oellermann, O.R., Ruiz, S., Saba, F.: Irregular networks. Congr. Numer. 64, 187–192 (1988)
Hulgan, J.: Concise proofs for adjacent vertex-distinguishing total colorings. Discret. Math. 309(8), 2548–2550 (2009). doi:10.1016/j.disc.2008.06.002. http://www.sciencedirect.com/science/article/pii/S0012365X08003865
Kalkowski, M.: A note on the 1,2-conjecture. Submitted
Kalkowski, M., Karoński, M., Pfender, F.: Vertex-coloring edge-weightings: Towards the 1-2-3-conjecture. Journal of Combinatorial Theory, Series B 100(3), 347–349 (2010). doi:10.1016/j.jctb.2009.06.002. http://www.sciencedirect.com/science/article/pii/S0095895609000586
Karoński, M., Łuczak, T., Thomason, A.: Edge weights and vertex colours. J. Comb. Theory Series B 91, 151–157 (2004)
Przybyło, J., Woźniak, M.: On a 1, 2 conjecture. Discret. Math. Theor. Comp. Sci. 12(1), 101–108 (2010)
Wang, H.: On the adjacent vertex-distinguishing total chromatic numbers of the graphs with \(\varDelta (G) = 3\). J. Comb. Optim. 14, 87–109 (2007)
Zhang, Z., Chen, X., Li, J., Yao, B., Lu, X., Wang, J.: On adjacent-vertex-distinguishing total coloring of graphs. Sci. China Series A Math. 48, 289–299 (2005)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hulgan, J., Lehel, J., Ozeki, K. et al. Vertex Coloring of Graphs by Total 2-Weightings. Graphs and Combinatorics 32, 2461–2471 (2016). https://doi.org/10.1007/s00373-016-1712-0
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-016-1712-0