Timeline for Equivalence between two definitions of Tree width
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 28, 2018 at 10:50 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jan 28, 2018 at 22:41 | answer | added | Discrete lizard♦ | timeline score: 2 | |
| Mar 27, 2017 at 6:49 | comment | added | user35837 | this is due the properties of chordal completion for original graph. | |
| Mar 24, 2017 at 20:15 | comment | added | user53923 | Ah no I was trying to say that if you take a tree decomposition of the chordal completion, you clearly have a bag of size k , but it could be less obvious for the original graph. (And yes I see I have missed that annoying -1 again... You are right) | |
| Mar 24, 2017 at 16:53 | comment | added | user35837 | I think you are talking about this $tw(G) ≥ ω(G) − 1$ , but see in the claim 1 I am not saying largest clique in $G$, I am saying largest clique in chordal completion of $G$. | |
| Mar 24, 2017 at 16:37 | history | edited | user35837 | CC BY-SA 3.0 |
added 5 characters in body
|
| Mar 24, 2017 at 16:30 | history | edited | user35837 | CC BY-SA 3.0 |
added 19 characters in body
|
| Mar 24, 2017 at 16:20 | comment | added | user35837 | your question is valid but I think it follows from the definition of tree - width ( by chordal i.e. definition 1) so it is true for original graph or am I missing something ? and for second thing you mean to say $k -1$ or at least $k$ ( see the last paragraph en.wikipedia.org/wiki/Chordal_graph) | |
| Mar 24, 2017 at 15:40 | comment | added | user53923 | About the proof of claim 1: It is indeed clear that the chordal completion has treewidth k, from your proof it is not obvious that this is true for the original graph. Also, you may want to rephrase your claims. Claim 1: If size of largest clique in a chordal decomposition of graph is say k then by tree decomposition we will get tree width at least k | |
| Mar 23, 2017 at 8:53 | history | tweeted | twitter.com/StackCompSci/status/844834496658661377 | ||
| Mar 22, 2017 at 12:29 | history | edited | user35837 |
edited tags
|
|
| Mar 22, 2017 at 10:51 | history | asked | user35837 | CC BY-SA 3.0 |