Weighted odd-cycle transversals and fractional colorings of planar graphs
We bound fractional chromatic numbers by establishing a connection with low-weight odd-cycle transversals. Let $\ell\geq 3$ be an integer and let $G$ be a graph of odd girth at least $\ell$ whose odd-cycle covering polyhedron is integral. For every nonnegative weight vector $w=(w_v)_{v\in V(G)}\in \mathbb{R}_{\geq 0}^{V(G)}$, we obtain a set $Z\subseteq V(G)$ such that $G-Z$ is bipartite and $w(Z)\leq\frac{mad(G)}{2\ell}w(V(G))$. Here, $w(S)=\sum_{v\in S}w_v$ for any $S\subseteq V(G)$, and $mad(G)$ denotes the maximum average degree of $G$. Consequently, if $mad(G)<2\ell$, then $G$ has…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.30719
curl -X POST /api/v1/records/arxiv/2610.30719/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.30719/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'