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/

[1] D.L. Boutin and S. Cockburn, Geometric graph homomorphisms, J. Graph Theory 69 (2012) 97–113. doi:10.1002/jgt.20566

[2] D.L. Boutin, S. Cockburn, A.M. Dean and A.M. Margea, Posets of geometric graphs, Ars Math. Contemp. 5 (2012) 269–288.

[3] S. Cockburn, The homomorphism poset of K3,3, (2013). arxiv: 1306.5732

[4] S. Cockburn, Homomorphism preimages of geometric cycles, J. Combin.Math. Combin. Comput., to appear.

[5] S. Cockburn and Y. Song, The homomorphism poset of K2,n, Australas. J. Combin. 57 (2013) 79–108.

[6] H.Harborth, Parity of numbers of crossings for complete n-partite graphs, Math. Slovaca 26 (1976) 77–95.

[7] P. Hell and J. Nešetřil, Graphs and Homomorphisms (Oxford University Press, Oxford, 2004). doi:10.1093/acprof:oso/9780198528173.001.0001

[8] P. Hell and J. Nešetřil, On the complexity of H-coloring, J. Combin. Theory Ser. B 48 (1990) 92–110. doi:10.1016/0095-8956(90)90132-J

[9] P. Hell, H. Zhou and X. Zhu, Homomorphisms to oriented cycles, Combinatorica 13 (1993) 421–433. doi:10.1007/BF01303514

[10] P. Hell, H. Zhou and X. Zhu, On homomorphisms to acyclic local tournaments, J. Graph Theory 20 (1995) 467–471. doi:10.1002/jgt.3190200410

[11] P. Hell and X. Zhu, Homomorphisms to oriented paths, Discrete Math. 132 (1994) 107–114. doi:10.1016/0012-365X(94)90235-6

[12] P. Hell and X. Zhu, The existence of homomorphisms to oriented cycles, SIAM J. Discrete Math. 8 (1995) 208–222. doi:10.1137/S0895480192239992

[13] H.A. Maurer, A. Salomaa and D.Wood, Colorings and interpretations: a connection between graphs and grammar forms, Discrete Appl. Math. 3 (1981) 119–135. doi:10.1016/0166-218X(81)90037-8

[14] H. Zhou, Characterization of the homomorphic preimages of certain oriented cycles, SIAM J. Discrete Math. 6 (1993) 87–99. doi:10.1137/0406007