On defining numbers of circular complete graphs

DOI10.1016/J.DISC.2006.07.002MaRDI QIDQ864158zbMATH OpenOpenAlexFDO

Authors Amir Daneshgar, Hossein Hajiabolhassan, Nasrin Soltankhah

Publication date 13 February 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.07.002

zbMATH Keywords

circular coloring defining set graph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

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\).

Recommendations

Cites work

Cited in

(1)

Properties of an approximability-related parameter on circular complete graphs

This page was built for publication: On defining numbers of circular complete graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q864158)