Timeline for The edge precoloring extension problem for complete graphs
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 25, 2020 at 11:10 | history | edited | Moritz Firsching | CC BY-SA 4.0 |
updated to new precoloring
|
| Jul 24, 2020 at 13:06 | history | edited | Moritz Firsching | CC BY-SA 4.0 |
deleted 240 characters in body
|
| Jul 24, 2020 at 11:59 | comment | added | vidyarthi | But, whether our precoloring sequence of fixed colors would appear in the normal edge coloring is the main question we must ask. See the answer by Florian. Yes, uniqueness would not be true, but even completion is also not true, as shown by Florian. But, given the colors having some intersection of colors between any two rows would warrant a completion is my view. | |
| Jul 24, 2020 at 10:33 | comment | added | Moritz Firsching | So many questions, but I think they can all be answered. For existence of a solution for every n, just take a coloring for all edges (which can always be done with n-1 colors) and forgot all but the $k$ outer diagonals as a precoloring. This can then clearly be extended. to a full coloring again. Uniqueness fails for n=10 already and it might not be too hard to construct more than one coloring for every larger n. I would expect that the number of extensions to a precoloring depends on the choice of precoloring. Perhaps asked more things as a actual questions and not in a comment.. | |
| Jul 24, 2020 at 10:22 | comment | added | vidyarthi | yes, thanks for the case $n=10$, but is there a formal proof for the possibility in every case, because the general problem of precoloring extension is NP-complete. So, I think in this case it is in P. Is it true? Would the uniqueness depend on the choice of the fixed colors? | |
| Jul 24, 2020 at 10:20 | history | edited | Moritz Firsching | CC BY-SA 4.0 |
completely answered question, after clarification of what was asked..
|
| Jul 24, 2020 at 9:58 | history | edited | Moritz Firsching | CC BY-SA 4.0 |
deleted 169 characters in body
|
| Jul 24, 2020 at 9:55 | comment | added | vidyarthi | thanks, edited the question slightly. My question is, can we do this unique extension for every complete graph of even order?That is given the last $k$ subdiagonals, can we always extend the coloring to the whole graph? | |
| Jul 24, 2020 at 9:34 | history | answered | Moritz Firsching | CC BY-SA 4.0 |