0xDE (11011110) wrote,

Perfect maximal planar graphs

Find a planar graph all of whose faces (including the outer face) are all quadrilaterals. Possible choices include the square, the cube, K2,n, etc. (All such graphs are bipartite, a fact that will be useful below.) Turn it into a maximal planar graph by adding a new vertex inside each face, connected to all the vertices of the face. For instance, doing this to a cube produces a tetrakis cube, whose graph I've written about previously here. So for short, let's call the result of this construction a "tetrakis graph".

It turns out that every tetrakis graph is a perfect graph, a graph for which the clique number of each induced subgraph equals its chromatic number. If the induced subgraph contains a triangle, or is independent, this is obvious, so the only interesting cases are the triangle-free induced subgraphs. They have clique number two so we need to check that they have chromatic number two. But the underlying quadrilateral-faced graph is always 2-colorable, and if there are no triangles then each of the added vertices that remains in the subgraph can only have neighbors of one color in this 2-coloring.

These aren't the only perfect maximal planar graphs: the tetrahedron K4 is also perfect, and gluing two perfect maximal planar graphs together on a triangular face (which becomes a separating triangle in the glued graph) creates others. Gluing a collection of tetrahedra in this way produces an Apollonian network, and we can also glue together mixtures of tetrahedra and tetrakis graphs. But aside from the tetrahedron, are the tetrakis graphs the only building blocks needed to create the rest by gluing? That is, are they the only 4-connected perfect maximal planar graphs?

Tags: graph theory
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded