Paper Info
Title
On realizations of point determining graphs, and obstructions to full homomorphisms
Abstract
graph is point determining if distinct vertices have distinct neighbourhoods. A realization of a point determining graph H is a point determining graph G such that each vertex-removed subgraph G-x which is point determining, is isomorphic to H. We study the fine structure of point determining graphs, and conclude that every point determining graph has at most two realizations. A full homomorphism of a graph G to a graph H is a vertex mapping f such that for distinct vertices u and v of G, we have uv an edge of G if and only if f(u)f(v) is an edge of H. For a fixed graph H, a full H-colouring of G is a full homomorphism of G to H. A minimal H-obstruction is a graph G which does not admit a full H-colouring, such that each proper induced subgraph of G admits a full H-colouring. We analyse minimal H-obstructions using our results on point determining graphs. We connect the two problems by proving that if H has k vertices, then a graph with k+1 vertices is a minimal H-obstruction if and only if it is a realization of H. We conclude that every minimal H-obstruction has at most k+1 vertices, and there are at most two minimal H-obstructions with k+1 vertices. We also consider full homomorphisms to graphs H in which loops are allowed. If H has @? loops and k vertices without loops, then every minimal H-obstruction has at most (k+1)(@?+1) vertices, and, when both k and @? are positive, there is at most one minimal H-obstruction with (k+1)(@?+1) vertices. In particular, this yields a finite forbidden subgraph characterization of full H-colourability, for any graph H with loops allowed.
Year
DOI
Venue
2008
10.1016/j.disc.2006.11.026
Discrete Mathematics
Keywords
Field
DocType
forbidden subgraph characterizations,full homomorphisms,point determining graphs,polynomial algorithms,fine structure
Discrete mathematics,Combinatorics,Graph toughness,Graph power,Bound graph,Graph homomorphism,Cycle graph,Neighbourhood (graph theory),Factor-critical graph,Mathematics,Complement graph
Journal
Volume
Issue
ISSN
308
9
Discrete Mathematics
Citations 
PageRank 
References 
15
0.93
10
Authors
2
Name
Order
Citations
PageRank
Tomás Feder11959184.99
Pavol Hell22638288.75