Steve Hedetniemi

Department of Computer Science

Clemson University

Clemson, SC 29634-1906

- 2-INTERSECTION NUMBER [Jacobson, 1992]
- INSTANCE: A path P
_{n}= (V,E) with n vertices, a positive integer K. - QUESTION: Is the 2-intersection number of P
_{n}<= K?

The idea here is to represent the path P

_{n}with n vertices as an intersection graph. We associate with each vertex a subset of a given set A, where |A| = K, and we require that two vertices are adjacent if and only if the cardinality of the intersection of the corresponding two subsets >= 2. The 2-intersection number of a graph is the smallest cardinality of a set A on which a 2-intersection representation is possible. It is apparently extremely difficult to determine the 2-intersection number of a path! [M.S. Jacobson, A.E. Kezdy and D.B. West, The 2-Intersection Number of Paths and Bounded-Degree Trees, preprint]. - INSTANCE: A path P
- NON-INTERSECTING LONGEST PATHS [Schwenk, 198X]
- INSTANCE: A connected graph G = (V,E).
- QUESTION: Does G have three longest paths which do not intersect in a common vertex?

Obviously, the problem of finding a longest path in a graph is NP-complete. This is not what Schwenk is asking. Instead, he wants to know if there exists a graph having three longest paths which do not intersect in a common vertex. All graph theorists know the famous result which states that every two longest paths in a connected graph must have a vertex in common. However, Schwenk says that a graph is known in which there exist something like seven longest paths which do not intersect in a common vertex. But no one has ever found a graph with three longest paths having this non-intersecting property.

- TREE PACKING [Gyarfas and Lehel, 1974]
- INSTANCE: A set of n-1 trees,
T
_{1},T_{2},...,T_{n-1}, where tree T_{i}has i edges. - QUESTION: Can this set of trees be packed exactly into K
_{n}?

- INSTANCE: A set of n-1 trees,
T
- PLANAR DECOMPOSITION INTO SERIES-PARALLEL GRAPHS [Richey, 198X]
- INSTANCE: A planar graph G = (V,E).
- QUESTION: Can the edges of G be partitioned into two sets
E
_{1}and E_{2}, each of which induces a series-parallel graph?

- PLANAR DECOMPOSITION INTO OUTERPLANAR GRAPHS [Hedetniemi, 1968]
- INSTANCE: A planar graph G = (V,E).
- QUESTION: Can the edges of G be partitioned into two sets
E
_{1}and E_{2}, each of which induces an outerplanar graph?

- GRAPH RECONSTRUCTION [Folklore]
- INSTANCE: A set of (vertex deleted) graphs of order n,
G
_{1}, ... , G_{n}. - QUESTION: Does there exist a (unique) graph G whose vertex deleted subgraphs equal the given set of graphs?

- INSTANCE: A set of (vertex deleted) graphs of order n,
G