The Weisfeiler-Leman dimension of planar graphs is at most 3

The Weisfeiler-Leman dimension of planar graphs is at most 3
复制标题

DOI：
10.1145/3333003
复制
发表时间：
2017-06
期刊：
2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
影响因子：
--
通讯作者：
Sandra Kiefer;I. Ponomarenko;Pascal Schweitzer
Sandra Kiefer;I. Ponomarenko;Pascal Schweitzer
中科院分区：
其他
文献类型：
--
作者：
Sandra Kiefer;I. Ponomarenko;Pascal Schweitzer

文献摘要

相似文献

We prove that the Weisfeiler-Leman (WL) dimension of the class of all finite planar graphs is at most 3. In particular, every finite planar graph is definable in first-order logic with counting using at most 4 variables. The previously best known upper bounds for the dimension and number of variables were 14 and 15, respectively.