Live briefing
Everything about Perfectly orderable graph
Special case of the perfect graphs in graph theory
In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: Perfectly orderable graphA 5-minute orientation
- Pick up a classic book: Generalized modular decompositions and the recognition of classes of perfectly orderable graphsThe most-reprinted book on the subject
- Read the landmark paper: Four classes of perfectly orderable graphsCited 63 times
- Go sideways: Greedy coloringA closely related topic
- Go sideways: Distance-hereditary graphA closely related topic
đź“– Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Four classes of perfectly orderable graphs
On the complexity of recognizing perfectly orderable graphs
Some classes of perfectly orderable graphs
Which claw-free graphs are perfectly orderable?
On the complexity of recognizing a class of perfectly orderable graphs
All variations on perfectly orderable graphs
Perfectly orderable graphs are quasi-parity graphs: a short proof
Recognition of some perfectly orderable graph classes
đź“š Books worth reading
- 📕Generalized modular decompositions and the recognition of classes of perfectly orderable graphsThomas Raschle · 1999
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
đź”— Related topics
- Greedy coloring In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of…
- Distance-hereditary graph In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances…
- Lexicographic breadth-first search In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different…
- Trivially perfect graph In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals…
- Strongly chordal graph In the mathematical area of graph theory, an undirected graph G is strongly chordal if it is a chordal graph and every cycle of even length (≥ 6) in G…
- Chordal bipartite graph In the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph B = (X,Y,E) in which every cycle of length at least 6 in B has…
- Outerplanar graph In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar…
- 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…