Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Equitable_coloring> ?p ?o }
Showing triples 1 to 77 of
77
with 100 triples per page.
- Equitable_coloring abstract "In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way thatNo two adjacent vertices have the same color, andThe numbers of vertices in any two color classes differ by at most one.That is, the partition of vertices among the different colors is as uniform as possible. For instance, giving each vertex a distinct color would be equitable, but would typically use many more colors than are necessary in an optimal equitable coloring. An equivalent way of defining an equitable coloring is that it is an embedding of the given graph as a subgraph of a Turán graph. There are two kinds of chromatic number associated with equitable coloring. The equitable chromatic number of a graph G is the smallest number k such that G has an equitable coloring with k colors. But G might not have equitable colorings for some larger numbers of colors; the equitable chromatic threshold of G is the smallest k such that G has equitable colorings for any number of colors greater than or equal to k.The Hajnal–Szemerédi theorem, posed as a conjecture by Paul Erdős (1964) and proven by András Hajnal and Endre Szemerédi (1970), states that any graph with maximum degree Δ has an equitable coloring with Δ + 1 colors. Several related conjectures remain open. Polynomial time algorithms are also known for finding a coloring matching this bound, and for finding optimal colorings of special classes of graphs, but the more general problem of deciding whether an arbitrary graph has an equitable coloring with a given number of colors is NP-complete.".
- Equitable_coloring thumbnail Equitable-K15.svg?width=300.
- Equitable_coloring wikiPageExternalLink citation.cfm?id=365411.365811.
- Equitable_coloring wikiPageExternalLink opuscula_math_2603.pdf.
- Equitable_coloring wikiPageExternalLink index.html.
- Equitable_coloring wikiPageExternalLink COCOA-coloring.pdf.
- Equitable_coloring wikiPageID "21796230".
- Equitable_coloring wikiPageLength "18285".
- Equitable_coloring wikiPageOutDegree "40".
- Equitable_coloring wikiPageRevisionID "680799331".
- Equitable_coloring wikiPageWikiLink American_Mathematical_Monthly.
- Equitable_coloring wikiPageWikiLink Brooks_theorem.
- Equitable_coloring wikiPageWikiLink Category:Graph_coloring.
- Equitable_coloring wikiPageWikiLink Chernoff_bound.
- Equitable_coloring wikiPageWikiLink Clique_(graph_theory).
- Equitable_coloring wikiPageWikiLink Combinatorics,_Probability_and_Computing.
- Equitable_coloring wikiPageWikiLink Complement_graph.
- Equitable_coloring wikiPageWikiLink Complete_bipartite_graph.
- Equitable_coloring wikiPageWikiLink Complete_graph.
- Equitable_coloring wikiPageWikiLink Dense_graph.
- Equitable_coloring wikiPageWikiLink File:Equitable-K15.svg.
- Equitable_coloring wikiPageWikiLink Gabriel_Andrew_Dirac.
- Equitable_coloring wikiPageWikiLink Glossary_of_graph_theory.
- Equitable_coloring wikiPageWikiLink Graph_(discrete_mathematics).
- Equitable_coloring wikiPageWikiLink Graph_coloring.
- Equitable_coloring wikiPageWikiLink Graph_product.
- Equitable_coloring wikiPageWikiLink Graph_theory.
- Equitable_coloring wikiPageWikiLink Hamiltonian_path.
- Equitable_coloring wikiPageWikiLink Job_shop_scheduling.
- Equitable_coloring wikiPageWikiLink Journal_of_Combinatorial_Theory.
- Equitable_coloring wikiPageWikiLink List_of_conjectures_by_Paul_Erdős.
- Equitable_coloring wikiPageWikiLink Load_balancing_(computing).
- Equitable_coloring wikiPageWikiLink Lovász_local_lemma.
- Equitable_coloring wikiPageWikiLink NP-completeness.
- Equitable_coloring wikiPageWikiLink Opuscula_Mathematica.
- Equitable_coloring wikiPageWikiLink Outerplanar_graph.
- Equitable_coloring wikiPageWikiLink Parameterized_complexity.
- Equitable_coloring wikiPageWikiLink Split_graph.
- Equitable_coloring wikiPageWikiLink Star_(graph_theory).
- Equitable_coloring wikiPageWikiLink Tree_(graph_theory).
- Equitable_coloring wikiPageWikiLink Treewidth.
- Equitable_coloring wikiPageWikiLink Turán_graph.
- Equitable_coloring wikiPageWikiLink Variance.
- Equitable_coloring wikiPageWikiLink Vertex_(graph_theory).
- Equitable_coloring wikiPageWikiLinkText "Equitable coloring".
- Equitable_coloring wikiPageWikiLinkText "equitable coloring".
- Equitable_coloring wikiPageWikiLinkText "equitable".
- Equitable_coloring author1Link "András Hajnal".
- Equitable_coloring author2Link "Endre Szemerédi".
- Equitable_coloring authorlink "Paul Erdős".
- Equitable_coloring first "András".
- Equitable_coloring first "Endre".
- Equitable_coloring first "Paul".
- Equitable_coloring last "Erdős".
- Equitable_coloring last "Hajnal".
- Equitable_coloring last "Szemerédi".
- Equitable_coloring wikiPageUsesTemplate Template:Citation.
- Equitable_coloring wikiPageUsesTemplate Template:Harvnb.
- Equitable_coloring wikiPageUsesTemplate Template:Harvs.
- Equitable_coloring wikiPageUsesTemplate Template:Harvtxt.
- Equitable_coloring wikiPageUsesTemplate Template:Refbegin.
- Equitable_coloring wikiPageUsesTemplate Template:Refend.
- Equitable_coloring wikiPageUsesTemplate Template:Reflist.
- Equitable_coloring year "1964".
- Equitable_coloring year "1970".
- Equitable_coloring subject Category:Graph_coloring.
- Equitable_coloring hypernym Assignment.
- Equitable_coloring type Redirect.
- Equitable_coloring comment "In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way thatNo two adjacent vertices have the same color, andThe numbers of vertices in any two color classes differ by at most one.That is, the partition of vertices among the different colors is as uniform as possible.".
- Equitable_coloring label "Equitable coloring".
- Equitable_coloring sameAs Q2984415.
- Equitable_coloring sameAs Coloration_équitable.
- Equitable_coloring sameAs m.05mx030.
- Equitable_coloring sameAs Q2984415.
- Equitable_coloring wasDerivedFrom Equitable_coloring?oldid=680799331.
- Equitable_coloring depiction Equitable-K15.svg.
- Equitable_coloring isPrimaryTopicOf Equitable_coloring.