Nordhaus-Gaddum problem in term of G-free coloring

2022/01/12 by Rowshan, Yaser
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2201.04330

Abstract

Let H=(V(H),E(H)) be a graph. A k-coloring of H is a mapping π: V(H) \longrightarrow \1,2,…, k\, if each color class induces a K₂-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 induced subgraph by each color class of π, contains no copy of G. The G-free chromatic number of H, is the minimum number k, so that it has a G-free k-coloring, and denoted by χ_G(H). In this paper, we give some bounds and attributes on the G-free chromatic number of graphs, in terms of the number of vertices, maximum degree, minimum degree, and chromatic number. Our main results are the Nordhaus-Gaddum-type theorem for the \G-free chromatic number of a graph.

Related

• Extremal results on G-free colorings of graphs
• Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number
• Hereditary Nordhaus-Gaddum Graphs
• On generalized list \G-free colorings of graphs
• Nordhaus-Guddam Type Relations of Three Graph Coloring Parameters