The Complexity of Chromatic Number When Restricted to graphs with Bounded Genus or Bounded Crossing Number

e present a known theorem with the following authors. Part 1 was proven by Hopcroft and Tarjan [10]. Part 2 is easy. Part 3 was proven by Garey, Johnson, and Stockmeyer [6]. Part 4 was proven by Appel, Haken, and Koch [2, 3].

Saved in:
Bibliographic Details
Published in:SIGACT news 2022-06, Vol.53 (2), p.27-38
Main Authors: Gasarch, William, Hayes, Nathan, Ostuni, Anthony, Park, Davin
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:e present a known theorem with the following authors. Part 1 was proven by Hopcroft and Tarjan [10]. Part 2 is easy. Part 3 was proven by Garey, Johnson, and Stockmeyer [6]. Part 4 was proven by Appel, Haken, and Koch [2, 3].
ISSN:0163-5700
DOI:10.1145/3544979.3544987