Construction of K_n-minor free graphs with given circular chromatic number

In this paper it is shown that for each integer \(n\geq 5\) and each rational number \(r\) in the interval \([2,n-1]\), there is a \(K_{n}\)-minor free graph \(G\) with \(\chi_{c}(G)=r\), where \(\chi _{c}(G)\) denotes the circular chromatic number of \(G\). This answers a question asked by \textit{X. Zhu} [Discrete Math. 229, 371-410 (2001; Zbl 0973.05030)]. To prove this the required graphs are actually constructed, based on the labeling method of calculating \(\chi _{c}(G)\). For \(2<p/q<4\), the \(K_{5}\)-minor free graph \(H\) with \(\chi _{c}(H)=p/q\) constructed in this way is a planar graph. This produces an alternate proof of the results by \textit{D. Moser} [J. Graph Theory 24, 33-43 (1997; Zbl 0870.05017)] and \textit{X. Zhu} [J. Comb. Theory, Ser. B 76, 170-200 (1999; Zbl 0933.05053)]. The proof is based on a different idea and is simpler than the original proofs.

Recommendations

Cited in

(7)

This page was built for publication: Construction of \(K_{n}\)-minor free graphs with given circular chromatic number

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