9
$\begingroup$

I have a short paper I'm working on where I prove:

Theorem: Every graph on (2t-1) vertices with no (t+1)-clique has a vertex that is contained in every t-clique.

By "t-clique", I mean a complete subgraph with t vertices. It's actually a lemma for the main result in the paper, but it's where most of the work is done. It feels like something that has been done before, but I haven't come up with anything in my searches. I think it might be related to clique graphs or clique-helly graphs, but I haven't found a direct link.

Does anyone know of a paper with this result? Or another result that would imply this one? Or at least a related paper that might be worth looking into? Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
11
$\begingroup$

Hajnal's Clique Collection Lemma implies your theorem. See Corollary 2.10 from this paper http://arxiv.org/pdf/1101.4564v5.pdf or Hajnal's original paper http://cms.math.ca/cjm/v17/cjm1965v17.0720-0724.pdf .

Improve this answer
$\endgroup$
2
  • $\begingroup$ So much for that paper I was working on. But thanks -- That's exactly the sort of thing I thought might be out there, and very quick response too. $\endgroup$
    – Tyler Seacrest
    Commented Aug 15, 2014 at 2:45
  • $\begingroup$ +1ed. Welcome to MO! I am glad you exist now. $\endgroup$
    – Tony Huynh
    Commented Aug 15, 2014 at 3:04

You must log in to answer this question.

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