This page contains a collection of problems in graph theory, which occurred to me when I was working on related research topics. The problems are small, but I think they are good appetizers, to get started in these areas.
- Intersection of Longest Paths Problem: In 1966, Gallai asked whether all longest paths in a connected graph share a common vertex. Counterexamples indicate that this is not true in general. However, Gallai’s question is positive for certain well-known classes of connected graphs, such as split graphs, interval graphs, circular arc graphs, outerplanar graphs, series-parallel graphs, and $2K_2$-free graphs. Is Gallai’s question true for the following families of graphs:
- 3K_2-free
- 2K_2 union K_1-free
- K_2 union P_3-free
- Line graphs, particularly, line graphs of cubic graphs (a path in the line graph $L(G)$ of $G$ is corresponding to an open trail in the graph $G$, and in a cubic graph, an open trail is just a path)
- P_5-free graphs
- graphs which do not contain forbidden pairs for hamiltonian paths
- Generalization of Intersection of Longest Paths Problem: Is it true that in a connected graph, all longest open trails have a nonempty intersection?
- Characterize 2-edge-connected $n$-vertex graphs which satisfy $σ_3(G)>=n$ but contain no two edge-disjoint spanning trees.
- Problems on Homeomorphically Irreducible Spanning Trees
- if every 4-connected claw-free graph has a HIST
- if every 4-connected line graph has a HIST
- what is the minimum toughness for a graph to have a HIST, is 2-tough enough
- Characterize forbidden pairs for prism hamiltonicity (solved in my Graph Theory class in Fall 2017)