Abstract
It is known that for every integer k≥ 4, each k-map graph with n vertices has at most kn – 2k edges. Previously, it was open whether this bound is tight or not. We show that this bound is tight for k=4. We also show that this bound is not tight for large enough k; more precisely, we show that for every \(0 < \epsilon < \frac{3}{328}\) and for every integer \(k\ge \frac{140}{41\epsilon}\), each k-map graph with n vertices has at most \((\frac{325}{328}+\epsilon)kn -- 2k\) edges. We further show that for every positive multiple k of 6, there are infinitely many integers n such that some k-map graph with n vertices has at least \((\frac{11}{12}k+\frac{1}{3})n\) edges.
The full version can be found at http://rnc.r.dendai.ac.jp/~chen/papers/kmap.pdf
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chen, Z.-Z.: Approximation algorithms for independent sets in map graphs. J. Algorithms 41, 20–40 (2001)
Chen, Z.-Z., Grigni, M., Papadimitriou, C.H.: Planar map graphs. In: Proceedings of the 30th ACM Symposium on Theory of Computing, pp. 514–523 (1998)
Chen, Z.-Z., Grigni, M., Papadimitriou, C.H.: Map graphs. J. ACM 49, 127–138 (2002)
Sanders, D.P., Zhao, Y.: A new bound on the cyclic chromatic number. J. Combinatorial Theory Ser. B 83, 102–111 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, ZZ. (2004). New Bounds on the Number of Edges in a k-Map Graph. In: Chwa, KY., Munro, J.I.J. (eds) Computing and Combinatorics. COCOON 2004. Lecture Notes in Computer Science, vol 3106. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27798-9_35
Download citation
DOI: https://doi.org/10.1007/978-3-540-27798-9_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22856-1
Online ISBN: 978-3-540-27798-9
eBook Packages: Springer Book Archive