Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Edge_coloring> ?p ?o }
- 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 citation.cfm?id=1873601.1873605.
- Edge_coloring wikiPageExternalLink invitedpaper2.pdf.
- Edge_coloring wikiPageExternalLink books?id=mKkIGIea_BkC&pg=PA462.
- Edge_coloring wikiPageExternalLink index.php?id=11&PPN=PPN235181684_0077&DMDID=DMDLOG_0051&L=1.
- Edge_coloring wikiPageExternalLink edge-coloring.shtml.
- Edge_coloring wikiPageExternalLink 1977-20.pdf.
- Edge_coloring wikiPageID "690647".
- Edge_coloring wikiPageLength "63883".
- Edge_coloring wikiPageOutDegree "154".
- Edge_coloring wikiPageRevisionID "677724307".
- Edge_coloring wikiPageWikiLink 1-factorization.
- Edge_coloring wikiPageWikiLink Acyclic_coloring.
- Edge_coloring wikiPageWikiLink Akiyamas_conjecture.
- Edge_coloring wikiPageWikiLink Almost_all.
- Edge_coloring wikiPageWikiLink Aperiodic_graph.
- Edge_coloring wikiPageWikiLink Arboricity.
- Edge_coloring wikiPageWikiLink Baranyais_theorem.
- Edge_coloring wikiPageWikiLink Biconnected_graph.
- Edge_coloring wikiPageWikiLink Bipartite_double_cover.
- Edge_coloring wikiPageWikiLink Bipartite_graph.
- Edge_coloring wikiPageWikiLink Bridge_(graph_theory).
- Edge_coloring wikiPageWikiLink Brooks_theorem.
- Edge_coloring wikiPageWikiLink Category:Graph_coloring.
- Edge_coloring wikiPageWikiLink Channel_allocation_schemes.
- Edge_coloring wikiPageWikiLink Claude_Berge.
- Edge_coloring wikiPageWikiLink Combinatorica.
- Edge_coloring wikiPageWikiLink Competitive_analysis_(online_algorithm).
- Edge_coloring wikiPageWikiLink Competitive_ratio.
- Edge_coloring wikiPageWikiLink Complete_bipartite_graph.
- Edge_coloring wikiPageWikiLink Complete_coloring.
- Edge_coloring wikiPageWikiLink Complete_graph.
- Edge_coloring wikiPageWikiLink Configuration_(geometry).
- Edge_coloring wikiPageWikiLink Critical_graph.
- Edge_coloring wikiPageWikiLink Cubic_graph.
- Edge_coloring wikiPageWikiLink Cycle_graph.
- Edge_coloring wikiPageWikiLink D._R._Fulkerson.
- Edge_coloring wikiPageWikiLink De_Bruijn–Erdős_theorem_(graph_theory).
- Edge_coloring wikiPageWikiLink Degree_(graph_theory).
- Edge_coloring wikiPageWikiLink Deterministic_finite_automaton.
- Edge_coloring wikiPageWikiLink Dinitz_conjecture.
- Edge_coloring wikiPageWikiLink Directed_graph.
- Edge_coloring wikiPageWikiLink Discrete_Mathematics_(journal).
- Edge_coloring wikiPageWikiLink Distributive_lattice.
- Edge_coloring wikiPageWikiLink Dual_graph.
- Edge_coloring wikiPageWikiLink Eli_Upfal.
- Edge_coloring wikiPageWikiLink Equitable_coloring.
- Edge_coloring wikiPageWikiLink Ernst_Steinitz.
- Edge_coloring wikiPageWikiLink Euler_tour.
- Edge_coloring wikiPageWikiLink Eulerian_path.
- Edge_coloring wikiPageWikiLink Existential_theory_of_the_reals.
- Edge_coloring wikiPageWikiLink Fiber-optic_communication.
- Edge_coloring wikiPageWikiLink Fiber_optic.
- Edge_coloring wikiPageWikiLink Forest_(graph_theory).
- Edge_coloring wikiPageWikiLink Four_color_theorem.
- Edge_coloring wikiPageWikiLink Fractional_coloring.
- Edge_coloring wikiPageWikiLink Gabriel_Andrew_Dirac.
- Edge_coloring wikiPageWikiLink Generalized_Petersen_graph.
- Edge_coloring wikiPageWikiLink Girth_(graph_theory).
- Edge_coloring wikiPageWikiLink Glossary_of_graph_theory.
- Edge_coloring wikiPageWikiLink Graph_(mathematics).
- Edge_coloring wikiPageWikiLink Graph_coloring.
- Edge_coloring wikiPageWikiLink Graph_drawing.
- Edge_coloring wikiPageWikiLink Graph_factorization.
- Edge_coloring wikiPageWikiLink Graph_theory.
- Edge_coloring wikiPageWikiLink Greedy_coloring.
- Edge_coloring wikiPageWikiLink Greg_Kuperberg.
- Edge_coloring wikiPageWikiLink Hamiltonian_cycle.
- Edge_coloring wikiPageWikiLink Hamiltonian_path.
- Edge_coloring wikiPageWikiLink Handshaking_lemma.
- Edge_coloring wikiPageWikiLink Herbert_Grötzsch.
- Edge_coloring wikiPageWikiLink Hexagon.
- Edge_coloring wikiPageWikiLink Infinite_graph.
- Edge_coloring wikiPageWikiLink Information_Processing_Letters.
- Edge_coloring wikiPageWikiLink Integer_program.
- Edge_coloring wikiPageWikiLink Integer_programming.
- Edge_coloring wikiPageWikiLink Interval_edge_coloring.
- Edge_coloring wikiPageWikiLink Journal_of_Combinatorial_Theory.
- Edge_coloring wikiPageWikiLink K-edge-connected_graph.
- Edge_coloring wikiPageWikiLink Kempe_chain.
- Edge_coloring wikiPageWikiLink Latin_square.
- Edge_coloring wikiPageWikiLink Lexicographic_order.
- Edge_coloring wikiPageWikiLink Lexicographical_order.
- Edge_coloring wikiPageWikiLink Line_graph.
- Edge_coloring wikiPageWikiLink Linear_programming.
- Edge_coloring wikiPageWikiLink List_edge-coloring.
- Edge_coloring wikiPageWikiLink Maria_Chudnovsky.
- Edge_coloring wikiPageWikiLink Matching_(graph_theory).
- Edge_coloring wikiPageWikiLink Mathematische_Annalen.
- Edge_coloring wikiPageWikiLink Maximum_matching.
- Edge_coloring wikiPageWikiLink Misra_&_Gries_edge_coloring_algorithm.
- Edge_coloring wikiPageWikiLink Multigraph.
- Edge_coloring wikiPageWikiLink NP-complete.
- Edge_coloring wikiPageWikiLink NP-completeness.
- Edge_coloring wikiPageWikiLink National_Football_League.
- Edge_coloring wikiPageWikiLink Odd_graph.
- Edge_coloring wikiPageWikiLink Online_algorithm.
- Edge_coloring wikiPageWikiLink Open-shop_scheduling.
- Edge_coloring wikiPageWikiLink Open_shop_scheduling.