Reconstruction Conjecture - Recognizable Properties

Recognizable Properties

In context of the reconstruction conjecture, a graph property is called recognizable if one can determine the property from the deck of a graph. The following properties of graphs are recognizable:

  • Degree sequence
  • Tutte polynomial
  • Planarity
  • The types of spanning trees in a graph
  • Chromatic polynomial
  • Being a perfect graph or an interval graph, or some other subclasses of perfect graphs

Read more about this topic:  Reconstruction Conjecture

Famous quotes containing the word properties:

    “The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
    —John Locke (1632–1704)