Odd-angulated graphs and cancelling factors in box products

✍ Scribed by Zhongyuan Che; Karen L. Collins; Claude Tardif

• Book ID: 102345806
• Publisher: John Wiley and Sons
• Year: 2008
• Tongue: English
• Weight: 205 KB
• Volume: 58
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20307

✦ Synopsis

Abstract

Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2__k__ + 1. We say that G is (2__k__ + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2__k__ + 1)‐cycle. We call G strongly (2__k__ + 1)‐angulated if every two vertices are connected by a sequence of (2__k__ + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2__k__ + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2__k__ + 1, and ϕ: G□ H→S□T is a graph homomorphism, then either ϕ maps G□{h} to S□{t~h~} for all h∈V(H) where t~h~∈V(T) depends on h; or ϕ maps G□{h} to {s~h~}□ T for all h∈V(H) where s~h~∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008