کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648053 | 1342391 | 2011 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On minimal triangle-free graphs with prescribed kk-defective chromatic number
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On minimal triangle-free graphs with prescribed kk-defective chromatic number On minimal triangle-free graphs with prescribed kk-defective chromatic number](/preview/png/4648053.png)
چکیده انگلیسی
A graph GG is (m,k)(m,k)-colourable if its vertices can be coloured with mm colours such that the maximum degree of any subgraph induced on vertices receiving the same colour is at most kk. The k-defective chromatic number χk(G)χk(G) is the least positive integer mm for which GG is (m,k)(m,k)-colourable. Let f(m,k)f(m,k) be the smallest order of a triangle-free graph such that χk(G)=mχk(G)=m. In this paper we study the problem of determining f(m,k)f(m,k). We show that f(3,2)=13f(3,2)=13 and characterize the corresponding minimal graphs. We present a lower bound for f(m,k)f(m,k) for all m≥3m≥3 and also an upper bound for f(3,k)f(3,k).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issue 13, 6 July 2011, Pages 1119–1127
Journal: Discrete Mathematics - Volume 311, Issue 13, 6 July 2011, Pages 1119–1127
نویسندگان
Nirmala Achuthan, N.R. Achuthan, M. Simanihuruk,