FOM: n-colorable graphs & first order logic
lrwiman at ilstu.edu
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,
More information about the FOM