کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648114 | 1342393 | 2012 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Locally identifying colourings for graphs with given maximum degree
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Locally identifying colourings for graphs with given maximum degree Locally identifying colourings for graphs with given maximum degree](/preview/png/4648114.png)
چکیده انگلیسی
A proper vertex-colouring of a graph GG is said to be locally identifying if for any pair uu, vv of adjacent vertices with distinct closed neighbourhoods, the sets of colours in the closed neighbourhoods of uu and vv are different. We show that any graph GG has a locally identifying colouring with 2Δ2−3Δ+32Δ2−3Δ+3 colours, where ΔΔ is the maximum degree of GG, answering in a positive way a question asked by Esperet et al. We also provide similar results for locally identifying colourings which have the property that the colours in the neighbourhood of each vertex are all different and apply our method to the class of chordal graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 10, 28 May 2012, Pages 1832–1837
Journal: Discrete Mathematics - Volume 312, Issue 10, 28 May 2012, Pages 1832–1837
نویسندگان
Florent Foucaud, Iiro Honkala, Tero Laihonen, Aline Parreau, Guillem Perarnau,