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

چکیده انگلیسی
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
Journal: European Journal of Combinatorics - Volume 30, Issue 1, January 2009, Pages 43–52
نویسندگان
Jean-François Culus, Bertrand Jouve,