Full-homomorphisms to paths and cycles
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
Abstract
A full-homomorphism between a pair of graphs is a vertex mapping that preserves adjacencies and non-adjacencies. For a fixed graph H, a full H-colouring is a full-homomorphism of G to H. A minimal H-obstruction is a graph that does not admit a full H-colouring, such that every proper induced subgraph of G admits a full H-colouring. Feder and Hell proved that for every graph H there is a finite number of minimal H-obstructions. We begin this work by describing all minimal obstructions of paths. Then, we study minimal obstructions of regular graphs to propose a description of minimal obstructions of cycles. As a consequence of these results, we observe that for each path P and each cycle C, the number of minimal P-obstructions and C-obstructions is O(|V(P)|2) and O(|V(C)|2), respectively. Finally, we propose some problems regarding the largest minimal H-obstructions, and the number of minimal H-obstructions.
Details
| Originalsprache | Englisch |
|---|---|
| Aufsatznummer | 113800 |
| Fachzeitschrift | Discrete Mathematics |
| Jahrgang | 347 |
| Ausgabenummer | 3 |
| Publikationsstatus | Veröffentlicht - März 2024 |
| Peer-Review-Status | Ja |
| Extern publiziert | Ja |
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- Full H-colouring, Full-homomorphism, Minimal obstructions, Point-determining graphs