2022/10/10 by Rowshan, Yaser, Taherkhani, Ali
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2210.04967
Let Kp be a complete graph of order p≥ 2. A Kp-free k-coloring of a graph H is a partition of V(H) into V1, V2…,Vk such that H[Vi] does not contain Kp for each i≤ k . In 1977 Borodin and Kostochka conjectured that any graph H with maximum degree Δ(H)≥ 9 and without KΔ(H) as a subgraph has chromatic number at most Δ(H)-1. As analogue of the Borodin-Kostochka conjecture, we prove that if p1≥ ⋯≥ pk≥ 2, p1+p2≥ 7, ∑i=1kpi=Δ(H)-1+k, and H does not contain KΔ(H) as a subgraph, then there is a partition of V(H) into V1,…,Vk such that for each i, H[Vi] does not contain Kpi. In particular, if p≥ 4 and H does not contain KΔ(H) as a subgraph, then H admits a Kp-free \lceilΔ(H)-1\over p-1\rceil-coloring. Catlin showed that every connected non-complete graph H with Δ(H)≥ 3 has a Δ(H)-coloring such that one of the color classes is maximum K2-free subset (maximum independent set). In this regard, we show that there is a partition of vertices of H into V1 and V2 such that H[V1] does not contain Kp, H[V2] does not contain Kq, and V1 is a maximum Kp-free subset of V(H) if p≥ 4, q≥ 3, p+q=Δ(H)+1, and its clique number ω(H)=p.