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/}
}
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/