Thursday, April 30, 2009

Tadpoles


Tadpoles are graphs made of cycles and paths. The smallest tadpole is made of a cycle on three vertices joined with a path with just one edge. Bigger tadpoles can be obtained by making the cycle larger and/or the path longer. When the tail of the tadpole is made of just one edge, the graph is also known as a pan graph, with the tail playing the role of a pan-handle. Tadpole graphs have been mentioned in the physics literature and seem to date back to Feynman.

Monday, April 20, 2009

Snarks


Snarks are graphs with an interesting property related to graph coloring. One of the most fascinating coloring results, the four-color theorem states that every map can be colored with 4 colors so that no two neighboring countries have the same color. This is the same as saying that every planar graph can be vertex-colored with 4 colors so that no two adjacent nodes have the same color. The four-color theorem can be restated in terms of snarks as follows: no snark is planar. Informally, a snark is a graph in which every vertex has degree 3 and in which every 3-coloring of edges results in some pair of adjacent edges with the same color. Formally, a snark is a biconnected cubic graph with edge chromatic number 4. There are infinitely many snarks but Petersen's graph is the classic. Since the 70's a lot of strange-looking snarks have appeared in various papers: the Szekeres snark, the Blanusa snark, the Zemfirescu snark, Tietze's graph, etc. Tutte's conjecture that all snarks have the Petersen graph as a minor was proven by Robertson, Seymour and company and is now known as "the snark theorem." Snarks are non-planar and non-Hamiltonian. Even stronger, removing any one node from a snark leaves a Hamiltonian subgraph.

Tuesday, April 7, 2009

Centipedes


Centipedes are a subclass of caterpillars. A graph is a centipede if it can be obtained by appending a "leg" to each degree-2 node of a path. In reality they look like a centipede seen from the side at a moment when all its legs on one side occlude all its legs on the other side. I know they were used as far back as 1986 where they popped up in the characterization of the class of graphs that admit cylindric visibility representations.