Full-homomorphisms to paths and cycles

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

  • Santiago Guzmán-Pro - , Universidad Nacional Autónoma de México (Author)

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 languageEnglish
Article number113800
JournalDiscrete Mathematics
Volume347
Issue number3
Publication statusPublished - Mar 2024
Peer-reviewedYes
Externally publishedYes

Keywords

Keywords

  • Full H-colouring, Full-homomorphism, Minimal obstructions, Point-determining graphs