{"id":"arxiv/2607.12367","url":"https://arxiv.org/abs/2607.12367","tags":["math.CO","cs.DM"],"score":0,"title":"Coloring $(P_6,C_4)$-free graphs with $Δ- 1$ colors","domain":"math.CO","source":"arxiv","authors":["Uttam K. Gupta","Dinabandhu Pradhan","Rashmi Rekha Swain"],"reviews":0,"subject":"math.CO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-14","reactions":{}}