New bounds on the edge number of a k-map graph

✍ Scribed by Zhi-Zhong Chen

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 310 KB
• Volume: 55
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20237

✦ Synopsis

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