Geodesic
Homomorphic Preimages of Geometric Paths
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 553-571

Voir la notice de l'article provenant de la source Library of Science

A graph G is a homomorphic preimage of another graph H, or equivalently G is H-colorable, if there exists a graph homomorphism f : G → H. A geometric graph G 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 (respectively, isomorphism) G→H is a graph homomorphism (respectively, isomorphism) that preserves edge crossings (respectively, and non-crossings). The homomorphism poset 𝒢 of 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 ℋ-colorable if G→H for some H∈ℋ. In this paper, we provide necessary and sufficient conditions for G to be 𝒫_n-colorable for n ≥ 2. Along the way, we also provide necessary and sufficient conditions for G to be 𝒦_2,3-colorable.
Keywords: geometric graphs, graph homomorphisms 
@article{DMGT_2018_38_2_a15,
     author = {Cockburn, Sally},
     title = {Homomorphic {Preimages} of {Geometric} {Paths}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {553--571},
     publisher = {mathdoc},
     volume = {38},
     number = {2},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a15/}
}
TY  - JOUR
AU  - Cockburn, Sally
TI  - Homomorphic Preimages of Geometric Paths
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 553
EP  - 571
VL  - 38
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a15/
LA  - en
ID  - DMGT_2018_38_2_a15
ER  - 
%0 Journal Article
%A Cockburn, Sally
%T Homomorphic Preimages of Geometric Paths
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 553-571
%V 38
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a15/
%G en
%F DMGT_2018_38_2_a15
Cockburn, Sally. Homomorphic Preimages of Geometric Paths. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 553-571. http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a15/