zbMATH — the first resource for mathematics

Vertex-coloring edge-weightings: towards the 1-2-3-conjecture. (English) Zbl 1209.05087
Summary: A weighting of the edges of a graph is called vertex-coloring if the weighted degrees of the vertices yield a proper coloring of the graph. In this paper we show that such a weighting is possible from the weight set \(\{1,2,3,4,5\}\) for all graphs not containing components with exactly 2 vertices.

05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
Full Text: DOI
[1] Addario-Berry, L.; Dalal, K.; McDiarmid, C.; Reed, B.A.; Thomason, A., Vertex-colouring edge-wheitings, Combinatorica, 27, 1-12, (2007) · Zbl 1127.05034
[2] Addario-Berry, L.; Dalal, K.; Reed, B.A., Degree constrained subgraphs, Discrete appl. math., 156, 1168-1174, (2008) · Zbl 1147.05055
[3] M. Kalkowski, A note on the 1,2-conjecture, submitted for publication
[4] Diestel, R., Graph theory, (2005), Springer-Verlag Heidelberg · Zbl 1074.05001
[5] Karoński, M.; Łuczak, T.; Thomason, A., Edge weights and vertex colours, J. combin. theory ser. B, 91, 151-157, (2004) · Zbl 1042.05045
[6] Wang, T.; Yu, Q., On vertex-coloring 13-edge-weighting, Front. math. China, 3, 1-7, (2008)
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.