Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Edge_coloring> ?p ?o. }
Showing items 1 to 29 of
29
with 100 items per page.
- Edge_coloring abstract "In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.By Vizing's theorem, the number of colors needed to edge color a simple graph is either its maximum degree Δ or Δ+1. For some graphs, such as bipartite graphs and high-degree planar graphs, the number of colors is always Δ, and for multigraphs, the number of colors may be as large as 3Δ/2. There are polynomial time algorithms that construct optimal colorings of bipartite graphs, and colorings of non-bipartite simple graphs that use at most Δ+1 colors; however, the general problem of finding an optimal edge coloring is NP-complete and the fastest known algorithms for it take exponential time. Many variations of the edge coloring problem, in which an assignments of colors to edges must satisfy other conditions than non-adjacency, have been studied. Edge colorings have applications in scheduling problems and in frequency assignment for fiber optic networks.".
- Edge_coloring thumbnail Desargues_graph_3color_edge.svg?width=300.
- Edge_coloring wikiPageExternalLink index.php?id=11&PPN=PPN235181684_0077&DMDID=DMDLOG_0051&L=1.
- Edge_coloring wikiPageExternalLink citation.cfm?id=1873601.1873605.
- Edge_coloring wikiPageExternalLink edge-coloring.shtml.
- Edge_coloring wikiPageExternalLink invitedpaper2.pdf.
- Edge_coloring wikiPageExternalLink 1977-20.pdf.
- Edge_coloring wikiPageID "690647".
- Edge_coloring wikiPageRevisionID "584317970".
- Edge_coloring hasPhotoCollection Edge_coloring.
- Edge_coloring subject Category:Graph_coloring.
- Edge_coloring comment "In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring.".
- Edge_coloring label "Coloration des arêtes d'un graphe".
- Edge_coloring label "Coloração de arestas".
- Edge_coloring label "Edge coloring".
- Edge_coloring label "Kantenfärbung".
- Edge_coloring label "Kolorowanie krawędzi".
- Edge_coloring label "Рёберная раскраска".
- Edge_coloring sameAs Kantenfärbung.
- Edge_coloring sameAs Χρωματισμός_ακμών.
- Edge_coloring sameAs Coloration_des_arêtes_d'un_graphe.
- Edge_coloring sameAs Kolorowanie_krawędzi.
- Edge_coloring sameAs Coloração_de_arestas.
- Edge_coloring sameAs m.0332bx.
- Edge_coloring sameAs Q1050972.
- Edge_coloring sameAs Q1050972.
- Edge_coloring wasDerivedFrom Edge_coloring?oldid=584317970.
- Edge_coloring depiction Desargues_graph_3color_edge.svg.
- Edge_coloring isPrimaryTopicOf Edge_coloring.