Back to Search Start Over

ON THE WEISFEILER-LEMAN DIMENSION OF PERMUTATION GRAPHS.

Authors :
JIN GUO
GAVRILYUK, ALEXANDER L.
PONOMARENKO, ILIA
Source :
SIAM Journal on Discrete Mathematics. 2024, Vol. 38 Issue 2, p1915-1929. 15p.
Publication Year :
2024

Abstract

It is proved that the Weisfeiler-Leman dimension of the class of permutation graphs is at most 18. Previously, it was only known that this dimension is finite (B. Grußien, Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017, pp. 1-12). [ABSTRACT FROM AUTHOR]

Subjects

Subjects :
*COMPUTER logic
*PERMUTATIONS

Details

Language :
English
ISSN :
08954801
Volume :
38
Issue :
2
Database :
Academic Search Index
Journal :
SIAM Journal on Discrete Mathematics
Publication Type :
Academic Journal
Accession number :
178602110
Full Text :
https://doi.org/10.1137/23M1575019
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details