Open: 4 colorability for graphs of bounded genus or bounded crossing number (has this been asked before?)

 I have  co-authored (with Nathan Hayes, Anthony Ostuni, Davin Park) an open problems column  on the topic of this post. It is here.

Let g(G) be the genus of a graph and cr(G) be the crossing number of a graph.

As usual chi(G) is the chromatic number of a graph. 

KNOWN to most readers of this blog:

{G: \chi(G) \le 2} is in P

{G: \chi(G) \le 3 and g(G)\le 0 } is NPC (planar graph 3-col)

{G : \chi(G) \le 4 and g(G) \le 0} is in P (it's trivial since all planar graphs are 4-col)

{G: \chi(G) \le 3 and cr(G) \le 0} is NPC (planar graph 3-col)

{G: \chi(G) \le 4 and cr(G) \le 0} is in P (trivial since all planar graphs are 4-col)

LESS WELL KNOWN BUT TRUE (and brought to my attention by my co-authors and also Jacob Fox and Marcus Schaefer) 

For all g\ge 0 and r\ge 5, {G : \chi(G) \le r and g(G) \le g} is in P

For all c\ge 0 and r\ge 5, {G : \chi(G) \le r and cr(G) \le c} is in P 

SO I asked the question: for various r,g,c what is the complexity of the following sets:

{G: \chi(G) \le r AND g(G) \le g} 

{G: \chi(G) \le r AND cr(G) \le c}

SO I believe the status of the following sets is open

{G : \chi(G) \le 4 and g(G)\le 1} (replace 1 with 2,3,4,...)

{G : \chi(G) \le 4 and cr(G)\le 1} (replace 1 with 2,3,4...) 

QUESTIONS

1) If anyone knows the answer to these open questions, please leave comments. 

2) The paper pointed to above mentions all of the times I read of someone asking questions like this. There are not many, and the problem does not seem to be out there. Why is that?

a) It's hard to find out who-asked-what-when. Results are published, open problems often are not. My SIGACT News open problems column gives me (and others) a chance to write down open problems; however, such venues are rare. So it's possible that someone without a blog or an open problems column raised these questions before. (I checked cs stack exchange- not there- and I posted there but didn't get much of a response.) 

b) Proving NPC seems hard since devising gadgets with only one crossing is NOT good enough since you use the gadget many times. This may have discouraged people from thinking about it. 

c) Proving that the problems are in P (for the r\ge 6 case) was the result of using a hard theorem in graph theory from 2007. The authors themselves did not notice the algorithmic result. The first published account of the algorithmic result might be my open problems column.  This may be a case of the graph theorists and complexity theorists not talking to each other, though that is surprising since there is so much overlap that I thought there was no longer a distinction. 

d) While I think this is a natural question to ask, I may be wrong. See here for a blog post about when I had a natural question and found out why I may be wrong about the problems naturalness.