№ 59-4 (том 1): ОБРАЗОВАНИЕ И НАУКА В XXI ВЕКЕ, Февраль, 2025
Научно-образовательные статьи

PERFECT GRAPHS: BRIDGING STRUCTURE AND OPTIMIZATION

PDF
  • Hapizova Aylar Orazgeldiyeva,
  • Ovezov Halmuhamed Amanmuhamedovich
Hapizova Aylar Orazgeldiyeva
Oguz han Engineering and Technology university of Turkmenistan. Ashgabat, Turkmenistan
Ovezov Halmuhamed Amanmuhamedovich
Oguz han Engineering and Technology university of Turkmenistan. Ashgabat, Turkmenistan

Опубликован 25.03.2025

Как цитировать

A.O. Hapizova, & H.A. Ovezov. (2025). PERFECT GRAPHS: BRIDGING STRUCTURE AND OPTIMIZATION. ОБРАЗОВАНИЕ И НАУКА В XXI ВЕКЕ, 59-4 (том 1). https://mpcareer-google.ru/index.php/journal/article/view/1246

Аннотация

Perfect graphs are a profound class of graphs in combinatorial mathematics where structural elegance meets algorithmic efficiency. Defined by the property that every induced subgraph satisfies χ(G) = ω(G) (the chromatic number equals the clique number), perfect graphs unify fundamental concepts in graph theory. Their study has revolutionized optimization, coloring problems, and complexity theory, offering polynomial-time solutions to otherwise NP-hard challenges. This article explores the definition, properties, and applications of perfect graphs, highlighting their role in modern mathematics and computer science. 

PDF

Библиографические ссылки

  1. Book: "Graph Theory" by Reinhard Diestel — Covers perfect graphs and their properties.
  2. Research Paper: "A Characterization of Perfect Graphs" by László Lovász — Foundational work on perfect graph theory.
  3. Textbook: "Combinatorial Optimization" by William J. Cook et al. — Algorithms for perfect graph problems.
  4. Article: "The Strong Perfect Graph Theorem" (Annals of Mathematics) — Proof of the forbidden-subgraph characterization.