Noyau des graphes

Les preuves de les propositions, Corollary et Theorem suivantes: Proposition 2.1 If G is a core, then every endomorphism of G is an automorphism Proposition 2.2 Every homomorphism equivalence class contains a unique core (up to isomorphism). Proposition 2.3 Any graph has a unique core (up to isomorphism). Proposition 2.4 A graph G is a core if and only if every endomorphism of G is an automorphism. Proposition 2.5 If the clique number and chromatic number of G are both equal to k, then the core of G is Kk. Proposition 2.6 If G is vertex-transitive then so is its core. Proposition 2.7 The core of an edge-transitive graph is edge-transitive; the same is true for arc-transitivity and for (ordered or unordered) cliquetransitivity. Proposition 2.8 The connected components of a core are cores of classes forming an antichain in the homomorphism order. Conversely, if {G1, . . . ,Gr} is an antichain of cores, then the disjoint union of these graphs is a core. Corollary 2.9 The core of a vertex-transitive graph is connected. Theorem 3.1 (Lov´asz) Let G and G0 be finite graphs, and suppose that | Hom(F,G)| = | Hom(F,G0)| for all finite graphs F. Then G = G0.