Pith.

Combinatorics · arXiv:2105.09871 v3 · submitted 20 May 2021

Tuza's Conjecture for Threshold Graphs

Marthe Bonamy, {L}ukasz Bożyk, Andrzej Grzesik, Meike Hatzel, Tomáš Masařík, Jana Novotná, Karolina Okrasa

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

Pith says

Pith has not reviewed this paper.

Get a Pith Review, $5

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.

Request a human review

How Pith checks papers · The full audit of this paper

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.

SentenceRoleThe authors' own workStates the main conclusionStrength
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

  1. Epi: Towards a Persistent, Self-Improving Agent for Autonomous Research cs.CL · Oct 2026

Challenges and discussion

Know something about this paper? Leave a comment.

No comments yet.

Sign in to comment