## Abstract

We introduce the circular chromatic number χ_{c} of a digraph and establish various basic results. They show that the coloring theory for digraphs is similar to the coloring theory for undirected graphs when independent sets of vertices are replaced by acyclic sets. Since the directed k-cycle has circular chromatic number k/(k - 1), for k ≥ 2, values of χ_{c} between 1 and 2 are possible. We show that in fact, χ_{c} takes on all rational values greater than 1. Furthermore, there exist digraphs of arbitrarlly large digirth and circular chromatic number. it is NP-complete to decide if a given digraph has χ_{c} at most 2.

Original language | English |
---|---|

Pages (from-to) | 227-240 |

Number of pages | 14 |

Journal | Journal of Graph Theory |

Volume | 46 |

Issue number | 3 |

DOIs | |

State | Published - Jul 2004 |

## Keywords

- Acyclic homomorphism
- Chromatic number
- Circular chromatic number
- Digirth
- Digraph
- NP-completeness