Vertex-critical graphs in subfamilies of $(P_4+\ell P_1)$-free graphs
A graph $G$ is $k$-vertex-critical if $χ(G)=k$ but $χ(G-v)<k$ for all $v\in V(G)$. In this paper we make progress on the open problem of the finiteness of $k$-vertex-critical $(P_4+\ell P_1)$-free graphs by showing that there are only finitely many $k$-vertex-critical graphs in the following subfamilies of $(P_4+\ell P_1)$-free graphs for all $k\ge 1$ and $\ell\ge 0$: $\bullet$ $(P_4+\ell P_1,\text{chair})$-free graphs, $\bullet$ $(P_4+\ell P_1,P_5,\text{bull})$-free graphs, and $\bullet$ $(P_4+\ell P_1,P_5,\text{cricket})$-free graphs. In fact, all but the first of these are special cases…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.06999
curl -X POST /api/v1/records/arxiv/2604.06999/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.06999/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'