On defining numbers of circular complete graphs (Q864158): Difference between revisions

Let \(\gamma \) be an onto \(t\)-coloring of the vertices of a graph \(G\), i.e., a proper \(t\)-coloring in which all \(t\) colors actually appear. A subset \(S\) of \(V(G)\) is a ``defining set'' of \(\gamma \) if the only extension of \(\gamma | S\) to a proper vertex-coloring of \(G\) is \( \gamma \) itself; \(d(\gamma )\) is the minimum size of a defining set of \( \gamma \). Let \(d^{\min }(G,t)\) (resp. \(d^{\max }(G,t)\)) be the smallest (resp. largest) value of \(d(\gamma )\) among the onto \(t\)-colorings of \(G\). The authors study \(d^{\min }(K_{n,d},\chi )\) and \(d^{\max }(K_{n,d},\chi )\) of the complete circular graph \(K_{n,d}\), where \(\chi =\chi (K_{n,d})=\left\lceil n/d\right\rceil \geq 4\). As an application they show that if \(G\) is a graph with circular chromatic number \(\chi _{c}(G)=\frac{n}{d}\geq 3\) where \(\gcd (n,d)=1\), \(n=kd-s\) and \(0<s<d\), then \(d^{\max }(G,\chi (G))\geq \chi (G)+2s-3\).