Coloring $(P_6,C_4)$-free graphs with $Δ- 1$ colors

Uttam K. Gupta; Dinabandhu Pradhan; Rashmi Rekha Swain

Coloring $(P_6,C_4)$-free graphs with $Δ- 1$ colors

Uttam K. Gupta, Dinabandhu Pradhan, Rashmi Rekha Swain

arXivarxiv/2607.12367Jul 14, 2026math.COscore 0

For a graph $G$, let $Δ(G)$, $ω(G)$, and $χ(G)$ denote the maximum degree, clique number, and chromatic number of $G$, respectively. Let $P_n$ and $C_n$ denote the chordless path and chordless cycle on $n$ vertices, respectively. In this paper, we prove that every $(P_6,C_4)$-free graph $G$ with $Δ(G)\ge 9$ and $ω(G)<Δ(G)$ is $(Δ(G)-1)$-colorable.

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2607.12367
curl -X POST /api/v1/records/arxiv/2607.12367/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.12367/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'