Timeline for Variant of Graph coloring
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Oct 1, 2017 at 12:09 | history | bounty ended | CommunityBot | ||
| S Oct 1, 2017 at 12:09 | history | notice removed | CommunityBot | ||
| Sep 23, 2017 at 11:15 | answer | added | domotorp | timeline score: 6 | |
| S Sep 23, 2017 at 11:01 | history | bounty started | user1659936 | ||
| S Sep 23, 2017 at 11:01 | history | notice added | user1659936 | Draw attention | |
| Sep 20, 2017 at 15:31 | history | edited | user1659936 | CC BY-SA 3.0 |
added 2 characters in body
|
| Sep 20, 2017 at 10:22 | history | edited | user1659936 | CC BY-SA 3.0 |
added 18 characters in body
|
| Sep 20, 2017 at 10:21 | comment | added | user1659936 | @Peter Heining Since threshold graphs have nice structure, I expect a polynomial time algorithm to this problem. Moreover, I have not seen any hard graph problem on threshold graphs. Because of these two things I believe the problem is polytime solvable. | |
| Sep 20, 2017 at 10:05 | comment | added | Peter Heinig | a function $\overline{c}\colon V\to\mathcal{C}$ such that $\overline{c}$ is a maximizer of the number of monochromatic edges among all such extensions. (Note that I recommend that you replace "high" with the usual 'monochromatic'.) And is there a reason for you to expect a polynomial time algorithm for threshold graphs? (The mentioning of which currently seems surprising.) | |
| Sep 20, 2017 at 10:04 | comment | added | Peter Heinig | Re "to total coloring": I think you unintentionally 'hit' an already taken technical term: you evidently do not intend to in the end have a total coloring of your graph. Again, the meaning is clear, yet it might get even clearer if you edited your question to the mathematically precise "Given a graph $G=(V,E)$, some $S\subset V$ and a function $c\colon S\to \mathcal{C}$, my goal is to extend $c$ to [...] | |
| Sep 20, 2017 at 9:25 | history | asked | user1659936 | CC BY-SA 3.0 |