论文标题
Nordhaus-gaddum问题，$ g $ free free着色
Nordhaus-Gaddum problem in term of $G$-free coloring
论文作者
论文摘要
令$ h =（v（h），e（h））$为图。 $ k $ - 颜色的$ h $是映射$π：v（h）\ longrightArrow \ {1,2，\ ldots，k \} $，如果每个颜色类都诱导$ k_2 $ free subsgraph。对于图$ g $的订单，至少$ 2 $，$ g $ -free $ k $ - 颜色为$ h $，是一个映射$π：v（h）\ longrightarrow \ {1,2，\ ldots，k \} $，因此，每种颜色的$π$ copper ocpers of $ g $ coppect of $π$的诱导子图。 $ g $ - $ h $的$ f $ h $，是最低$ k $，因此它具有$ g $ - free $ k $ - 颜色，并用$χ_g（h）$表示。在本文中，我们在$ g $ free颜色的图表上给出了一些界限和属性，就顶点数量，最高度，最低度和色数提供了一些界限和属性。我们的主要结果是$ \ g $ free图的nordhaus-gaddum-type定理。
Let $H=(V(H),E(H))$ be a graph. A $k$-coloring of $H$ is a mapping $π: V(H) \longrightarrow \{1,2,\ldots, k\}$, if each color class induces a $K_2$-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,\ldots,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.
