
doi: 10.1007/bf02122697
In this paper multigraphs \(G=(V,E)\) without loops are under consideration. They are assigned edge colourings satisfying the following two conditions: (i) Each colour appears at each vertex v no more than f(v) times. (ii) Each colour appears at each set of multiple edges joining vertices v and w no more than g(vw) times. These edge colourings are called fg-colourings. \(q^*_{fg}(G)\) denotes the minimum number of colours needed to fg-colour a multigraph G. Various upper bounds on \(g^*_{fg}(G)\) are given. The main result is \[ q^*_{fg}(G)\leq \max_{vw\in G}\lceil d(v)/f(v)+p(vw)/g(vw)\rceil. \] A polynomial time algorithm to fg-colour a given multigraph using \(\leq 2q^*_{fg}(G)\) colours is presented.
Coloring of graphs and hypergraphs, fg-colourings, multigraphs, polynomial time algorithm, edge colourings, fg-chromatic index
Coloring of graphs and hypergraphs, fg-colourings, multigraphs, polynomial time algorithm, edge colourings, fg-chromatic index
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 7 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
