| Article ID: | iaor201527239 |
| Volume: | 115 |
| Issue: | 10 |
| Start Page Number: | 791 |
| End Page Number: | 796 |
| Publication Date: | Oct 2015 |
| Journal: | Information Processing Letters |
| Authors: | Bang-Jensen Jrgen, Halldrsson Magns M |
| Keywords: | digraphs, graph coloring |
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.