Timeline for Partial order on graphs induced by homomorphism counts
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 26, 2023 at 15:28 | history | edited | YCor | CC BY-SA 4.0 |
formatting, changed tag
|
| Jan 25, 2023 at 19:17 | comment | added | David Roberson | @MartinRubey It is not even clear to me if determining whether $G \le_{hom} H$ is a decidable problem. | |
| Jan 25, 2023 at 17:17 | comment | added | Martin Rubey | Is it clear how many graphs one needs to test to check whether $G\leq_{hom} H$, e.g., if both have $n$ vertices? For example, if $G$ is the star on four vertices and $H$ is the union of a triangle $C_3$ and an isolated vertex, then $\hom(C_3, G)=0$, $\hom(C_3, H)=6$ but $\hom(G, G)=30$ and $\hom(G, H)=24$, so $G$ and $H$ are not comparable. | |
| Jan 25, 2023 at 15:21 | history | asked | David Roberson | CC BY-SA 4.0 |