zbMATH — the first resource for mathematics

Vertex colouring edge partitions. (English) Zbl 1074.05031
Suppose that the edges of a graph are assigned labels from a \(k\)-set, or equivilently, the edges are partitioned into \(k\) parts. Each vertex \(v\) has an associated multiset \(X_v\) consisting of the labels on its incident edges. The partition is a (proper) vertex coloring if for every edge \(uv\), \(X_u \neq X_v\).
The authors show that the edges of any graph (except those containing a component isomorphic to \(K_2\)) have a partition into four parts such that the associated multisets form a vertex coloring. Moreover, if the minimum degree is at least 1000, then the edges can be partitioned into three parts yielding a vertex coloring.
This paper is well written and the result is interesting.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] L. Addario-Berry, K. Dalal, C. McDiarmid, B. Reed, A. Thomason, Vertex colouring edge weights, 2004, submitted for publication. · Zbl 1127.05034
[2] Aigner, M.; Triesch, E.; Tuza, Zs., Irregular assignments and vertex-distinguishing edge-colorings of graphs, (), 1-9 · Zbl 0769.05035
[3] Burris, A.C.; Schelp, R.H., Vertex-distinguishing proper edge colourings, J. graph theory, 26, 2, 73-82, (1997) · Zbl 0886.05068
[4] Balister, P.N.; Riordan, O.M.; Schelp, R.H., Vertex-distinguishing edge colorings of graphs, J. graph theory, 42, 2, 95-109, (2003) · Zbl 1008.05067
[5] Edwards, K., The harmonious chromatic number of bounded degree graphs, J. London math. soc., 255, 3, 435-447, (1997)
[6] Karoński, M.; Luczak, T.; Thomason, A., Edge weights and vertex colours, J. combin. theory B, 91, 151-157, (2004) · Zbl 1042.05045
[7] Lovasz, L.; Plummer, M.D., Matching theory, (1986), Academic Press New York · Zbl 0618.05001
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.