Full-homomorphisms to paths and cycles
Research output: Contribution to journal › Research article › Contributed › peer-review
Contributors
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
Original language | English |
---|---|
Article number | 113800 |
Journal | Discrete Mathematics |
Volume | 347 |
Issue number | 3 |
Publication status | Published - Mar 2024 |
Peer-reviewed | Yes |
Externally published | Yes |
Keywords
ASJC Scopus subject areas
Keywords
- Full H-colouring, Full-homomorphism, Minimal obstructions, Point-determining graphs