Vertex-Ramsey theorems for Cartesian powers of graphs
For graphs $G,H$ and positive integers $r$ and $n$ we write $G^{\square n} \xrightarrow{r} H$ if every $r$-vertex-coloring of the Cartesian power $G^{\square n}$ of $G$ contains a monochromatic copy of $H$. Since chromatic number $χ$ of $G^{\square n}$ is the same as $χ(G)$, there is an $r$-vertex coloring of $G^{\square n}$ for $r=χ(G)$, such that each color class is an independent set. We prove that for $r<χ(G)$ there is a large class of graphs $H$ such that $G^{\square n} \xrightarrow{r} H$. These graphs are so-called layered graphs in a hypercube. We also show that for some graphs $G$,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.07102
curl -X POST /api/v1/records/arxiv/2608.07102/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.07102/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'