Live briefing
Everything about Perfect graph
Graph with tight clique-coloring relation
In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Perfect graphA 5-minute orientation
- Skim a recent paper: Signed Graph Metric Learning via Gershgorin Disc Perfect AlignmentInfluential work since 2022
- Pick up a classic book: Algorithmic graph theory and perfect graphsThe most-reprinted book on the subject
- Read the landmark paper: The strong perfect graph theoremCited 877 times
- Go sideways: Perfect graph theoremA closely related topic
- Go sideways: Strong perfect graph theoremA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🏆 Landmark papers (most cited)
The strong perfect graph theorem
Normal hypergraphs and the perfect graph conjecture
The minimum degree threshold for perfect graph packings
Perfect matchings of a graph
On the perfect graph conjecture
The Strong Perfect Graph Conjecture for Planar Graphs
No Graph is Perfect
On the strong perfect graph conjecture
🆕 Influential since 2022
Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment
Extracting perfect GHZ states from imperfect weighted graph states via entanglement concentration
Pseudorandom sets in Grassmann graph have near-perfect expansion
Perfect state transfer in Grover walks between states associated to vertices of a graph
Perfect Matchings in the Semirandom Graph Process
📚 Books worth reading
Algorithmic graph theory and perfect graphsMartin Charles Golumbic · 1980
Perfect GraphsJ.L.R. Alfonsin · 2001
Algorithmic graph theory and perfect graphsMartin Charles Golumbic · 2004
Topics on perfect graphsClaude Berge · 1984- 📕Problems from the world surrounding perfect graphsA. Gyárfás · 1985
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Perfect graph theorem In graph theory, the perfect graph theorem of László Lovász (1972a, 1972b) states that an undirected graph is perfect if and only if its complement graph…
- Strong perfect graph theorem In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither…
- Kőnig's theorem (graph theory) In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem…
- Cograph In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation…
- Glossary of graph theory Look up Appendix:Glossary of graph theory in Wiktionary, the free dictionary. This is a glossary of graph theory. Graph theory is the study of graphs,…
- Split graph In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split…
- Mirsky's theorem In mathematics, in the areas of order theory and combinatorics, Mirsky's theorem characterizes the height of any finite partially ordered set in terms…
- Complement graph In the mathematical field of graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices are…