Teoría de grafos/Problemas y algoritmos

Problemas y Algoritmos

• Coloramiento de grafos:
  • el teorema de 4-colores
  • el strong perfect graph theorem
  • la conjetura Erdős-Faber-Lovász (sin resolver)
  • la total coloring conjecture (unsolved)
  • la list coloring conjecture (unsolved)

• Subestructura Gráfica:
  • Independent set
  • Clique

• Route problems:
  • Seven bridges of Königsberg
  • Minimum spanning tree
  • Steiner tree
  • Shortest path problem
  • Route inspection problem (also called the "Chinese Postman Problem")
  • Traveling salesman problem

• Network flows:
  • Max flow min cut theorem
• Reconstruction conjecture

• Graph isomorphism problems (Graph matching)
  • Canonical labeling
  • Subgraph isomorphism and monomorphisms
  • Maximal common subgraph