کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650489 1342489 2007 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A local characterization of bounded clique-width for line graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A local characterization of bounded clique-width for line graphs
چکیده انگلیسی

It is shown that a line graph G   has clique-width at most 8k+48k+4 and NLC-width at most 4k+34k+3, if G contains a vertex whose non-neighbours induce a subgraph of clique-width k or NLC-width k in G, respectively. This relation implies that co-gem-free line graphs have clique-width at most 14 and NLC-width at most 7.It is also shown that in a line graph the neighbours of a vertex induce a subgraph of clique-width at most 4 and NLC-width at most 2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issue 6, 28 March 2007, Pages 756–759
نویسندگان
, ,