Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

Tuza's conjecture for threshold graphs

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:50:43Z
dc.abstract.enTuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average degree, including planar graphs. However, for dense graphs that are neither cliques nor 4-colorable, only asymptotic results are known. Here, we confirm the conjecture for threshold graphs, i.e. graphs that are both split graphs and cographs, and for co-chain graphs with both sides of the same size divisible by 4.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorOkrasa, Karolina
dc.contributor.authorBożyk, Łukasz
dc.contributor.authorMasařík, Tomáš
dc.contributor.authorBonamy, Marthe
dc.contributor.authorHatzel, Meike
dc.contributor.authorNovotná, Jana
dc.contributor.authorGrzesik, Andrzej
dc.date.accessioned2024-01-26T11:08:02Z
dc.date.available2024-01-26T11:08:02Z
dc.date.copyright2022-09-28
dc.date.issued2022
dc.description.accesstimeAT_PUBLICATION
dc.description.financePublikacja bezkosztowa
dc.description.number1
dc.description.versionFINAL_PUBLISHED
dc.description.volume24
dc.identifier.doi10.46298/DMTCS.7660
dc.identifier.issn1365-8050
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/123915
dc.identifier.weblinkhttps://ruj.uj.edu.pl/xmlui/handle/item/300350
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofDiscrete Mathematics and Theoretical Computer Science
dc.relation.pages1-14
dc.rightsCC-BY
dc.sciencecloudnosend
dc.titleTuza's conjecture for threshold graphs
dc.typeJournalArticle
dspace.entity.typePublication