Vertex colouring edge partitions
| Autor: | Bruce Reed, Robert E. L. Aldred, Louigi Addario-Berry, Ketan Dalal |
|---|---|
| Rok vydání: | 2005 |
| Předmět: |
Discrete mathematics
Vertex (graph theory) Multiset Neighbourhood (graph theory) Multiplicity (mathematics) Edge cover Theoretical Computer Science Combinatorics Edge weights Computational Theory and Mathematics Degree-constrained subgraphs Saturation (graph theory) Discrete Mathematics and Combinatorics Partition (number theory) Vertex colours Edge space Mathematics |
| Zdroj: | Journal of Combinatorial Theory, Series B. 94:237-244 |
| ISSN: | 0095-8956 |
| DOI: | 10.1016/j.jctb.2005.01.001 |
| Popis: | A partition of the edges of a graph G into sets {S1,…,Sk} defines a multiset Xv for each vertex v where the multiplicity of i in Xv is the number of edges incident to v in Si. We show that the edges of every graph can be partitioned into 4 sets such that the resultant multisets give a vertex colouring of G. In other words, for every edge (u,v) of G, Xu≠Xv. Furthermore, if G has minimum degree at least 1000, then there is a partition of E(G) into 3 sets such that the corresponding multisets yield a vertex colouring. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect