Treewidth and the Product of Tree-Independence and Tree-Chromatic Numbers
En palabras de los autores
For a graph , let , , and denote its treewidth, tree-independence number, and tree-chromatic number, respectively. We prove that every nonempty graph satisfies . This improves the quadratic bound of Koutsoutis, Krause, Liu, Redzic, and Ueckerdt. For every pair of integers , we construct a graph with , , and . Thus the upper bound is best possible up to a constant factor.
Resultado principalEl resumen no menciona limitaciones.
Apareció: jueves, 15 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 8 pages