New bounds on the edge number of a k ‐map graph
Zhi‐Zhong Chen · Journal of Graph Theory · 2007
Abstract It is known that for every integer k ≥ 4, each k ‐map graph with n vertices has at most kn − 2 k edges. Previously, it was open whether this bound is tight or not. We show that this bound is tight for k = 4, 5. We also show that this bound is not tight for large enough k (namely, k ≥ 374); more precisely, we show that for every $0 < \epsilon < {3 \over 328}$ and for every integer $k \ge {140 \over {41\epsilon}}$ , each k ‐map graph with n vertices has at most $({325 \over 328} + \epsilon){kn} - 2{k}$ edges. This result implies the first polynomial (indeed linear) time algorithm for coloring a given k ‐map graph with less than 2 k colors for large enough k . 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 $({11 \over 12}{k} + {1 \over 3}) {n}$ edges. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 267–290, 2007