Open Problems & Conjectures


Problem  (Dennis Shasha)

(Graph Movement) G is a connected graph whose nodes are colored. You want to swap pairs of nodes in G, to obtain G' where all nodes of the same color are connected. Can you do this with the fewest swaps?



                                    Other Open Problems

Mark Goldberg's Graph Theory Page



Open Questions in Graph Theory


Open Problems in Discrete Math

Exploring Graph Theory Through Conjectures of Graffiti


Some Open Problems and Conjectures


Tutte's 3, 4, and 5-flow conjectures


Conjectures on edge-connectivity