Timeline for Coloring a graph formed by cliques sharing at most one point
Current License: CC BY-SA 4.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 1, 2019 at 7:43 | comment | added | vidyarthi | @EGME ..contd. This can always be done, as every vertex has one $\textit{undominated}$ (non-adjacent) (in fact $k-1$) vertex from each of the cliques that do not share that vertex (otherwise those cliques would share that vertex). Since the cliques may share a single vertex, therefore a single vertex would represent the cliques that share it. Similarly, we pick another vertex of the colored clique and again give the same color to one representative vertex from each clique, in the manner similar to the previous coloring. Any counterexamples? | |
| Jul 1, 2019 at 7:41 | comment | added | vidyarthi | @EGME I slightly modified theprocess: we consider a vertex of the clique, and, if it is shared by $m$ cliques ($m\ge0$), then we can color one vertex from $k-m$ cliques which is not dominated by the vertex ; with the same color. Thus, all cliques have one of the vertices colored with the same color. Note that the vertices colored need not be distinct, that is, if one of the $k-m$ vertices are being in turn shared by some other cliques, then we are just actually picking one vertex for all those cliques. This means we are picking each $\textit{representative}$ vertex from each distinct clique.. | |
| Apr 30, 2019 at 16:33 | comment | added | vidyarthi | @EDGE ok! thanks for your feedback | |
| Apr 30, 2019 at 16:32 | comment | added | EGME | Could we do it some other day, I am doing this and that at the same time at the moment ... I thank you for your understanding. | |
| Apr 30, 2019 at 16:31 | comment | added | vidyarthi | @EGME saw my comment in chat? | |
| Apr 30, 2019 at 16:20 | comment | added | vidyarthi | Let us continue this discussion in chat. | |
| Apr 30, 2019 at 16:17 | comment | added | EGME | Hm, I don’t see why that would necessarily work. At least, not yet. | |
| Apr 30, 2019 at 16:15 | comment | added | EGME | At the very least, you have to show that, no matter how you choose the vertices in the cliques that do not intersect $K$, you can always make such choice to end up, at the end of each round, with all the cliques having a vertex colored as the color of the vertex in $K$ in the given round. Perhaps might you explain your idea further? | |
| Apr 30, 2019 at 16:14 | comment | added | vidyarthi | @EGME call the $\it{clique}$ $\it{degree}$ of a vertex, the number of cliques that share it. Now, I propose that the vertices with same clique degree, or, if not available, the next higher clique degree should be chosen to be in a color class. Does this look good? | |
| Apr 30, 2019 at 16:00 | comment | added | EGME | I will try to read further and deeper into the rest of your argument. But, if the choice is not random, then you must specify how to choose that vertex, and then you have to prove that you can make such choices all the way to the end. I don’t see quite how to do this, or how you do it. I would be glad to hear further. If it is of any consolation, this problem has been looked at by the truly “great” graph theorists of our time, without full success. | |
| Apr 30, 2019 at 15:49 | comment | added | vidyarthi | @EGME yes, you got my point exactly. And I even agree that the choice of points is not completely random. But, the crux of my argument is that exactly $k$ colors suffice | |
| Apr 30, 2019 at 14:37 | comment | added | EGME | So note that what I wrote just above has a problem (for one, in general, the vertex you choose in the $k-(m-1)$ cliques cannot be arbitrary, as those cliques might intersect). But again, I am just asking if I understood correctly. Apologies if I didn’t. | |
| Apr 30, 2019 at 14:07 | comment | added | EGME | It is a bit difficult to parse what you write. Please tell me if the idea you outline is the following (I hope it is not as difficult to read). Color one clique $K$, and suppose $m$ cliques intersect $K$ at a vertex $v$ with color 1. Then, for each of the $k-(m-1)$ cliques that do not intersect $K$ at $v$ you can choose an arbitrary vertex, and color it with color 1. Now all cliques have a vertex colored with color 1. Pick another vertex of $K$ and proceed likewise. And so on until you have exhausted all the vertices and colors. Do I understand you correctly? (No more space ... tbc) | |
| Apr 30, 2019 at 12:06 | comment | added | vidyarthi | @MichalAdamaszek I address that issue by considering their shared vertices. The intersection, if any, will be exactly at one vertex. If the vertices of the other cliques are shared with the first clique, then, we need not worry about them. The unshared vertices are definitely non-adjacent to one of the vertices in the first clique(each of them) hence could be put in one of the color classes already formed. Isnt it? | |
| Apr 30, 2019 at 11:55 | comment | added | Michal Adamaszek | Your argument doesn't address the fact that the other cliques (except for the initial one) can intersect. That causes a problem in the "proceeding so on" stage. | |
| Apr 30, 2019 at 10:47 | history | edited | vidyarthi | CC BY-SA 4.0 |
added 225 characters in body
|
| Apr 30, 2019 at 10:36 | comment | added | vidyarthi | @BenBarber where do you find confusion in my argument? Could you please specify? | |
| S Apr 30, 2019 at 9:50 | history | suggested | LeechLattice |
Equivalent to Erdos-Faber-Lovasz conjecture.
|
|
| Apr 30, 2019 at 8:46 | review | Suggested edits | |||
| S Apr 30, 2019 at 9:50 | |||||
| Apr 30, 2019 at 8:37 | comment | added | Ben Barber | This is a famous open problem. en.wikipedia.org/wiki/… I'm afraid I don't quite follow what you're suggesting well enough to pinpoint a mistake. | |
| Apr 30, 2019 at 7:58 | history | asked | vidyarthi | CC BY-SA 4.0 |