On the fg-coloring of graphs
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.
- A better than “best possible” algorithm to edge color multigraphs
- A generalization of edge-coloring in graphs
- A Theorem on Coloring the Lines of a Network
- scientific article; zbMATH DE number 3918395 (Why is no real title available?)
- scientific article; zbMATH DE number 3654142 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1534644 (Why is no real title available?)
- On the f-coloring of multigraphs
- Scheduling File Transfers
- Some results in chromatic scheduling
- The NP-Completeness of Edge-Coloring
- Vertex colourings of multigraphs with forbiddances on edges
- Revisiting a theorem by Folkman on graph colouring
- \(F\)-WORM colorings: results for 2-connected graphs
- The method of coloring in graphs and its application
- On decomposing even regular multigraphs into small isomorphic trees
- Edge-coloring of multigraphs
- On coloring problems for two-season multigraphs
- On the f-coloring of multigraphs
- scientific article; zbMATH DE number 1555935 (Why is no real title available?)
- scientific article; zbMATH DE number 2097452 (Why is no real title available?)
- On the multigraph overfull conjecture
This page was built for publication: On the fg-coloring of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277478)
