About: Edge coloring

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia-live.demo.openlinksw.com

An assignment of colors to the edges of a graph so that no two edges that share an endpoint have the same color as each other

Property	Value
dbo:description	an assignment of colors to the edges of a graph so that no two edges that share an endpoint have the same color as each other (en) задача «раскраски» рëбер таким образом, что смежные рёбра не могут быть «закрашены» в один цвет (ru) Zuordnung einer Farbe zu jeder Kante eines Graphen (de) přiřazení barev hranám grafu tak, aby žádné dvě hrany sdílející vrchol neměly stejnou barvu (cs) dodelitev barv povezavam grafa, tako da nobena povezava, ki ima skupno končno točko, nima enake barve (sl)
dbo:thumbnail	wiki-commons:Special:FilePath/Desargues_graph_3color_edge.svg?width=300
dbo:wikiPageExternalLink	http://www.math.cmu.edu/~af1p/Texfiles/strochrom.pdf https://books.google.com/books%3Fid=mKkIGIea_BkC&pg=PA462 http://www.renyi.hu/~p_erdos/1977-20.pdf http://www.cs.sunysb.edu/~algorith/files/edge-coloring.shtml http://www.cs.helsinki.fi/u/mkhkoivi/publications/sicomp-200Y.pdf http://www.cs.umanitoba.ca/~cccg2010/electronicProceedings/invitedpaper2.pdf https://web.archive.org/web/20150119200819/http:/gdz.sub.uni-goettingen.de/index.php%3Fid=11&PPN=PPN235181684_0077&DMDID=DMDLOG_0051&L=1 http://gdz.sub.uni-goettingen.de/index.php%3Fid=11&PPN=PPN235181684_0077&DMDID=DMDLOG_0051&L=1 http://portal.acm.org/citation.cfm%3Fid=1873601.1873605
dbo:wikiPageWikiLink	dbr:Graph_drawing dbr:Baranyai's_theorem dbr:Online_algorithm dbr:Parameterized_complexity dbr:Lexicographic_order dbr:Rainbow_coloring dbr:Forest_(graph_theory) dbr:Hamiltonian_cycle dbr:Ernst_Steinitz dbr:Latin_square dbr:Vadim_G._Vizing dbr:Recursion dbr:Adjacency_matrix dbr:Dual_graph dbr:Utility_graph dbr:Infinite_graph dbr:Linear_programming dbr:Almost_all dbr:Paul_Seymour_(mathematician) dbr:Shannon_multigraph dbr:Matching_(graph_theory) dbr:Time-division_multiple_access dbr:Parallel_algorithm dbr:Scheduling_(production_processes) dbr:Distributive_lattice dbr:Multigraph dbr:Triangulation_(geometry) dbr:Path_coloring dbr:Odd_graph dbr:National_Football_League dbr:Fiber-optic_communication dbr:Directed_graph dbr:Existential_theory_of_the_reals dbr:Snark_(graph_theory) dbr:Israel_Journal_of_Mathematics dbr:Claude_Berge dbr:Anthony_Hilton dbr:Cycle_graph dbr:Handshaking_lemma dbr:Deterministic_finite_automaton dbr:Petersen_graph dbr:Round-robin_tournament dbr:Star_network dbr:Greedy_coloring dbr:Graph_theory dbr:Mathematische_Annalen dbr:Bipartite_graph dbr:Graph_coloring dbr:Maria_Chudnovsky dbr:Girth_(graph_theory) dbr:Bridge_(graph_theory) dbr:Acyclic_coloring dbr:Thue_number dbr:Regular_hexagon dbr:Herbert_Grötzsch dbr:Information_Processing_Letters dbr:De_Bruijn–Erdős_theorem_(graph_theory) dbr:Complete_graph dbr:Complete_bipartite_graph dbr:Random_graph dbr:Cubic_graph dbr:Strongly_connected_graph dbr:K-edge-connected_graph dbr:Complete_coloring dbr:Total_coloring dbr:Uniquely_colorable_graph dbr:Gabriel_Andrew_Dirac dbr:Journal_of_Combinatorial_Theory dbr:Aperiodic_graph dbr:Arboricity dbr:Fractional_coloring dbr:Dinitz_conjecture dbr:Discrete_Mathematics_(journal) dbr:Strong_coloring dbc:Graph_coloring dbr:Four_color_theorem dbr:Prism_(geometry) dbr:Brooks'_theorem dbr:Line_graph dbr:Ramsey's_theorem dbr:Vizing's_theorem dbr:Channel_allocation_schemes dbr:Treewidth dbr:Degree_(graph_theory) dbr:Greg_Kuperberg dbr:Eli_Upfal dbr:Graph_(discrete_mathematics) dbr:Planar_graph dbr:Regular_graph dbr:Critical_graph dbr:Combinatorica dbr:Equitable_coloring dbr:Bipartite_double_cover dbr:Mex_(mathematics) dbr:Triangle-free_graph dbr:D._R._Fulkerson dbr:Biconnected_graph dbr:Synchronizing_word dbr:List_edge-coloring dbr:Perfect_matching dbr:Star_(graph_theory) dbr:Interval_edge_coloring dbr:Linear_arboricity dbr:Generalized_Petersen_graph dbr:Road_coloring_problem dbr:Journal_of_Graph_Theory dbr:Kempe_chain dbr:Sensor_network dbr:SIAM_Journal_on_Computing dbr:SIAM_Journal_on_Discrete_Mathematics dbr:Overfull_graph dbr:Fiber_optic dbr:Amanda_Chetwynd dbr:NP-complete dbr:NP-hard dbr:Jin_Akiyama dbr:Wireless_networks dbr:Misra_&_Gries_edge_coloring_algorithm dbr:Open_shop_scheduling dbr:Maximum_matching dbr:File:Complete-edge-coloring.svg dbr:Akiyama's_conjecture dbr:File:Class-2-planar-3-regular.svg dbr:File:Desargues_graph_3color_edge.svg dbr:File:Generalized_Petersen_9_2_Hamiltonicity.svg dbr:File:K33_parallel_edge_coloring.svg dbr:File:Multigraph-edge-coloring.svg dbr:1-factorization dbr:Euler_tour dbr:File:K44_arboricity.svg dbr:Competitive_ratio dbr:Integer_program dbr:Projective_configuration
dbp:wikiPageUsesTemplate	dbt:Main dbt:Reflist dbt:Math dbt:Cite_journal dbt:Citation dbt:Refend dbt:Sfnp dbt:Refbegin dbt:Mvar dbt:Harv dbt:Harvtxt dbt:Short_description
dct:subject	dbc:NP-complete_problems dbc:Graph_coloring
gold:hypernym	dbr:Assignment
rdfs:label	Edge coloring (en) Χρωματισμός ακμών (el) Kantenfärbung (de) Coloration des arêtes d'un graphe (fr) 변 색칠 (ko) Kolorowanie krawędzi (pl) Coloração de arestas (pt) Рёберная раскраска (ru) Розфарбовування ребер (uk)
owl:sameAs	yago-res:Edge coloring freebase:Edge coloring wikidata:Edge coloring dbpedia-de:Edge coloring dbpedia-fr:Edge coloring dbpedia-pt:Edge coloring dbpedia-he:Edge coloring dbpedia-hu:Edge coloring dbpedia-fa:Edge coloring dbpedia-ru:Edge coloring dbpedia-pl:Edge coloring dbpedia-ko:Edge coloring dbpedia-el:Edge coloring dbpedia-hr:Edge coloring dbpedia-sk:Edge coloring dbpedia-sr:Edge coloring dbpedia-ta:Edge coloring dbpedia-uk:Edge coloring dbpedia-global:Edge coloring dbr:Edge coloring
prov:wasDerivedFrom	wikipedia-en:Edge_coloring?oldid=1250288509&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Class-2-planar-3-regular.svg wiki-commons:Special:FilePath/Desargues_graph_3color_edge.svg wiki-commons:Special:FilePath/Generalized_Petersen_9_2_Hamiltonicity.svg wiki-commons:Special:FilePath/K33_parallel_edge_coloring.svg wiki-commons:Special:FilePath/K44_arboricity.svg wiki-commons:Special:FilePath/Multigraph-edge-coloring.svg wiki-commons:Special:FilePath/Complete-edge-coloring.svg
foaf:isPrimaryTopicOf	wikipedia-en:Edge_coloring
is dbo:wikiPageRedirects of	dbr:Edge_chromatic_number dbr:Tait_coloring dbr:Edge_colouring dbr:Chromatic_index dbr:K-edge_colorable dbr:Applications_of_edge_coloring dbr:Algorithms_for_edge_coloring
is dbo:wikiPageWikiLink of	dbr:Extremal_graph_theory dbr:Baranyai's_theorem dbr:Rainbow_coloring dbr:Glossary_of_graph_theory dbr:Latin_square dbr:Vadim_G._Vizing dbr:Hadwiger_conjecture_(graph_theory) dbr:Edge_chromatic_number dbr:Tait_coloring dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Fano_plane dbr:Shannon_multigraph dbr:Matching_(graph_theory) dbr:Linkless_embedding dbr:Odd_graph dbr:Erdős–Faber–Lovász_conjecture dbr:Graph_factorization dbr:Cycle_double_cover dbr:Snark_(graph_theory) dbr:Anthony_Hilton dbr:Graph_theory dbr:Bipartite_graph dbr:Graph_coloring dbr:Rado_graph dbr:K-graph_C*-algebra dbr:Incidence_(graph) dbr:Claude_Shannon dbr:Edge_colouring dbr:Complete_bipartite_graph dbr:Graph_minor dbr:Cubic_graph dbr:Heawood_graph dbr:Hypohamiltonian_graph dbr:Tietze's_graph dbr:Domatic_number dbr:Nowhere-zero_flow dbr:Total_coloring dbr:Trace_diagram dbr:Uniquely_colorable_graph dbr:Helly_family dbr:List_of_graph_theory_topics dbr:Tait's_conjecture dbr:Brooks'_theorem dbr:Vizing's_theorem dbr:Open-shop_scheduling dbr:Pancake_graph dbr:Computers_and_Intractability dbr:Perfect_graph dbr:APX dbr:List_edge-coloring dbr:Entropy_compression dbr:Hamiltonian_simulation dbr:Dijkstra_Prize dbr:Chromatic_index dbr:Book_embedding dbr:Interval_edge_coloring dbr:Prism_graph dbr:Graph-encoded_map dbr:Generalized_Petersen_graph dbr:Quartic_graph dbr:Matching_in_hypergraphs dbr:Overfull_graph dbr:Planar_SAT dbr:Slicing_the_Truth dbr:The_Petersen_Graph dbr:Graph_amalgamation dbr:Graph_coloring_game dbr:Amanda_Chetwynd dbr:Common_graph dbr:Misra_&_Gries_edge_coloring_algorithm dbr:Desargues_configuration dbr:Goldberg–Seymour_conjecture dbr:Balanced_hypergraph dbr:Rainbow_matching dbr:Gallery_of_named_graphs dbr:K-edge_colorable dbr:110-vertex_Iofinova-Ivanov_graph dbr:Applications_of_edge_coloring dbr:Algorithms_for_edge_coloring
is foaf:primaryTopic of	wikipedia-en:Edge_coloring