×

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.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. Addario-Berry, K. Dalal, C. McDiarmid, B. Reed, A. Thomason, Vertex colouring edge weights, 2004, submitted for publication.; 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, (Barlotti, A.; etal., Combinatorics, vol. 90 (1992), Elsevier Science Publishers: Elsevier Science Publishers New York), 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) · Zbl 0869.05033
[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: 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.