Convex circuit free coloration of an oriented graph
Résumé
We introduce the \textit{convex circuit-free coloration} and \textit{convex circuit-free chromatic number} $\overrightarrow{\chi_a}(\overrightarrow{G})$ of an oriented graph $\overrightarrow{G}$ and establish various basic results. We show that the problem of deciding if an oriented graph verifies $\chi_a( \overrightarrow{G}) \leq k$ is NP-complete if $k \geq 3$ and polynomial if $k \leq 2$. We exhibit an algorithm which finds the optimal convex circuit-free coloration for tournaments, and characterize the tournaments that are \textit{vertex-critical} for the convex circuit-free coloration.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...