Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650489 | Discrete Mathematics | 2007 | 4 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Frank Gurski, Egon Wanke,