Timeline for Tree width and clique width of regular graphs
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 15, 2022 at 5:27 | comment | added | LeechLattice | The reference for $K_{3,3}$ is N. C. Wormald's survey, Models of random regular graphs, Lemma 2.7. The lemma states that for fixed d and fixed graph F with more edges than vertices, almost all random d-regular graphs do not contain F as a subgraph. | |
| Sep 15, 2022 at 5:24 | comment | added | LeechLattice | @RandomMatrices It's true for n-4 regular graphs. As the complement of an (n-4)-regular graph is a cubic graph, and the complement graph of a graph of clique-width k has clique-width at most 2k, the (n-4)-regular graph has clique-width Θ(n) if the cubic graph is taken to be a random cubic graph. | |
| Sep 15, 2022 at 5:16 | comment | added | RandomMatrices | Is there a reference to the fact that no random regular graph has $K_{3 \times 3}$ as a subgraph? Also, for what regularity does this fact break down? It is obviously false for a complete ($n-1$ regular graph), because the tree width of a complete graph is linear, but the clique width is bounded. It is also false for $n-2$ and $n-3$ regular graphs for a similar reason. Is it true from $n-4$ regular graphs? | |
| Sep 14, 2022 at 18:24 | vote | accept | RandomMatrices | ||
| Sep 14, 2022 at 2:08 | history | answered | LeechLattice | CC BY-SA 4.0 |