Tuza's conjecture for threshold graphs

2022
journal article
article
1
cris.lastimport.wos2024-04-09T21:54:36Z
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.pl
dc.affiliationWydział Matematyki i Informatyki : Instytut Matematykipl
dc.contributor.authorBonamy, Marthepl
dc.contributor.authorBożyk, Łukaszpl
dc.contributor.authorGrzesik, Andrzej - 104622 pl
dc.contributor.authorHatzel, Meikepl
dc.contributor.authorMasařík, Tomášpl
dc.contributor.authorNovotná, Janapl
dc.contributor.authorOkrasa, Karolinapl
dc.date.accessioned2022-09-28T07:42:20Z
dc.date.available2022-09-28T07:42:20Z
dc.date.issued2022pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.number1pl
dc.description.physical1-14pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume24pl
dc.identifier.articleid24pl
dc.identifier.doi10.46298/dmtcs.7660pl
dc.identifier.issn1365-8050
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/300350
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa*
dc.rights.licenceCC-BY
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/legalcode.pl*
dc.share.typeotwarte czasopismo
dc.subtypeArticlepl
dc.titleTuza's conjecture for threshold graphspl
dc.title.journalDiscrete Mathematics and Theoretical Computer Science
dc.typeJournalArticlepl
dspace.entity.typePublication
cris.lastimport.wos
2024-04-09T21:54:36Z
dc.abstract.enpl
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.
dc.affiliationpl
Wydział Matematyki i Informatyki : Instytut Matematyki
dc.contributor.authorpl
Bonamy, Marthe
dc.contributor.authorpl
Bożyk, Łukasz
dc.contributor.authorpl
Grzesik, Andrzej - 104622
dc.contributor.authorpl
Hatzel, Meike
dc.contributor.authorpl
Masařík, Tomáš
dc.contributor.authorpl
Novotná, Jana
dc.contributor.authorpl
Okrasa, Karolina
dc.date.accessioned
2022-09-28T07:42:20Z
dc.date.available
2022-09-28T07:42:20Z
dc.date.issuedpl
2022
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.numberpl
1
dc.description.physicalpl
1-14
dc.description.version
ostateczna wersja wydawcy
dc.description.volumepl
24
dc.identifier.articleidpl
24
dc.identifier.doipl
10.46298/dmtcs.7660
dc.identifier.issn
1365-8050
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/300350
dc.languagepl
eng
dc.language.containerpl
eng
dc.rights*
Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa
dc.rights.licence
CC-BY
dc.rights.uri*
http://creativecommons.org/licenses/by/4.0/legalcode.pl
dc.share.type
otwarte czasopismo
dc.subtypepl
Article
dc.titlepl
Tuza's conjecture for threshold graphs
dc.title.journal
Discrete Mathematics and Theoretical Computer Science
dc.typepl
JournalArticle
dspace.entity.type
Publication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
8
Views per month
Views per city
Krakow
1
Warsaw
1
Downloads
grzesik_et-al_tuzas_conjecture_for_threshold_graphs_2022.pdf
18
grzesik_et-al_tuzas_conjecture_for_threshold_graphs_2022.odt
4