Back to Search Start Over

Construction of <f>Kn</f>-minor free graphs with given circular chromatic number

Authors :
Liaw, Sheng-Chyang
Pan, Zhishi
Zhu, Xuding
Source :
Discrete Mathematics. Feb2003, Vol. 263 Issue 1-3, p191. 16p.
Publication Year :
2003

Abstract

For each integer &lt;f&gt;n&amp;ges;5&lt;/f&gt; and each rational number &lt;f&gt;r&lt;/f&gt; in the interval &lt;f&gt;[2,n−1]&lt;/f&gt;, we construct a &lt;f&gt;Kn&lt;/f&gt;-minor free graph &lt;f&gt;G&lt;/f&gt; with &lt;f&gt;χc(G)=r&lt;/f&gt;. This answers a question asked by Zhu (Discrete Mathematics, 229 (1–3) (2001) 371). In case &lt;f&gt;n=5&lt;/f&gt;, the constructed graphs are actually planar. Such planar graphs were first constructed in J. Graph Theory 24 (1997) 33 (for &lt;f&gt;∈[2,3]&lt;/f&gt;) and in J. Combin. Theory 76 (1999) 170 (for &lt;f&gt;r∈[3,4]&lt;/f&gt;). However, our construction and proof are much simpler. [Copyright &amp;y&amp; Elsevier]

Details

Language :
English
ISSN :
0012365X
Volume :
263
Issue :
1-3
Database :
Academic Search Index
Journal :
Discrete Mathematics
Publication Type :
Academic Journal
Accession number :
9144437
Full Text :
https://doi.org/10.1016/S0012-365X(02)00529-0