# 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

http://www.cs.uwa.edu.au/~gordon/remote/questions.html

Open Problems in Discrete Math

http://www.math.princeton.edu/~matdevos/open/open.html

http://www.maths.qmw.ac.uk/~pjc/oldprob.html

http://www.math.binghamton.edu/zaslav/Bsg/sgbgprobs.html

http://www.emba.uvm.edu/~archdeac/newlist/problems.html

http://www.eecs.umich.edu/~qstout/constantques.html

Exploring Graph Theory Through Conjectures of Graffiti

http://cms.dt.uh.edu/faculty/delavinae/StudentPictures/B_Chervenka_Poster_Contents.pdf

Some Open Problems and Conjectures

http://www.eecs.umich.edu/~qstout/constantques.html

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

Conjectures on edge-connectivity

http://www.math.princeton.edu/~matdevos/open/edgecon.html