Teschner's conjecture on the upper bondage number of critical graphs

About 16 years old · traced to 2010

Let $\mathcal{P} \subseteq \mathcal{G}$ be additive and hereditary. A graph $G$ is vertex- $\gamma_{\mathcal{P}}$ -critical if its vertex domination number with respect to $\mathcal{P}$ has the criticality property used in the paper, and let $b_{\mathcal{P}}^+(G)$ denote its upper bondage number and $\Delta(G)$ its maximum degree. Teschner's conjecture. For any vertex- $\gamma_{\mathcal{P}}$ -critical graph $G$ ,

b_{\mathcal{P}}^+(G) \leq 1.5\Delta(G).

The conjecture is presented as the main outstanding conjecture on the ordinary bondage number when $\mathcal{P}=\mathcal{G}$ ; its general status is not resolved in the supplied source.

References

Primary source

Vladimir Samodivkin, “Changing of the domination number of a graph: edge multisubdivision and edge removal”, arXiv:1502.06245 (2015).

Additional references

3 papers in this index state this conjecture (2010–2015). The statement above is taken from the most recent of them; the others are arXiv:1204.4010, arXiv:1012.4117.

Posted 1 month ago · edited 3 weeks ago

Progress summary

Refreshed 3 weeks ago

Claimed solved

A listing claims a counterexample to the conjecture, but the claim has not been substantiated or verified.

Teschner’s ordinary conjecture, proposed in 1995, asks whether the bondage number is at most $1.5$ times the maximum degree; the stated property-relative version asks the same for $b_{\mathcal{P}}^+(G)$ .

Known results

Teschner (1993) disproved $b(G) \leq \Delta(G)+1$ using $K_3 \square K_3$ .
Hartnell–Rall and Teschner independently obtained equality $b(K_n \square K_n)=1.5\Delta(K_n \square K_n)$ for $n \geq 3$ .
Kang and Yuan (2000) proved $b(G) \leq \min\{\Delta(G)+2,8\}$ for planar graphs.
Samodivkin (2013) extended bondage results to nondegenerate graph properties.

Undated claimed counterexample

A listing titled “A Counterexample to Teschner's Bondage-Number Conjecture” claims a resolution by refutation. The supplied material gives no authors, argument, publication date, or verification, so this remains an unconfirmed claim.

Current status (as of September 2026): The conjecture has an unverified claimed counterexample, but no substantiated proof or counterexample is recorded; its truth therefore remains open.

Sources

No solutions have been posted yet.