Graph Theory

Links ## Books (with information on the web)

- Graph Theory by Reinhard Diestel. Can be downloaded in pdf.
- Graphtheory.com homepage for "Graph Theory and it Applications" by Gross and Yellen.
- The Theory of 2-Structures by Andrzej Ehrenfeucht, Tero Harju and Grzegorz Rozenberg.
- Lecture Notes by Tero Harju.
## General Links and tutorials

- The Graph Theory White Pages by Daniel P. Sanders.
- Mathworld Graph Theory Part of Eric W. Weisstein's comprehensive site.
- Graph Theory Page by Stephen C. Locke (Course notes and definitions).
- Graph Theory Tutorials by Chris Caldwell.
## Open Problems

- Problems in Topological Graph Theory by Dan Archdeacon.
- Open Problem Columns by Douglas West.
- Graph Theory Open Problems from Rutgers.
- Unsolved Problems The list of 50 problems from the book by Bondy and Murty (Stephen C. Locke).
## Combinatorics Sites

## More Graph Theory Sites

- Switching Jurriaan Hage's page on switching of graphs.
- Signed, Gain and Biased Graphs by Thomas Zaslavsky.
- History of the 4-Colour Theorem
- 4-Colour Theorem A summary of a new proof by Robertson, Sanders, Seymour and Thomas.
- Graph coloring by David Eppstein.

## Some of my Articles on Switching

Andrzej Ehrenfeucht, Tero Harju, and Grzegorz Rozenberg

Transitivity of local complementation and switching on graphs

Discrete Math.278 (2004), 45 - 60.doi: 10.1016/j.disc.2003.04.001

Transitivity of complementation, local complementation and switching are considered for undirected graphs. Simple compositions of these operations are shown to form transitive groups. Also, most impressively, it is shown that complementation is a composition of 13 operations of local complementation and switching.

Jurriaan Hage and Tero Harju

A characterization of acyclic switching classes using forbidden subgraphs

SIAM J. Discrete Math.18(1) (2004), 159 - 176.doi: 10.1137/S0895480100381890

We characterize by forbidden subgraphs the switching classes of graphs that do not contain an acyclic graph. In addition to switches of the cycles C(n) forn > 6, there are only finitely many such graphs in 24 switching classes, all having at most 9 vertices.

Andrzej Ehrenfeucht, Tero Harju, and Grzegorz Rozenberg:

Finite metrics in switching classes

An older version:

Discrete Appl. Math.,155 (2007), 68-73.doi:10.1016/j.dam.2006.04.041