Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654673 | European Journal of Combinatorics | 2009 | 10 Pages |
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
Jean-François Culus, Bertrand Jouve,