Marthe Bonamy ; Łukasz Bożyk ; Andrzej Grzesik ; Meike Hatzel ; Tomáš Masařík et al. - Tuza's Conjecture for Threshold Graphs

dmtcs:7660 - Discrete Mathematics & Theoretical Computer Science, August 14, 2022, vol. 24, no. 1 - https://doi.org/10.46298/dmtcs.7660
Tuza's Conjecture for Threshold GraphsArticle

Authors: Marthe Bonamy ; Łukasz Bożyk ; Andrzej Grzesik ; Meike Hatzel ; Tomáš Masařík ORCID; Jana Novotná ; Karolina Okrasa ORCID

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.

Comment: 14 pages, 11 figures, Accepted to European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB) 2021

https://doi.org/10.46298/dmtcs.7660
Source: arXiv.org:2105.09871
Volume: vol. 24, no. 1
Section: Graph Theory
Published on: August 14, 2022
Accepted on: June 3, 2022
Submitted on: July 9, 2021
Keywords: Mathematics - Combinatorics, Computer Science - Discrete Mathematics, 05C70
Licence: Attribution 4.0 International (CC BY 4.0)
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada
  • Large Discrete Structures; Funder: European Commission; Code: 648509
  • Cuts and decompositions: algorithms and combinatorial properties; Funder: European Commission; Code: 714704

Classifications

Mathematics Subject Classification 20201
Sources:
  • [1] zbMATH Open.

Share and export

Consultation statistics

This page has been seen 1026 times.
This article's PDF has been downloaded 1062 times.