Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Graph_coloring> ?p ?o. }
- Graph_coloring abstract "In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges share the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.Vertex coloring is the starting point of the subject, and other coloring problems can be transformed into a vertex version. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a plane graph is just a vertex coloring of its dual. However, non-vertex coloring problems are often stated and studied as is. That is partly for perspective, and partly because some problems are best studied in non-vertex form, as for instance is edge coloring.The convention of using colors originates from coloring the countries of a map, where each face is literally colored. This was generalized to coloring the faces of a graph embedded in the plane. By planar duality it became coloring the vertices, and in this form it generalizes to all graphs. In mathematical and computer representations, it is typical to use the first few positive or nonnegative integers as the "colors". In general, one can use any finite set as the "color set". The nature of the coloring problem depends on the number of colors but not on what they are.Graph coloring enjoys many practical applications as well as theoretical challenges. Beside the classical types of problems, different limitations can also be set on the graph, or on the way a color is assigned, or even on the color itself. It has even reached popularity with the general public in the form of the popular number puzzle Sudoku. Graph coloring is still a very active field of research.Note: Many terms used in this article are defined in Glossary of graph theory.".
- Graph_coloring thumbnail Petersen_graph_3-coloring.svg?width=300.
- Graph_coloring wikiPageExternalLink graph-coloring.appspot.com.
- Graph_coloring wikiPageExternalLink cm3119.pdf.
- Graph_coloring wikiPageExternalLink msb5974.
- Graph_coloring wikiPageExternalLink citation.cfm?id=803884.
- Graph_coloring wikiPageExternalLink software.
- Graph_coloring wikiPageExternalLink gcpcodes_link.html.
- Graph_coloring wikiPageExternalLink index.html.
- Graph_coloring wikiPageExternalLink podc08SW.pdf.
- Graph_coloring wikiPageExternalLink podcfp107_schneider_188.pdf.
- Graph_coloring wikiPageExternalLink cfl.pdf.
- Graph_coloring wikiPageExternalLink rawnet06.pdf.
- Graph_coloring wikiPageExternalLink 1951-01.pdf.
- Graph_coloring wikiPageExternalLink tutte.
- Graph_coloring wikiPageID "426743".
- Graph_coloring wikiPageRevisionID "605226907".
- Graph_coloring above "Graph coloring".
- Graph_coloring abovestyle "background: #DD9".
- Graph_coloring authorlink "Alexander Zykov".
- Graph_coloring authorlink "Jan Mycielski".
- Graph_coloring data NP-complete.
- Graph_coloring data NP-hard.
- Graph_coloring data Sharp-P-complete.
- Graph_coloring data "3".
- Graph_coloring data "Chromatic number".
- Graph_coloring data "Chromatic polynomial".
- Graph_coloring data "Does G admit a proper vertex coloring with k colors?".
- Graph_coloring data "FPRAS for restricted cases".
- Graph_coloring data "GT4".
- Graph_coloring data "Graph G with n vertices. Integer k".
- Graph_coloring data "Graph G with n vertices.".
- Graph_coloring data "Graph coloring, vertex coloring, k-coloring".
- Graph_coloring data "No PTAS unless P = NP".
- Graph_coloring data "O unless P = NP".
- Graph_coloring data "O".
- Graph_coloring data "The number P of proper k-colorings of G".
- Graph_coloring data "χ".
- Graph_coloring first "Alexander".
- Graph_coloring first "Jan".
- Graph_coloring hasPhotoCollection Graph_coloring.
- Graph_coloring header "Counting problem".
- Graph_coloring header "Decision".
- Graph_coloring header "Optimisation".
- Graph_coloring headerstyle "background: #DD9".
- Graph_coloring label "Approximability".
- Graph_coloring label "Complexity".
- Graph_coloring label "Garey–Johnson".
- Graph_coloring label "Inapproximability".
- Graph_coloring label "Input".
- Graph_coloring label "Name".
- Graph_coloring label "Output".
- Graph_coloring label "Reduction from".
- Graph_coloring label "Running time".
- Graph_coloring labelstyle "font-weight:normal".
- Graph_coloring last "Mycielski".
- Graph_coloring last "Zykov".
- Graph_coloring year "1949".
- Graph_coloring year "1955".
- Graph_coloring subject Category:Computational_problems_in_graph_theory.
- Graph_coloring subject Category:Extensions_and_generalizations_of_graphs.
- Graph_coloring subject Category:Graph_coloring.
- Graph_coloring subject Category:Graph_theory.
- Graph_coloring subject Category:NP-complete_problems.
- Graph_coloring type Abstraction100002137.
- Graph_coloring type Attribute100024264.
- Graph_coloring type ComputationalProblemsInGraphTheory.
- Graph_coloring type Condition113920835.
- Graph_coloring type Difficulty114408086.
- Graph_coloring type NP-completeProblems.
- Graph_coloring type Problem114410605.
- Graph_coloring type State100024720.
- Graph_coloring comment "In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring.".
- Graph_coloring label "Coloración de grafos".
- Graph_coloring label "Coloration de graphe".
- Graph_coloring label "Colorazione dei grafi".
- Graph_coloring label "Coloração de grafos".
- Graph_coloring label "Färbung (Graphentheorie)".
- Graph_coloring label "Graph coloring".
- Graph_coloring label "Kleuren van grafen".
- Graph_coloring label "Kolorowanie grafu".
- Graph_coloring label "Раскраска графов".
- Graph_coloring label "مشكلة تلوين المخطط".
- Graph_coloring label "グラフ彩色".
- Graph_coloring label "图着色问题".
- Graph_coloring sameAs Barvení_grafu.
- Graph_coloring sameAs Färbung_(Graphentheorie).
- Graph_coloring sameAs Χρωματισμός_γραφήματος.
- Graph_coloring sameAs Coloración_de_grafos.
- Graph_coloring sameAs Grafo_koloreztaketa.
- Graph_coloring sameAs Coloration_de_graphe.
- Graph_coloring sameAs Colorazione_dei_grafi.
- Graph_coloring sameAs グラフ彩色.
- Graph_coloring sameAs 그래프_색칠_문제.
- Graph_coloring sameAs Kleuren_van_grafen.
- Graph_coloring sameAs Kolorowanie_grafu.
- Graph_coloring sameAs Coloração_de_grafos.
- Graph_coloring sameAs m.02749z.
- Graph_coloring sameAs Q504843.
- Graph_coloring sameAs Q504843.