Show that in a graph $G$ where every two different edges are connected (i.e there is an edge incident with both) we have that $\delta<\omega+{\omega \choose 2}$ where $\delta$ is the min degree and $\omega$ is the clique number.

It looks like it should some kind of combinatoric argument where we get a larger clique by contradiction.

Note that the original question was to show that in a graph $G$ where every two different edges are connected (i.e there is an edge incident with both) we have that $\chi \le \omega+{\omega \choose 2}$, and what I did was assume by negation that this wasn't true and found a subgraph with min degree at least that, looking to find a contradiction. It looks to me like it should be a valid direction with some kind of combinatoric argument as mentioned, however I just can't find one.



If $G=K_{n,n}$ where $n\ge3$ then for any two edges there is a third edge incident with both, and $\delta=n\ge3=\omega+\binom\omega2.$

Here's how to prove $\chi\le\omega+\binom\omega2$.

Choose $W\subseteq V(G)$ so that $W$ is the vertex set of a maximum clique, $|W|=\omega$. We can define a proper coloring $f:V(G)\to\binom W1\cup\binom W2$ as follows. Consider any vertex $v\in V(G)$. By the maximality of $W$ we have $W\not\subseteq N(v)$, i.e., $|W\setminus N(v)|\ge1$. If $|W\setminus N(v)|=1$ let $f(v)=W\setminus N(v)$. If $|W\setminus N(v)|\ge2$ choose $f(v)\subseteq W\setminus N(v)$ with $|f(v)|=2$. We have to show that $f$ is a proper coloring; i.e., we show that vertices of the same color can not be adjacent.

First, suppose $f(u)=f(v)=\{w\}\in\binom W1$. If $u,v$ were adjacent, then $(W\setminus\{w\})\cup\{u,v\}$ would induce a clique of order $\omega+1$, which is absurd.

Second, suppose $f(u)=f(v)=\{w,x\}\in\binom W2$. If $u,v$ were adjacent, then we would have two edges $uv$ and $wx$ and no edge incident with both of them, contradicting the assumption that any two edges are "connected".

  • $\begingroup$ Does this answer your question, or do you also want a hint towards proving $\chi\le\omega+\binom\omega2$? $\endgroup$ – bof Feb 12 '15 at 13:07
  • $\begingroup$ Yeah, so I guess my direction was incorrect so I need a hint towards that. $\endgroup$ – ctlaltdefeat Feb 12 '15 at 13:32
  • $\begingroup$ Looks good though I'll look at it more closely later. Is there some insight you could give me regarding these types of problems about when I should look to construct an explicit coloring vs when I should "just" treat $\chi$ as some indicator to the density of the graph? $\endgroup$ – ctlaltdefeat Feb 12 '15 at 16:54
  • $\begingroup$ I guess I'd try for an explicit coloring every time, because that's how my mind works, simple and straightforward. If something more devious is needed, I'm just going to be stuck. Actually, I don't understand what you mean by "treat $\chi$ as some indicator to the density of the graph:, $\endgroup$ – bof Feb 13 '15 at 7:42
  • $\begingroup$ For example in math.stackexchange.com/questions/619988/…, you reached a conclusion about $\chi$ by showing that if it was too big then $\delta$ of a subgraph would be too big, without there being any coloring at all. That type of argument doesn't work here, as you've pointed out. $\endgroup$ – ctlaltdefeat Feb 13 '15 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.