FOM: n-colorable graphs & first order logic

Lucas Wiman lrwiman at
Mon Jun 24 22:00:07 EDT 2002


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

More information about the FOM mailing list