کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4654673 1632824 2009 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Convex circuit-free coloration of an oriented graph
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Convex circuit-free coloration of an oriented graph
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 30, Issue 1, January 2009, Pages 43–52
نویسندگان
, ,