The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw

Ilia Ponomarenko, Grigory Ryabov

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

A graph X is said to be chordal bipartite if it is bipartite and contains no induced cycle of length at least 6. It is proved that if X does not contain bipartite claw as an induced subgraph, then the Weisfeiler–Leman dimension of X is at most 3. This implies that the Weisfeiler–Leman dimension of any bipartite permutation graph is at most 3. The proof is based on the theory of coherent configurations.

Язык оригиналаанглийский
ЖурналGraphs and Combinatorics
DOI
СостояниеОпубликовано - мар 2021

Предметные области OECD FOS+WOS

  • 1.02 КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ
  • 1.01 МАТЕМАТИКА

Fingerprint Подробные сведения о темах исследования «The Weisfeiler–Leman Dimension of Chordal Bipartite Graphs Without Bipartite Claw». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать