About: Graph homomorphism

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

A structure-preserving correspondence between node-link graphs

Property	Value
dbo:description	a structure-preserving correspondence between node-link graphs (en) відображення між двома графами, що не порушує структури (uk) 圖論中，保持圖結構的映射 (zh)
dbo:thumbnail	wiki-commons:Special:FilePath/Graph_homomorphism_into_C5.svg?width=300
dbo:wikiPageExternalLink	http://vrs.amsi.org.au/projects/ https://wwwpub.zih.tu-dresden.de/~bodirsky/Graph-Homomorphisms.pdf http://www.maths.qmul.ac.uk/~pjc/csgnotes/hom1.pdf http://www.mast.queensu.ca/~ctardif/articles/ghss.pdf http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1a1%7Cdoi-access=free http://www.cs.sfu.ca/~pavol/cspCCC.pdf http://www.cs.sfu.ca/~pavol/hombook.html http://vrs.amsi.org.au/wp-content/uploads/sites/6/2014/09/CORRECTED-digraph-lattice-Gray-updated.pdf
dbo:wikiPageWikiLink	dbr:Kneser_graph dbr:Backtracking dbr:Parameterized_complexity dbr:Harmonic dbr:Polynomial-time_reduction dbr:File:Complete_graph_K7.svg dbr:Glossary_of_graph_theory dbr:P_versus_NP_problem dbr:Constraint_satisfaction_problem dbr:NP-intermediate dbr:Cartesian_closed_category dbr:Wireless_network dbc:Graph_theory dbr:Electronic_Journal_of_Combinatorics dbc:Morphisms dbr:Graph_isomorphism dbr:Antichain dbr:Homomorphism dbr:Neighbourhood_(graph_theory) dbr:Heyting_algebra dbr:Scheduling_(production_processes) dbr:Distributive_lattice dbr:Covering_graph dbr:Complement_graph dbr:Preorder dbr:Mathematics dbr:Dense_order dbr:Inverse_function dbr:Connectivity_(graph_theory) dbr:Odd_number dbr:La_Trobe_University dbr:Equivalence_class dbr:Exponential_time_hypothesis dbr:Cycle_graph dbr:Hypercube_graph dbr:Jaroslav_Nešetřil dbr:Vertex_(graph_theory) dbr:Tensor_product_of_graphs dbr:Graph_theory dbr:Bipartite_graph dbr:Chromatic_number dbr:Graph_coloring dbr:Initial_and_terminal_objects dbr:Structure_(mathematical_logic) dbr:Girth_(graph_theory) dbr:Induced_subgraph dbr:Australian_Mathematical_Sciences_Institute dbr:Complete_graph dbr:Category_(mathematics) dbr:Complete_bipartite_graph dbr:Graph_minor dbr:Electromagnetic_interference dbr:Grötzsch_graph dbr:Median_graph dbr:Partial_order dbr:Surjective_function dbr:Fractional_coloring dbr:Local_search_(constraint_satisfaction) dbr:T-coloring dbr:Bijection dbr:Injective_function dbr:Loop_(graph_theory) dbr:Path_graph dbr:Product_(category_theory) dbr:Graph_rewriting dbr:Directed_edge dbr:Time_complexity dbr:Treewidth dbr:Multiple_edges dbr:Orientation_(graph_theory) dbr:Oriented_coloring dbr:Oriented_graph dbr:Dynamic_programming dbr:Frequency_allocation dbr:Brute-force_search dbr:Graph_(discrete_mathematics) dbr:Homeomorphism_(graph_theory) dbr:Mycielskian dbr:Circular_coloring dbr:Complexity_of_constraint_satisfaction dbr:Bipartite_double_cover dbr:Join_and_meet dbr:Exponential_object dbr:Gallai–Hasse–Roy–Vitaver_theorem dbr:Decision_problem dbr:Computational_complexity dbr:Frequency_assignment dbr:L(2,1)-coloring dbr:Sidorenko's_conjecture dbr:Recursive_set dbr:NP-complete dbr:Martin_Grohe dbr:Pavol_Hell dbr:Hedetniemi's_conjecture dbr:Glossary_of_graph_theory_terms dbr:Moshe_Y._Vardi dbr:Fixed-parameter_tractable dbr:Join-irreducible dbr:Primal_constraint_graph dbr:Constraint_propagation dbr:Circular_clique dbr:Covering_map dbr:Meet-irreducible dbr:Poset dbr:File:Graph_homomorphism_into_C5.svg dbr:File:Graph_of_non-adjacent_weekdays.svg dbr:File:Groetzsch-graph.svg
dbp:1a	Cameron (en) Hell (en) Nešetřil (en)
dbp:1loc	Proposition 2.3 (en) Theorem 3.30 (en) §6.1 (en) §6.2 (en)
dbp:1p	1 (xsd:integer) 192 (xsd:integer)
dbp:1y	2004 (xsd:integer) 2006 (xsd:integer)
dbp:2a	Hahn (en) Hell (en) Nešetřil (en) Tardif (en)
dbp:2loc	Corollary 1.32 (en) Proposition 1.7 (en) Theorem 2.33 (en) §4.4 (en) §4.5 (en)
dbp:2p	127 (xsd:integer)
dbp:2y	1997 (xsd:integer) 2004 (xsd:integer)
dbp:date	2018-08-14 (xsd:date)
dbp:url	https://web.archive.org/web/20180814235547/http:/vrs.amsi.org.au/projects/
dbp:wikiPageUsesTemplate	dbt:Good_article dbt:Cite_book dbt:Main dbt:Reflist dbt:Math dbt:Sfn dbt:Citation dbt:Var dbt:Distinguish dbt:Sfnm dbt:Shy dbt:Webarchive dbt:Short_description dbt:Vec
dct:subject	dbc:NP-complete_problems dbc:Graph_theory dbc:Morphisms
gold:hypernym	dbr:Mapping
rdf:type	owl:Thing owl:Thing
rdfs:label	Graph homomorphism (en) Homomorfismo de grafos (es) Morphisme de graphes (fr) Homomorfismo de grafos (pt) Гомоморфизм графов (ru) Grafhomomorfi (sv) Гомоморфізм графів (uk) 圖同態 (zh)
owl:differentFrom	dbr:Homeomorphism_(graph_theory)
owl:sameAs	freebase:Graph homomorphism wikidata:Graph homomorphism dbpedia-fr:Graph homomorphism dbpedia-zh:Graph homomorphism dbpedia-pt:Graph homomorphism dbpedia-es:Graph homomorphism dbpedia-hu:Graph homomorphism dbpedia-fa:Graph homomorphism dbpedia-ru:Graph homomorphism dbpedia-sv:Graph homomorphism dbpedia-vi:Graph homomorphism dbpedia-uk:Graph homomorphism dbpedia-global:Graph homomorphism dbr:Graph homomorphism
prov:wasDerivedFrom	wikipedia-en:Graph_homomorphism?oldid=1289628935&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Complete_graph_K7.svg wiki-commons:Special:FilePath/Groetzsch-graph.svg wiki-commons:Special:FilePath/Graph_homomorphism_into_C5.svg wiki-commons:Special:FilePath/Graph_of_non-adjacent_weekdays.svg
foaf:isPrimaryTopicOf	wikipedia-en:Graph_homomorphism
is dbo:wikiPageRedirects of	dbr:Graph_epimorphism dbr:Graph_monomorphism dbr:Homomorphism_(graph_theory) dbr:Digraph_homomorphism dbr:Digraph_morphism
is dbo:wikiPageWikiLink of	dbr:Extremal_graph_theory dbr:Jin-Yi_Cai dbr:Glossary_of_graph_theory dbr:Constraint_satisfaction_problem dbr:List_of_NP-complete_problems dbr:Graph_isomorphism dbr:Homomorphism dbr:Tensor_product dbr:Core_(graph_theory) dbr:Conceptual_graph dbr:Connectivity_(graph_theory) dbr:Free_category dbr:Jaroslav_Nešetřil dbr:Petersen_graph dbr:Global_element dbr:Tensor_product_of_graphs dbr:Graph_coloring dbr:Structure_(mathematical_logic) dbr:Homomorphism_density dbr:Václav_Chvátal dbr:Grötzsch_graph dbr:Median_graph dbr:List_of_graph_theory_topics dbr:Product_(category_theory) dbr:Graph_rewriting dbr:Beckman–Quarles_theorem dbr:Mirsky's_theorem dbr:Oriented_coloring dbr:Moser_spindle dbr:Circular_coloring dbr:Grötzsch's_theorem dbr:Gallai–Hasse–Roy–Vitaver_theorem dbr:Graphon dbr:Book_embedding dbr:Gradually_varied_surface dbr:Graph_morphism dbr:Quotient_graph dbr:Sidorenko's_conjecture dbr:Common_graph dbr:Graph_removal_lemma dbr:Pavol_Hell dbr:Hedetniemi's_conjecture dbr:Graph_epimorphism dbr:Graph_monomorphism dbr:Homomorphism_(graph_theory) dbr:Digraph_homomorphism dbr:Digraph_morphism
is owl:differentFrom of	dbr:Homeomorphism_(graph_theory)
is foaf:primaryTopic of	wikipedia-en:Graph_homomorphism