کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649486 1342458 2010 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Anticoloring and separation of graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Anticoloring and separation of graphs
چکیده انگلیسی

An anticoloring of a graph is a coloring of some of the vertices, such that no two adjacent vertices are colored in distinct colors. The anticoloring problem seeks, roughly speaking, such colorings with many vertices colored in each color. We deal with the anticoloring problem for planar graphs and, using Lipton and Tarjan’s separation algorithm, provide an algorithm with some bound on the error. We also show that, to solve the anticoloring problem for general graphs, it suffices to solve it for connected graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issue 3, 6 February 2010, Pages 390–399
نویسندگان
, , ,