Timeline for Does every infinite, connected, locally finite, vertex-transitive graph have a leafless spanning tree?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 13, 2023 at 17:02 | comment | added | Gabor Lippner | Question i) appears as question 28 in this list from 2010: users.renyi.hu/~abert/questions.pdf, attributed there to Babai. | |
| Feb 13, 2023 at 8:33 | comment | added | Agelos | ... the finite analogue seems to be open too: according to a 1996 conjecture of Alspach, Liu, & Zhang, every finite $d$-regular Cayley graph is $d$-edge-colourable. See link.springer.com/chapter/10.1007/978-3-642-40020-9_20 and references therein. | |
| Feb 13, 2023 at 8:32 | comment | added | Agelos | @bof: good question about the edge chromatic number in the cubic case. This is probably unknown, and has been asked here for arbitrary vertex-degree math.stackexchange.com/questions/3679294/…. I think this should be posted on MO too, would you like to? ... | |
| Feb 13, 2023 at 2:10 | comment | added | bof | @DanielAsimov For an acyclic graph (in particular a tree), "every edge lies in a double ray" is equivalent to "no vertex has degree $1$". Why do you think it's necessary to assume that the graph is infinite? What finite counterexample do you have in mind? | |
| Feb 13, 2023 at 1:39 | comment | added | Daniel Asimov | "Equivalently, every edge of 𝑇 lies in a double-ray." Doesn't this assume that T is infinite? | |
| Feb 13, 2023 at 1:05 | history | edited | Sam Hopkins | CC BY-SA 4.0 |
added 16 characters in body
|
| Feb 13, 2023 at 0:53 | history | edited | Sam Hopkins | CC BY-SA 4.0 |
added 22 characters in body
|
| Feb 13, 2023 at 0:17 | history | edited | bof | CC BY-SA 4.0 |
edited title
|
| Feb 12, 2023 at 11:11 | comment | added | bof | Conjecture (iii) implies that every infinite, connected, $3$-regular, vertex-transitive graph has edge chromatic number $3$. Is this true? | |
| Feb 12, 2023 at 10:39 | comment | added | bof | Conjecture (iii) says in other words: every infinite, connected, locally finite, vertex-transitive graph has an acyclic $2$-regular spanning subgraph. By the usual compactness argument, this is equivalent to the ostensibly weaker assertion: if $G$ is an infinite, connected, locally finite, vertex-transitive graph, then for each finite set $X\subset V(G)$ there is a subgraph $H_X$ of $G$ such that $X\subset V(H_X)$ and every vertex in $X$ has degree $2$ in $H_X$. | |
| Feb 10, 2023 at 19:26 | history | edited | Agelos | CC BY-SA 4.0 |
added 11 characters in body
|
| Feb 10, 2023 at 14:49 | history | asked | Agelos | CC BY-SA 4.0 |