2-Distance Coloring of 4-Irregular Planar Graphs
A $k$-irregular graph is a graph with maximum degree $k$ such that vertices of degree $k$ are not adjacent. A $2$-distance $k$-coloring of a graph is a coloring of the vertices using $k$ colors in which any two vertices at distance at most $2$ receive distinct colors. The $2$-distance chromatic number of $G$, denoted by $χ_{2}(G)$, is the minimum integer $k$ such that $G$ admits a $2$-distance $k$-coloring. Zhu \cite{zhu} proved that $χ_2(G)\leq 13$ for planar graphs with maximum degree at most $4$. We prove that for a 4-irregular planar graph $G$, we have $χ_2(G) \leq 10$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.23590
curl -X POST /api/v1/records/arxiv/2608.23590/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.23590/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'