Combinatorics · arXiv:2105.09871 v3 · submitted 20 May 2021
Tuza's Conjecture for Threshold Graphs
The paper says
“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.”
from the abstract · picked out as the main claim by a classifier
Reviews
Reviews by people
No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.
The paper
Abstract
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.
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.
abstract compiled · 2026-09-23 · no language-model review
How the main claim is stated: asserted 1.00
What the abstract itself states, as probabilities: claims first 0.08 · states limitation 0.29 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.69 · compares with prior results 0.86 · mentions code or data availability 0.02
The abstract, sentence by sentence
This table labels the abstract only (arXiv listing abstract v3). The number is the probability the classifier gave the label.
| Sentence | Role | The authors' own work | States the main conclusion | Strength |
|---|---|---|---|---|
| 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. | background 1.00 | 0.02 | 0.03 | speculative 0.55 |
| The conjecture holds for graphs with small treewidth or small maximum average degree, including planar graphs. | background 1.00 | 0.05 | 0.02 | asserted 1.00 |
| However, for dense graphs that are neither cliques nor 4-colorable, only asymptotic results are known. | gap 0.91 | 0.04 | 0.02 | asserted 1.00 |
| 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. | contribution 0.67 | 0.96 | 0.97 | asserted 1.00 |
What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 0.99
What was examined, and what was not
Sources read
- arXiv listing abstract v3
Not examined
- full text
- figures and tables
- references and citing sentences
- relations to other papers
Levels run
- P abstract
Not run
- S sections
- T body sentences
- C citations
- R cross-paper relations
How the labels were made
Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 3,638 input tokens.
Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON
Cited by 1 Pith paper
Reviewed papers on Pith that cite this one. The full citation record
Challenges and discussion
Know something about this paper? Leave a comment.
Come back by email
A short list of the week's newly reviewed papers. Nothing is sent until you confirm from your inbox, and every email has a link that stops it. No account.
No comments yet.
Sign in to comment