Inductive computations on graphs defined by clique-width expressions

Frédérique Carrère

Displaying similar documents to “Inductive computations on graphs defined by clique-width expressions”

Deciding clique-width for graphs of bounded tree-width.

Espelage, Wolfgang, Gurski, Frank, Wanke, Egon (2003)

Journal of Graph Algorithms and Applications

Similarity:

Path-Neighborhood Graphs

R.C. Laskar, Henry Martyn Mulder (2013)

Discussiones Mathematicae Graph Theory

Similarity:

A path-neighborhood graph is a connected graph in which every neighborhood induces a path. In the main results the 3-sun-free path-neighborhood graphs are characterized. The 3-sun is obtained from a 6-cycle by adding three chords between the three pairs of vertices at distance 2. A Pk-graph is a path-neighborhood graph in which every neighborhood is a Pk, where Pk is the path on k vertices. The Pk-graphs are characterized for k ≤ 4.

A note on the computational complexity of computing the edge rotation distance between graphs

Mirko Křivánek (1988)

Časopis pro pěstování matematiky

Similarity:

Asteroidal Quadruples in non Rooted Path Graphs

Marisa Gutierrez, Benjamin Lévêque, Silvia B. Tondato (2015)

Discussiones Mathematicae Graph Theory

Similarity:

A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted path graph is the intersection graph of a family of directed subpaths of a rooted tree. Rooted path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted path graphs. For this purpose, we are studying in this...