DUALIZABILITY OF GRAPHS Academic Article uri icon

abstract

  • AbstractWe investigate natural dualities for classes of simple graphs. For example, we give a natural duality for the class consisting of all n-colourable graphs and show that, for all n≥3, there is no natural duality for the class consisting of all freely n-colourable graphs. We also prove that there exist arbitrarily long finite chains of 3-colourable graphs that alternate between being dualizable and nondualizable.

publication date

  • December 2010