کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903520 | 1632569 | 2017 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the (di)graphs with (directed) proper connection number two
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On the (di)graphs with (directed) proper connection number two On the (di)graphs with (directed) proper connection number two](/preview/png/8903520.png)
چکیده انگلیسی
A coloring of a graph G is properly connected if every two vertices of G are the ends of a properly colored path. We study the complexity of computing the proper connection number (minimum number of colors in a properly connected coloring) for edge and vertex colorings, in undirected and directed graphs, respectively. First we disprove some conjectures of Magnant et al. (2016) on characterizing the strong digraphs with proper arc connection number at most two. Then, we prove that deciding whether a given digraph has proper arc connection number at most two is NP-complete. We initiate the study of proper vertex connectivity in digraphs and we prove similar results as for the arc version. Finally, we present polynomial-time recognition algorithms for bounded-treewidth graphs and bipartite graphs with proper edge connection number at most two.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 237-242
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 237-242
نویسندگان
Guillaume Ducoffe, Ruxandra Marinescu-Ghemeci, Alexandru Popa,