8
$\begingroup$

In Zsolt Tuza's Unsolved combinatorial problems I, Problem 46 is the following conjecture:

Let $G$ be a graph on $n$ vertices. Let $\alpha_1$ be the maximum number of edges of $G$ such that every triangle in $G$ contains at most one of these edges. Let $\tau_1$ be the minimum number of edges of $G$ such that every triangle in $G$ contains at least one of these edges. Then, it is conjectured that $\alpha_1+\tau_1 \leq \dfrac{n^2}{4}$.

The reference given is Paul Erdös, Tibor Gallai, Zsolt Tuza, Covering and independence in triangle structures, Discrete Mathematics 150 (1996) pp. 89-101. However, in this reference, the conjecture is only formulated (Conjecture 11) for the case when $G$ is a triangular graph (i. e., every edge of $G$ is contained in a triangle). Maybe I am missing something completely obvious, but is this really equivalent, or did Tuza extend his conjecture after this publication? Or is one of the statements wrong resp. mistakenly specialized? (Note that the conjecture for generic $G$ clearly generalizes Turan's theorem for $K_3$'s, but in the triangular case I don't see how it yields Turan.)

(Also, are there any news on this question?)

Improve this question
$\endgroup$
2
  • $\begingroup$ Erdos does the same here journals.cambridge.org/action/… He gives the conjecture for general graphs but only references the article on triangular graphs. $\endgroup$
    – Gjergji Zaimi
    Commented Feb 3, 2012 at 22:35
  • $\begingroup$ Both versions seem ok, so I'm guessing they generalized it on purpose. $\endgroup$
    – Brendan McKay
    Commented Feb 4, 2012 at 7:49

1 Answer 1

Reset to default
9
$\begingroup$

I hope I am not violating any kind of MathOverflow etiquette by responding to a question 2 years after it has been asked, but your question is answered in the following preprint of mine that just hit the arXiv: http://arxiv.org/abs/1408.5176

The preprint shows that any vertex-minimal counterexample to the Erdős--Gallai--Tuza Conjecture has minimum degree greater than n/2; in particular, such graphs are triangular. Thus, the "triangular" version and the unrestricted version are equivalent.

The proof is not difficult, but (at the risk of flattering myself) I don't think it is entirely trivial either.

Improve this answer
$\endgroup$
4
  • 5
    $\begingroup$ This is definitely not a violation of etiquette. $\endgroup$
    – Gerry Myerson
    Commented Aug 25, 2014 at 5:47
  • $\begingroup$ Very nice argument! (Just in case you are still going to edit the paper: I don't see why you require "nonempty proper" as early as in Lemma 2.1, and I wouldn't refer to (1) as "equation".) $\endgroup$
    – darij grinberg
    Commented Aug 25, 2014 at 9:07
  • $\begingroup$ @darijgrinberg: Thanks for your comments! Point taken regarding (1). As far as Lemma 2.1 goes, nothing is really gained by allowing S to be empty or to be all of V(G) (this only yields f_1(G) <= f_1(G) ). It seems a hair simpler to just keep the same hypothesis as Corollary 2.2, where the condition really is needed. $\endgroup$
    – Gregory J. Puleo
    Commented Aug 25, 2014 at 14:56
  • $\begingroup$ My problem with useless conditions is that I keep searching for the place where they are used in the proof, which tends to confuse me if they are not. But this proof is so clear that it doesn't really matter. $\endgroup$
    – darij grinberg
    Commented Aug 25, 2014 at 16:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .