Polynomial time complexity of edge colouring graphs with bounded colour classes

Romeo Rizzi; David Cariolaro

doi:10.1007/s00453-013-9746-7

Polynomial time complexity of edge colouring graphs with bounded colour classes

Romeo Rizzi, David Cariolaro^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

We show that the following fundamental edge-colouring problem can be solved in polynomial time for any given constant B: given a simple graph G, find an edge-colouring of G where each colour is assigned to at most B edges and which, subject to this condition, has the fewest number of colour classes.

Original language	English
Pages (from-to)	494-500
Number of pages	7
Journal	Algorithmica
Volume	69
Issue number	3
DOIs	https://doi.org/10.1007/s00453-013-9746-7
Publication status	Published - Jul 2014
Externally published	Yes

Keywords

Chromatic index
Edge-colouring
Equalized edge-colouring

Access to Document

10.1007/s00453-013-9746-7

Cite this

@article{7692e9a0dfe246d082e6c5d45f90f258,

title = "Polynomial time complexity of edge colouring graphs with bounded colour classes",

abstract = "We show that the following fundamental edge-colouring problem can be solved in polynomial time for any given constant B: given a simple graph G, find an edge-colouring of G where each colour is assigned to at most B edges and which, subject to this condition, has the fewest number of colour classes.",

keywords = "Chromatic index, Edge-colouring, Equalized edge-colouring",

author = "Romeo Rizzi and David Cariolaro",

year = "2014",

month = jul,

doi = "10.1007/s00453-013-9746-7",

language = "English",

volume = "69",

pages = "494--500",

journal = "Algorithmica",

issn = "0178-4617",

number = "3",

}

TY - JOUR

T1 - Polynomial time complexity of edge colouring graphs with bounded colour classes

AU - Rizzi, Romeo

AU - Cariolaro, David

PY - 2014/7

Y1 - 2014/7

N2 - We show that the following fundamental edge-colouring problem can be solved in polynomial time for any given constant B: given a simple graph G, find an edge-colouring of G where each colour is assigned to at most B edges and which, subject to this condition, has the fewest number of colour classes.

AB - We show that the following fundamental edge-colouring problem can be solved in polynomial time for any given constant B: given a simple graph G, find an edge-colouring of G where each colour is assigned to at most B edges and which, subject to this condition, has the fewest number of colour classes.

KW - Chromatic index

KW - Edge-colouring

KW - Equalized edge-colouring

UR - https://www.scopus.com/pages/publications/84901853437

U2 - 10.1007/s00453-013-9746-7

DO - 10.1007/s00453-013-9746-7

M3 - Article

AN - SCOPUS:84901853437

SN - 0178-4617

VL - 69

SP - 494

EP - 500

JO - Algorithmica

JF - Algorithmica

IS - 3

ER -

Polynomial time complexity of edge colouring graphs with bounded colour classes

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this