  Solving the algebraic dichotomy conjecture for constraint satisfaction
problems over structures first-order definable in countably infinite finitely
bounded homogeneous structures requires understanding the applicability of
local-consistency methods in this setting. We study the amount of consistency
(measured by relational width) needed to solve CSP for first-order expansions S
of countably infinite homogeneous graphs that additionally have bounded strict
width, i.e., for which establishing local consistency of an instance of the CSP
not only decides if there is a solution but also ensures that every solution
may be obtained from a locally consistent instance by greedily assigning values
to variables, without backtracking.
  Our main result is that the structures S under consideration have relational
width exactly (2, L) where L is the maximal size of a forbidden subgraph of a
homogeneous graph under consideration, but not smaller than 3. It beats the
upper bound (2m, 3m) where m = max(arity(S)+1, L, 3) and arity(S) is the
largest arity of a relation in S, which follows from a sufficient condition
implying bounded relational width from the literature. Since L may be
arbitrarily large, our result contrasts the collapse of the relational bounded
width hierarchy for finite structures , whose relational width, if finite, is
always at most (2,3).
