Article ID Journal Published Year Pages File Type
4650489 Discrete Mathematics 2007 4 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,