2
$\begingroup$

Consider the graph formed by $k$ cliques of order $k$, any two cliques sharing at most one point in common. Now, by Szekeres-Wilf theorem, I think the graph should be $k$ colorable, as any connected induced subgraph would have at least one vertex with degree $k-1$(for otherwise, the number of cliques would exceed $k$).

Any counterexamples in this case? Thanks beforehand.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ The problem you are asking is exactly the Erdos-Fabeb-Lovasz Conjecture. $\endgroup$
    – LeechLattice
    Commented Jun 25, 2019 at 10:01
  • $\begingroup$ @Bullet51 yes, so where is my argument wrong? $\endgroup$
    – vidyarthi
    Commented Jun 25, 2019 at 10:02
  • 2
    $\begingroup$ Interesting, this is the second time you ask the question about this problem (that I know of), although this time you tried to solve it in a different way. Here is something you could try if you are interested in solving this problem. Try extending the concept of a Kierstead path to simple hypergraphs. This requires careful thought, and it might not even be possible in any really useful way. $\endgroup$
    – EGME
    Commented Jun 25, 2019 at 18:22
  • 1
    $\begingroup$ After doing that, you would try to prove a hypergraph analogue of Vizing’s theorem. If you do that, you solve the problem. It is conjectured. $\endgroup$
    – EGME
    Commented Jun 25, 2019 at 20:50

1 Answer 1

Reset to default
3
$\begingroup$

Let $k=5$. Then there is a graph $G$ such that:

  1. $G$ is formed by $5$ cliques of order $5$, with any two cliques sharing at most one point in common.
  2. $G$ has an induced subgraph $H$ such that every vertex in $H$ has degree at least $5$ in $H$.

So for this example, the Szekeres-Wilf Theorem cannot be used to show that $G$ is $5$-colorable.

Here is the example:

enter image description here

I've drawn five pentagons, three in black, one red, and one blue. Any two pentagons share at most one point in common. Let $G$ be the graph obtained by filling in the rest of the edges to that the pentagons become cliques of order $5$. Let $H$ be subgraph induced on the nine green vertices. Every vertex in $H$ has degree at least $5$ in $H$.

EDIT: Here is a picture of the induced graph $H$. I think I got all the edges, but there are at least enough to show that every vertex in $H$ has degree at least $5$.

enter image description here

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks, can we give a smaller counterexample? $\endgroup$
    – vidyarthi
    Commented Jun 25, 2019 at 15:43
  • $\begingroup$ But the induced subgraph formed by those very vertices will not have at least $5$ degree, because, when we remove those nine vertices, their adjacency will be only with respect to those nine vertices, but their adjacency with respect to other vertices(in the clique of which they are a part of) will not be there right? $\endgroup$
    – vidyarthi
    Commented Jun 25, 2019 at 15:47
  • $\begingroup$ @vidyarthi Each of the green vertices is connected to at least 5 other green vertices (once we account for all of the edges in the cliques that I haven't drawn). Is this what you are asking? $\endgroup$
    – Gabe Conant
    Commented Jun 25, 2019 at 15:51
  • $\begingroup$ It is clearly seen that there are many green vertices which do not have five degree. Could you draw the nine vertex subgraph outside for more specificity $\endgroup$
    – vidyarthi
    Commented Jun 25, 2019 at 15:57
  • 1
    $\begingroup$ @vidyarthi I added a picture of $H$. The intuition behind your idea was that there couldn't be a subgraph of $G$ consisting only of vertices that join two of the cliques. This seems reasonable for $k=3$ or $k=4$, or in the case that the cliques don't "intertwine" too much (e.g., if $G$ is planar like in Wikipedia article for the conjecture). But for $k=5$ there is enough room to allow the cliques to intertwine enough. Combined with the guess that there wouldn't be such an easy proof of a $500 Erdos problem, the only thing left to do was a brute force drawing. $\endgroup$
    – Gabe Conant
    Commented Jun 25, 2019 at 16:15

You must log in to answer this question.

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