Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Gallai–Hasse–Roy–Vitaver_theorem> ?p ?o }
Showing triples 1 to 50 of
50
with 100 triples per page.
- Gallai–Hasse–Roy–Vitaver_theorem abstract "In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that a number k is the smallest number of colors among all colorings of graph G if and only if k is the largest number for which every orientation of G contains a simple directed path with k vertices. That is, the chromatic number is one plus the length of a longest path in an orientation of the graph chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation.An alternative statement of the same theorem is that every orientation of a graph with chromatic number k contains a simple directed path with k vertices; this path can be constrained to begin at any vertex that can reach all other vertices of the oriented graph.".
- Gallai–Hasse–Roy–Vitaver_theorem thumbnail Gallai-Hasse-Roy-Vitaver_theorem.svg?width=300.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageID "36620043".
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageLength "11133".
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageOutDegree "30".
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageRevisionID "681978147".
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Acyclic_orientation.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Bipartite_graph.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Category:Duality_theories.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Category:Graph_coloring.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Category:Theorems_in_graph_theory.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Category_(mathematics).
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Chromatic_number.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Claude_Berge.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Complete_graph.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Cycle_graph.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Directed_acyclic_graph.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Directed_graph.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Duality_(mathematics).
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Glossary_of_graph_theory.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Graph_coloring.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Graph_homomorphism.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Graph_theory.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Longest_path.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Longest_path_problem.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Mathematical_induction.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Maximal_element.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Mirskys_theorem.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Orientation_(graph_theory).
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Partially_ordered_set.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Path_graph.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Polytree.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Tibor_Gallai.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Tournament_(graph_theory).
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink Yuri_Matiyasevich.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLink File:Gallai-Hasse-Roy-Vitaver_theorem.svg.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageWikiLinkText "Gallai–Hasse–Roy–Vitaver theorem".
- Gallai–Hasse–Roy–Vitaver_theorem hasPhotoCollection Gallai–Hasse–Roy–Vitaver_theorem.
- Gallai–Hasse–Roy–Vitaver_theorem wikiPageUsesTemplate Template:Reflist.
- Gallai–Hasse–Roy–Vitaver_theorem subject Category:Duality_theories.
- Gallai–Hasse–Roy–Vitaver_theorem subject Category:Graph_coloring.
- Gallai–Hasse–Roy–Vitaver_theorem subject Category:Theorems_in_graph_theory.
- Gallai–Hasse–Roy–Vitaver_theorem comment "In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that a number k is the smallest number of colors among all colorings of graph G if and only if k is the largest number for which every orientation of G contains a simple directed path with k vertices.".
- Gallai–Hasse–Roy–Vitaver_theorem label "Gallai–Hasse–Roy–Vitaver theorem".
- Gallai–Hasse–Roy–Vitaver_theorem sameAs m.0knwscy.
- Gallai–Hasse–Roy–Vitaver_theorem sameAs Q5518852.
- Gallai–Hasse–Roy–Vitaver_theorem sameAs Q5518852.
- Gallai–Hasse–Roy–Vitaver_theorem wasDerivedFrom Gallai–Hasse–Roy–Vitaver_theorem?oldid=681978147.
- Gallai–Hasse–Roy–Vitaver_theorem depiction Gallai-Hasse-Roy-Vitaver_theorem.svg.
- Gallai–Hasse–Roy–Vitaver_theorem isPrimaryTopicOf Gallai–Hasse–Roy–Vitaver_theorem.