论文标题
关于图表的词素颜色
On indicated coloring of lexicographic product of graphs
论文作者
论文摘要
指示的着色是一个图形着色游戏，其中两个玩家以以下方式集体为图的顶点着色。在每个回合中，第一个播放器（ANN）选择一个顶点，然后使用固定的颜色，将第二个玩家（BEN）正确颜色。 ANN的目的是实现整个图的适当着色，而Ben试图防止实现该项目。 Ann在图$ g $上赢得游戏所需的最小数量的颜色（无论Ben的策略如何）称为$ G $的指示色数，用$χ_i（g）$表示。在本文中，我们已经证明，对于任何图表$ g $和$ h $，$ g [h] $ is $ k $指示可为所有$ k \ geq \ geq \ mathrm {col}（g）\ mathrm {colrm {col}（h）$。另外，我们已经证明，对于任何图$ g $，对于某些类别的图形$ H $，$χ（h）=χ_i（h）= \ ell $，$ g [h] $ is $ k $ ins as $ k $ - 指示可着色，并且仅当$ g [k_ \ ell] $ is $ k $ k $ ins $ k $ - g $ - 指示色彩。由于此结果，我们已经表明，对于某些特定的图表$ g $和$ h $，$ g [h] $ is $ k $指示的每$ k \ geqχ（g [h]）$可着色。这是对A. Grzesik在\ cite {and}中提出的一个问题之一的部分答案。此外，如果$ g $是两部分图形或$ \ {p_5，k_3 \} $ - free Graph（oR）a $ \ {p_5，p_5，paw \} $ - 免费图形，如果$ h $来自相同的图形家庭，那么我们已经表明，$χ_i（g [h]）=χ（g [h] g [h]）$。
Indicated coloring is a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph $G$ (regardless of Ben's strategy) is called the indicated chromatic number of $G$, denoted by $χ_i(G)$. In this paper, we have shown that for any graphs $G$ and $H$, $G[H]$ is $k$-indicated colorable for all $k\geq\mathrm{col}(G)\mathrm{col}(H)$. Also, we have shown that for any graph $G$ and for some classes of graphs $H$ with $χ(H)=χ_i(H)=\ell$, $G[H]$ is $k$-indicated colorable if and only if $G[K_\ell]$ is $k$-indicated colorable. As a consequence of this result we have shown that for some particular families of graphs $G$ and $H$, $G[H]$ is $k$-indicated colorable for every $k\geq χ(G[H])$. This serves as a partial answer to one of the questions raised by A. Grzesik in \cite{and}. In addition, if $G$ is a Bipartite graph or a $\{P_5,K_3\}$-free graph (or) a $\{P_5,Paw\}$-free graph and if $H$ is from the same families of graphs, then we have shown that $χ_i(G[H])=χ(G[H])$.
