Homomorphic Preimages of Geometric Cycles
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2015
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909221783601152 |
|---|---|
| author | Cockburn, Sally |
| author_facet | Cockburn, Sally |
| contents | A graph G is a homomorphic preimage of another graph H, or equivalently G is H-colorable, if there exists a graph homomorphism from G to H. A classic problem is to characterize the family of homomorphic preimages of a given graph H. A geometric graph is a simple graph G together with a straight line drawing of G in the plane with the vertices in general position. A geometric homomorphism (resp. isomorphism) is a graph homomorphism (resp. isomorphism) that preserves edge crossings (resp. and non-crossings). The homomorphism posetof a graph G is the set of isomorphism classes of geometric realizations of G partially ordered by the existence of injective geometric homomorphisms. A geometric graph G is H-colorable if there is a geometric homomorphism from G to some element of the homomorphism poset of H. We provide necessary and sufficient conditions for a geometric graph to be C_n-colorable for n less than 6. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1507_02758 |
| institution | arXiv |
| publishDate | 2015 |
| record_format | arxiv |
| spellingShingle | Homomorphic Preimages of Geometric Cycles Cockburn, Sally Combinatorics 05C60, 05C62 A graph G is a homomorphic preimage of another graph H, or equivalently G is H-colorable, if there exists a graph homomorphism from G to H. A classic problem is to characterize the family of homomorphic preimages of a given graph H. A geometric graph is a simple graph G together with a straight line drawing of G in the plane with the vertices in general position. A geometric homomorphism (resp. isomorphism) is a graph homomorphism (resp. isomorphism) that preserves edge crossings (resp. and non-crossings). The homomorphism posetof a graph G is the set of isomorphism classes of geometric realizations of G partially ordered by the existence of injective geometric homomorphisms. A geometric graph G is H-colorable if there is a geometric homomorphism from G to some element of the homomorphism poset of H. We provide necessary and sufficient conditions for a geometric graph to be C_n-colorable for n less than 6. |
| title | Homomorphic Preimages of Geometric Cycles |
| topic | Combinatorics 05C60, 05C62 |
| url | https://arxiv.org/abs/1507.02758 |