- Tytuł:
- Homomorphic Preimages of Geometric Paths
- Autorzy:
- Cockburn, Sally
- Powiązania:
- https://bibliotekanauki.pl/articles/31342316.pdf
- Data publikacji:
- 2018-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
geometric graphs
graph homomorphisms - Opis:
- 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 \rightarrow H $. A geometric graph $ \overline{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) $ \overline{G} \rightarrow \overline{H} $ is a graph homomorphism (respectively, isomorphism) that preserves edge crossings (respectively, and non-crossings). The homomorphism poset \( \mathcal{G} \) 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 $ \overline{G} $ is \( \mathcal{H} \)-colorable if $ \overline{G} \rightarrow \overline{H} $ for some \( \overline{H} \in \mathcal{H} \). In this paper, we provide necessary and sufficient conditions for $ \overline{G} $ to be \( \mathcal{P}_n \)-colorable for $ n \ge 2 $. Along the way, we also provide necessary and sufficient conditions for $ \overline{G} $ to be \( \mathcal{K}_{2,3} \)-colorable.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2018, 38, 2; 553-571
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł