Canadian Mathematical Society
Canadian Mathematical Society
  location:  PublicationsjournalsCJM
Abstract view

Strongly Projective Graphs

Open Access article
 Printed: Aug 2002
  • Benoit Larose
Format:   HTML   LaTeX   MathJax   PDF   PostScript  


We introduce the notion of strongly projective graph, and characterise these graphs in terms of their neighbourhood poset. We describe certain exponential graphs associated to complete graphs and odd cycles. We extend and generalise a result of Greenwell and Lov\'asz \cite{GreLov}: if a connected graph $G$ does not admit a homomorphism to $K$, where $K$ is an odd cycle or a complete graph on at least 3 vertices, then the graph $G \times K^s$ admits, up to automorphisms of $K$, exactly $s$ homomorphisms to $K$.
MSC Classifications: 05C15, 06A99 show english descriptions Coloring of graphs and hypergraphs
None of the above, but in this section
05C15 - Coloring of graphs and hypergraphs
06A99 - None of the above, but in this section

© Canadian Mathematical Society, 2015 :