2022/01/20 by Rowshan, Yaser
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2201.08048
Let H=(V(H),E(H)) be a graph. A k-coloring of H is a mapping π: V(H) \longrightarrow \1,2,…, k\ so that each color class induces a K2-free subgraph. For a graph G of order at least 2, a G-free k-coloring of H is a mapping π: V(H) \longrightarrow \1,2,…,k\ so that the subgraph of H induced by each color class of π is G-free, i.e. contains no copy of G. The G-free chromatic number of H is the minimum number k so that there is a G-free k-coloring of H, denoted by χG(H). A graph H is uniquely k-G-free colouring if χG(H)=k and every k-G-free colouring of H produces the same color classes. A graph H is minimal with respect to G-free, or G-free-minimal, if for every edges of E(H) we have χG(H∖\e\)= χG(H)-1. In this paper we give some bounds and attribute about uniquely k-G-free colouring and k-G-free-minimal.