Korina Ernjulie Manaloto, May 19, Tuesday, 6-7 PM, From One Path to Two: Full Homomorphisms and Minimal Obstructions

[Keimyung Discrete Math Seminar (계명 이산수학 세미나)]

Date and Time: May 19, Tuesday, 6-7 PM

Title: From One Path to Two: Full Homomorphisms and Minimal Obstructions

Speaker: Korina Ernjulie Manaloto, Kyungpook National University (경북대학교)

Location: Room 324

Abstract: Full homomorphisms are mappings between vertices of graphs that preserve both adjacency and non-adjacency. A minimal obstruction is a graph that does not admit a full homomorphism to a target graph H, but whose every induced subgraph does.

A structural description of the minimal obstructions to full homomorphisms to paths and cycles was given by Santiago Guzmán-Pro in "Full-homomorphisms to paths and cycles." In this talk, we extend this line of study to the case of two disjoint paths. We compare the similarities and differences between the single-path and two-path targets, and explore whether there is an efficient algorithm for enumerating minimal obstructions to full homomorphisms in this setting.