ISSN:
1439-6912
Keywords:
03 B 10
;
05 C 60
;
05 C 85
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract In this paper we show that Ω(n) variables are needed for first-order logic with counting to identify graphs onn vertices. Thek-variable language with counting is equivalent to the (k−1)-dimensional Weisfeiler-Lehman method. We thus settle a long-standing open problem. Previously it was an open question whether or not 4 variables suffice. Our lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that 3 variables suffice to identify all graphs of color class size 3, and 2 variables suffice to identify almost all graphs. Our lower bound is optimal up to multiplication by a constant becausen variables obviously suffice to identify graphs onn vertices.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01305232
Permalink