In this paper we give a finite forbidden subgraph characterization of graphs defined by NLC-width 2-expressions, by NLCT-width 2-expressions, or by linear NLC-width 2-expressions that have tree-width 1. The NLC-width of a graph is defined by a composition mechanism for vertex-labeled graphs [11]. The operations are the unions of two graphs in which edges can be inserted specified by a set of label pairs, and the relabeling of vertices. The NLC-width of a graph G is the minimum number of labels needed to define it. A similar concept which is called clique-width was defined by Courcelle and Olariu [2]. NLC-width and clique-width bounded graphs are particularly interesting from an algorithmic point of view, since a lot of NP-complete graph problems can be solved in polynomial time for graphs of bounded NLC-width [1,11,4,6].
展开▼
