Article ID Journal Published Year Pages File Type
4654673 European Journal of Combinatorics 2009 10 Pages PDF
Abstract

We introduce the Convex Circuit-Free coloration and Convex Circuit-Free chromatic number  χa⃗(G⃗) of an oriented graph G⃗ and establish various basic results. We show that the problem of deciding if an oriented graph verifies χa(G⃗)≤k is NP-complete if k≥3k≥3, and polynomial if k≤2k≤2. We introduce an algorithm which finds the optimal convex circuit-free coloration for tournaments, and characterize the tournaments that are vertex-critical for the convex circuit-free coloration.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,