Perfectly orderable graph (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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. (en) У теорії графів цілком упорядковуваний граф — це граф, вершини якого можна впорядкувати так, що алгоритм жадібного розфарбовування з цим упорядкуванням оптимально розфарбовує будь-який породжений підграф даного графу. Відповідне впорядкування називається досконалим. Цілком упорядковувані графи утворюють підклас досконалих графів і в цей підклас входять хордальні графи, графи порівнянності і дистанційно-успадковувані графи. Однак перевірка, чи є граф цілком упорядковуваним, є NP-повною задачею. (uk) В теории графов вполне упорядочиваемый граф — это граф, вершины которого можно упорядочить так, что алгоритм жадной раскраски с этим упорядочением оптимально раскрашивает любой порождённый подграф заданного графа. Соответствующее упорядочение называется совершенным. Вполне упорядочиваемые графы образуют подкласс совершенных графов и в это подкласс входят хордальные графы, графы сравнимости и дистанционно-наследуемые графы. Однако проверка, является ли граф вполне упорядочиваемым, есть NP-полная задача. (ru) |
| dbo:wikiPageExternalLink | https://archive.org/details/graphclassessurv0000bran https://refubium.fu-berlin.de/handle/fub188/18407 https://digitalcommons.odu.edu/computerscience_fac_pubs/132 |
| dbo:wikiPageID | 21051205 (xsd:integer) |
| dbo:wikiPageLength | 10268 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1032107611 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Topological_ordering dbc:Perfect_graphs dbr:Induced_path dbr:Induced_subgraph dbr:Lexicographic_breadth-first_search dbc:Graph_coloring dbr:Order_(journal) dbr:NP-complete dbr:Comparability_graph dbr:Complement_graph dbr:Perfect_graph dbr:Cycle_graph dbr:Partially_ordered_set dbr:Dilworth's_theorem dbr:Discrete_Mathematics_(journal) dbr:Graph_theory dbr:Journal_of_Combinatorial_Theory dbr:Tolerance_graph dbr:Chordal_graph dbr:Cograph dbr:Distance-hereditary_graph dbr:Greedy_coloring dbr:Mex_(mathematics) dbr:Neighborhood_(graph_theory) dbr:Transitive_orientation |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Reflist dbt:Sfnp dbt:Short_description |
| dct:subject | dbc:Perfect_graphs dbc:Graph_coloring |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:VisualCommunication106873252 yago:WikicatPerfectGraphs |
| rdfs:comment | 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. (en) У теорії графів цілком упорядковуваний граф — це граф, вершини якого можна впорядкувати так, що алгоритм жадібного розфарбовування з цим упорядкуванням оптимально розфарбовує будь-який породжений підграф даного графу. Відповідне впорядкування називається досконалим. Цілком упорядковувані графи утворюють підклас досконалих графів і в цей підклас входять хордальні графи, графи порівнянності і дистанційно-успадковувані графи. Однак перевірка, чи є граф цілком упорядковуваним, є NP-повною задачею. (uk) В теории графов вполне упорядочиваемый граф — это граф, вершины которого можно упорядочить так, что алгоритм жадной раскраски с этим упорядочением оптимально раскрашивает любой порождённый подграф заданного графа. Соответствующее упорядочение называется совершенным. Вполне упорядочиваемые графы образуют подкласс совершенных графов и в это подкласс входят хордальные графы, графы сравнимости и дистанционно-наследуемые графы. Однако проверка, является ли граф вполне упорядочиваемым, есть NP-полная задача. (ru) |
| rdfs:label | Perfectly orderable graph (en) Вполне упорядочиваемый граф (ru) Цілком упорядковуваний граф (uk) |
| owl:sameAs | freebase:Perfectly orderable graph yago-res:Perfectly orderable graph wikidata:Perfectly orderable graph dbpedia-ru:Perfectly orderable graph dbpedia-uk:Perfectly orderable graph https://global.dbpedia.org/id/gqAp |
| prov:wasDerivedFrom | wikipedia-en:Perfectly_orderable_graph?oldid=1032107611&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Perfectly_orderable_graph |
| is dbo:wikiPageWikiLink of | dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:Line_perfect_graph dbr:Comparability_graph dbr:Perfect_graph dbr:Tolerance_graph dbr:Chordal_graph dbr:Cograph dbr:Distance-hereditary_graph dbr:Greedy_coloring |
| is foaf:primaryTopic of | wikipedia-en:Perfectly_orderable_graph |