pipette
ENEnglish

Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number

Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S, Daniel Lokshtanov, Ilya Maier

Preprint

En palabras de los autores

A three-path-configuration is a graph consisting of three pairwise internally vertex-disjoint paths, the union of every two of which is an induced cycle of length at least four. A graph is 3PC-free if no induced subgraph of it is a three-path-configuration. We show that 3PC-free graphs have logarithmic tree-independence number, which is asymptotically best possible.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 22 de octubre. arXiv. Preprint, todavía sin revisión por pares.