Geodesic
Tuza's Conjecture for Threshold Graphs
Discrete mathematics & theoretical computer science, Tome 24 (2022) no. 1.

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.46298/dmtcs.7660
Classification : 05C70 
@article{DMTCS_2022_24_1_a23,
     author = {Bonamy, Marthe and Bo\.zyk, {\L}ukasz and Grzesik, Andrzej and Hatzel, Meike and Masa\v{r}{\'\i}k, Tom\'a\v{s} and Novotn\'a, Jana and Okrasa, Karolina},
     title = {Tuza's {Conjecture} for {Threshold} {Graphs}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2022},
     doi = {10.46298/dmtcs.7660},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7660/}
}
TY  - JOUR
AU  - Bonamy, Marthe
AU  - Bożyk, Łukasz
AU  - Grzesik, Andrzej
AU  - Hatzel, Meike
AU  - Masařík, Tomáš
AU  - Novotná, Jana
AU  - Okrasa, Karolina
TI  - Tuza's Conjecture for Threshold Graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2022
VL  - 24
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7660/
DO  - 10.46298/dmtcs.7660
LA  - en
ID  - DMTCS_2022_24_1_a23
ER  - 
%0 Journal Article
%A Bonamy, Marthe
%A Bożyk, Łukasz
%A Grzesik, Andrzej
%A Hatzel, Meike
%A Masařík, Tomáš
%A Novotná, Jana
%A Okrasa, Karolina
%T Tuza's Conjecture for Threshold Graphs
%J Discrete mathematics & theoretical computer science
%D 2022
%V 24
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7660/
%R 10.46298/dmtcs.7660
%G en
%F DMTCS_2022_24_1_a23
Bonamy, Marthe; Bożyk, Łukasz; Grzesik, Andrzej; Hatzel, Meike; Masařík, Tomáš; Novotná, Jana; Okrasa, Karolina. Tuza's Conjecture for Threshold Graphs. Discrete mathematics & theoretical computer science, Tome 24 (2022) no. 1. doi : 10.46298/dmtcs.7660. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7660/

Cité par Sources :