Tuza's Conjecture for Threshold Graphs
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...
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Artigo |
| Lingua: | Inglês |
| Pubblicazione: |
Discrete Mathematics & Theoretical Computer Science
2022-08-01
|
| Serie: | Discrete Mathematics & Theoretical Computer Science |
| Soggetti: | |
| Accesso online: | https://dmtcs.episciences.org/7660/pdf |
| Tags: |
Nessun Tag, puoi essere il primo ad aggiungerne!!
|