Artykuł w czasopiśmie
Brak miniatury
Licencja
Tuza's conjecture for threshold graphs
Autor
Bonamy, Marthe
Hatzel, Meike
Grzesik, Andrzej
Data publikacji
2022
Abstrakt (EN)
Tuza 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.
Dyscyplina PBN
informatyka
Czasopismo
Discrete Mathematics and Theoretical Computer Science
Tom
24
Zeszyt
1
Strony od-do
1-14
ISSN
1365-8050
Data udostępnienia w otwartym dostępie
2022-09-28
Link do źródła
Licencja otwartego dostępu
Uznanie autorstwa