Simple view
Full metadata view
Authors
Statistics
Tuza's conjecture for threshold graphs
Journal
Discrete Mathematics and Theoretical Computer Science
Author
Volume
24
Issue
1
Pages
1-14
Article ID
24
ISSN
1365-8050
Language
English
Journal language
English
Abstract in English
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.
Affiliation
Wydział Matematyki i Informatyki : Instytut Matematyki
Scopus© citations
1
cris.lastimport.wos | 2024-04-09T21:54:36Z | |
dc.abstract.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. | pl |
dc.affiliation | Wydział Matematyki i Informatyki : Instytut Matematyki | pl |
dc.contributor.author | Bonamy, Marthe | pl |
dc.contributor.author | Bożyk, Łukasz | pl |
dc.contributor.author | Grzesik, Andrzej - 104622 | pl |
dc.contributor.author | Hatzel, Meike | pl |
dc.contributor.author | Masařík, Tomáš | pl |
dc.contributor.author | Novotná, Jana | pl |
dc.contributor.author | Okrasa, Karolina | pl |
dc.date.accessioned | 2022-09-28T07:42:20Z | |
dc.date.available | 2022-09-28T07:42:20Z | |
dc.date.issued | 2022 | pl |
dc.date.openaccess | 0 | |
dc.description.accesstime | w momencie opublikowania | |
dc.description.number | 1 | pl |
dc.description.physical | 1-14 | pl |
dc.description.version | ostateczna wersja wydawcy | |
dc.description.volume | 24 | pl |
dc.identifier.articleid | 24 | pl |
dc.identifier.doi | 10.46298/dmtcs.7660 | pl |
dc.identifier.issn | 1365-8050 | |
dc.identifier.uri | https://ruj.uj.edu.pl/xmlui/handle/item/300350 | |
dc.language | eng | pl |
dc.language.container | eng | pl |
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.subtype | Article | pl |
dc.title | Tuza's conjecture for threshold graphs | pl |
dc.title.journal | Discrete Mathematics and Theoretical Computer Science | |
dc.type | JournalArticle | pl |
dspace.entity.type | Publication |
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
Wydział Matematyki i Informatyki
Grzesik, Andrzej
No affiliation
Bonamy, Marthe
Bożyk, Łukasz
Hatzel, Meike
Masařík, Tomáš
Novotná, Jana
Okrasa, Karolina
* 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
Open Access
Loading...