Counterexamples to Clique Immersion Conjecture for Direct Products
Let \(G\) and \(H\) be graphs, and let \(G\times H\) denote their direct product. For a graph \(G\), let \(\operatorname{im}(G)\) be the largest integer \(t\) such that \(G\) contains a \(K_t\)-immersion. Collins, Heenehan, and McDonald conjectured that if \(\operatorname{im}(G)=t\) and \(\operatorname{im}(H)=r\), then \[\operatorname{im}(G\times H)\ge (t-1)(r-1)+1.\] We disprove this conjecture by constructing an infinite family of connected bipartite counterexamples.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.28518
curl -X POST /api/v1/records/arxiv/2605.28518/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.28518/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'