FOM: n-colorable graphs & first order logic

[Lucas Wiman]

Hi,

I think I've shown that the predicate "... has chromatic number at least 
n" is not first-order definable in the language of graphs (it's not hard 
using Fraisse games, but I'm not too confident in my abilities).  Of 
course this is definable in a the second order language, but I would 
like a language where I can use the compactness theorem.  Is there a 
fragment of the second order language of graphs in which this predicate 
is definable, but where the compactness theorem holds?

Perhaps more to the point, can anyone give me pointers to the literature 
of the model theory of graphs?

Thanks in advance,
Lucas Wiman