Vertex coloring edge-weighted digraphs

Jørgen Bang-Jensen; Magnus M. Halldorsson

doi:10.1016/j.ipl.2015.05.007

Vertex coloring edge-weighted digraphs

Jørgen Bang-Jensen, Magnus M. Halldorsson

Department of Mathematics and Computer Science

Reykjavik University

Research output: Contribution to journal › Journal article › Research › peer-review

Abstract

A coloring of a digraph with non-negative edge weights is a partition of the vertex set into independent sets, where a set is independent if the weighted in-degree of each node within the set is less than 1. We give constructive optimal bounds on the chromatic number in terms of maximum in-degree and inductiveness of the graph.

Original language	English
Journal	Information Processing Letters
Volume	115
Issue number	10
Pages (from-to)	791-796
Number of pages	6
ISSN	0020-0190
DOIs	https://doi.org/10.1016/j.ipl.2015.05.007
Publication status	Published - 2015

Documents & Links

10.1016/j.ipl.2015.05.007

Cite this

@article{632e56a0f5ac4d9f8cfbbc68ff00d549,

title = "Vertex coloring edge-weighted digraphs",

abstract = "A coloring of a digraph with non-negative edge weights is a partition of the vertex set into independent sets, where a set is independent if the weighted in-degree of each node within the set is less than 1. We give constructive optimal bounds on the chromatic number in terms of maximum in-degree and inductiveness of the graph.",

author = "J{\o}rgen Bang-Jensen and Halldorsson, {Magnus M.}",

year = "2015",

doi = "10.1016/j.ipl.2015.05.007",

language = "English",

volume = "115",

pages = "791--796",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "10",

}

TY - JOUR

T1 - Vertex coloring edge-weighted digraphs

AU - Bang-Jensen, Jørgen

AU - Halldorsson, Magnus M.

PY - 2015

Y1 - 2015

N2 - A coloring of a digraph with non-negative edge weights is a partition of the vertex set into independent sets, where a set is independent if the weighted in-degree of each node within the set is less than 1. We give constructive optimal bounds on the chromatic number in terms of maximum in-degree and inductiveness of the graph.

AB - A coloring of a digraph with non-negative edge weights is a partition of the vertex set into independent sets, where a set is independent if the weighted in-degree of each node within the set is less than 1. We give constructive optimal bounds on the chromatic number in terms of maximum in-degree and inductiveness of the graph.

U2 - 10.1016/j.ipl.2015.05.007

DO - 10.1016/j.ipl.2015.05.007

M3 - Journal article

SN - 0020-0190

VL - 115

SP - 791

EP - 796

JO - Information Processing Letters

JF - Information Processing Letters

IS - 10

ER -

Vertex coloring edge-weighted digraphs

Abstract

Documents & Links

Fingerprint

Cite this