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:

    “A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
    —Ralph Waldo Emerson (1803–1882)