ENG

Iskanje po repozitoriju

A- | A+ | Natisni

Iskalni niz:	išči po
	išči po
	išči po
	išči po
Vrsta gradiva:	* po starem in bolonjskem študiju
Jezik:
Išči po:
Opcije:	Prikaži samo zadetke s celotnim besedilom
	Ponastavi

1 - 2 / 2

Tree-independence number of ▫$P_5$▫-free graphs with no large bicliques
Vá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: 300; Prenosov: 5
Celotno besedilo (1,00 MB)
Gradivo ima več datotek! Več...

Induced matching treewidth and tree-independence number, revisited
Noga Alon, Martin Milanič, Paweł Rzążewski, 2026, izvirni znanstveni članek

Opis: We study two graph parameters defined via tree decompositions: tree-independence number and induced matching treewidth. Both parameters are defined similarly as treewidth, but with respect to different measures of a tree decomposition T of a graph G: for tree-independence number, the measure is the maximum size of an independent set in G included in some bag of T, while for the induced matching treewidth, the measure is the maximum size of an induced matching in G such that some bag of T contains at least one endpoint of every edge of the matching. While the induced matching treewidth of any graph is bounded from above by its tree-independence number, the family of complete bipartite graphs shows that small induced matching treewidth does not imply small tree-independence number. On the other hand, Abrishami, Briański, Czyżewska, McCarty, Milanič, Rzążewski, and Walczak [SIAM Journal on Discrete Mathematics, 2025] showed that, if a fixed biclique K_{t,t} is excluded as an induced subghraph, then the tree-independence number is bounded from above by some function of the induced matching treewidth. The function resulting from their proof is exponential even for fixed t, as it relies on multiple applications of Ramsey’s theorem. In this note we show, using the Kövári-Sós-Turán theorem, that for any class of K_{t,t}-free graphs, the two parameters are in fact polynomially related.
Ključne besede: tree-independence number, induced matching treewidth, induced biclique, Kövári-Sós-Turán theorem
Objavljeno v RUP: 17.09.2026; Ogledov: 296; Prenosov: 6
Celotno besedilo (471,21 KB)
Gradivo ima več datotek! Več...

Iskanje izvedeno v 0.01 sek.

Na vrh