On the fg-coloring of graphs (Q2277478): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Nobuji Saito / rank | |||
Property / reviewed by | |||
Property / reviewed by: Ulrike Baumann / rank | |||
Property / author | |||
Property / author: Nobuji Saito / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Ulrike Baumann / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4091421 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Scheduling File Transfers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3853641 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A generalization of edge-coloring in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A better than “best possible” algorithm to edge color multigraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The NP-Completeness of Edge-Coloring / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the f-coloring of multigraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3693539 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Theorem on Coloring the Lines of a Network / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4517442 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some results in chromatic scheduling / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf02122697 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1486913849 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:47, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the fg-coloring of graphs |
scientific article |
Statements
On the fg-coloring of graphs (English)
0 references
1990
0 references
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.
0 references
fg-chromatic index
0 references
multigraphs
0 references
edge colourings
0 references
fg-colourings
0 references
polynomial time algorithm
0 references