Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Critical_graph> ?p ?o }
Showing triples 1 to 41 of
41
with 100 triples per page.
- Critical_graph abstract "Not to be confused with the Critical path method, a concept in project management.In general the notion of criticality can refer to any measure.But in graph theory, when the term is used without any qualification, it almost always refers to the chromatic number of a graph.Critical graphs are interesting because they are the minimal members in terms of chromatic number, which is a very important measure in graph theory.More precise definitions follow.A vertex or an edge is a critical element of a graph G if its deletion would decrease the chromatic number of G.Obviously such decrement can be no more than 1 in a graph.A critical graph is a graph in which every vertex or edge is a critical element.A k-critical graph is a critical graph with chromatic number k; a graph G with chromatic number k is k-vertex-critical if each of its vertices is a critical element.Some properties of a k-critical graph G with n vertices and m edges: G has only one component. G is finite (this is the de Bruijn–Erdős theorem of de Bruijn & Erdős 1951). δ(G) ≥ k − 1, that is, every vertex is adjacent to at least k − 1 others. More strongly, G is (k − 1)-edge-connected. See Lovász (1992) If G is (k − 1)-regular, meaning every vertex is adjacent to exactly k − 1 others, then G is either Kk or an odd cycle . This is Brooks' theorem; see Brooks & Tutte (1941)). 2 m ≥ (k − 1) n + k − 3 (Dirac 1957). 2 m ≥ (k − 1) n + [(k − 3)/(k2 − 3)] n (Gallai 1963a). Either G may be decomposed into two smaller critical graphs, with an edge between every pair of vertices that includes one vertex from each of the two subgraphs, or G has at least 2k - 1 vertices (Gallai 1963b). More strongly, either G has a decomposition of this type, or for every vertex v of G there is a k-coloring in which v is the only vertex of its color and every other color class has at least two vertices (Stehlík 2003).It is fairly easy to see that a graph G is vertex-critical if and only if for every vertex v, there is an optimal proper coloring in which v is a singleton color class.As Hajós (1961) showed, every k-critical graph may be formed from a complete graph Kk by combining the Hajós construction with an operation of identifying two nonadjacent vertices. The graphs formed in this way always require k colors in any proper coloring.A double-critical graph is a connected graph in which the deletion of any pair of adjacent vertices decreases the chromatic number by two.One open problem is to determine whether Kk is the only double-critical k-chromatic graph (Erdős 1966).".
- Critical_graph thumbnail Critical_graph_sample.svg?width=300.
- Critical_graph wikiPageID "680672".
- Critical_graph wikiPageLength "6145".
- Critical_graph wikiPageOutDegree "18".
- Critical_graph wikiPageRevisionID "702633468".
- Critical_graph wikiPageWikiLink Brooks_theorem.
- Critical_graph wikiPageWikiLink Category:Graph_coloring.
- Critical_graph wikiPageWikiLink Category:Graph_families.
- Critical_graph wikiPageWikiLink Complete_graph.
- Critical_graph wikiPageWikiLink Critical_path_method.
- Critical_graph wikiPageWikiLink De_Bruijn–Erdős_theorem_(graph_theory).
- Critical_graph wikiPageWikiLink Factor-critical_graph.
- Critical_graph wikiPageWikiLink Glossary_of_graph_theory.
- Critical_graph wikiPageWikiLink Graph_(discrete_mathematics).
- Critical_graph wikiPageWikiLink Graph_coloring.
- Critical_graph wikiPageWikiLink Graph_theory.
- Critical_graph wikiPageWikiLink Hajós_construction.
- Critical_graph wikiPageWikiLink Indagationes_Mathematicae.
- Critical_graph wikiPageWikiLink Journal_of_Combinatorial_Theory.
- Critical_graph wikiPageWikiLink File:Critical_graph_sample.svg.
- Critical_graph wikiPageWikiLinkText "Critical graph".
- Critical_graph wikiPageWikiLinkText "critical graph".
- Critical_graph wikiPageWikiLinkText "minimal ''k''-chromatic graph".
- Critical_graph wikiPageUsesTemplate Template:Citation.
- Critical_graph wikiPageUsesTemplate Template:Harv.
- Critical_graph wikiPageUsesTemplate Template:Harvnb.
- Critical_graph wikiPageUsesTemplate Template:Harvtxt.
- Critical_graph wikiPageUsesTemplate Template:Mvar.
- Critical_graph subject Category:Graph_coloring.
- Critical_graph subject Category:Graph_families.
- Critical_graph hypernym Members.
- Critical_graph type Graph.
- Critical_graph comment "Not to be confused with the Critical path method, a concept in project management.In general the notion of criticality can refer to any measure.But in graph theory, when the term is used without any qualification, it almost always refers to the chromatic number of a graph.Critical graphs are interesting because they are the minimal members in terms of chromatic number, which is a very important measure in graph theory.More precise definitions follow.A vertex or an edge is a critical element of a graph G if its deletion would decrease the chromatic number of G.Obviously such decrement can be no more than 1 in a graph.A critical graph is a graph in which every vertex or edge is a critical element.A k-critical graph is a critical graph with chromatic number k; a graph G with chromatic number k is k-vertex-critical if each of its vertices is a critical element.Some properties of a k-critical graph G with n vertices and m edges: G has only one component. ".
- Critical_graph label "Critical graph".
- Critical_graph sameAs Q5186721.
- Critical_graph sameAs m.032dkr.
- Critical_graph sameAs Q5186721.
- Critical_graph wasDerivedFrom Critical_graph?oldid=702633468.
- Critical_graph depiction Critical_graph_sample.svg.
- Critical_graph isPrimaryTopicOf Critical_graph.