1.
Tree-independence number of ▫$P_5$▫-free graphs with no large bicliquesVáclav Blažej,
J. Pascal Gollin,
Tomáš Hons,
Tomáš Masařík,
Martin Milanič,
Paweł Rzążewski,
Ondřej Suchý,
Alexandra Wesolek, 2026, objavljeni znanstveni prispevek na konferenci
Opis: The tree-independence number of a graph is the minimum, over all tree-decompositions of the graph, of the maximum size of an independent set contained in a bag. Graph classes of bounded tree-independence number have strong structural and algorithmic properties, but the parameter can be unbounded even in quite restricted classes. In particular, the presence of an induced biclique K_{t,t} forces tree-independence number at least t. This leads to the question whether large induced bicliques are the only obstruction to bounded tree-independence number in natural hereditary classes. A conjecture of Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht states that for all positive integers s and t, {P_s,K_{t,t}}-free graphs have bounded tree-independence number. We prove this conjecture for s = 5 by showing that every {P₅,K_{t,t}}-free graph has tree-independence number at most 4t. We also obtain related bounds for the weaker parameter of independence degeneracy.
Ključne besede: tree-independence number, independence degeneracy, independence treewidth, P5-free graphs
Objavljeno v RUP: 21.09.2026; Ogledov: 275; Prenosov: 5
Celotno besedilo (1,00 MB)
Gradivo ima več datotek! Več...
