Page not found

It seems we don't have the page that you requested. If you think this is an error of the system, please contact us.

Graph Theory » Directed Graphs

Seymour's Second Neighbourhood Conjecture ★★★

Author(s): Seymour

Conjecture   Any oriented graph has a vertex whose outdegree is at most its second outdegree.

Keywords: Caccetta-Häggkvist; neighbourhood; second; Seymour

Posted by nkorppi
updated March 18th, 2011
5 comments
Graph Theory » Topological G.T. » Coloring

5-coloring graphs with small crossing & clique numbers ★★

Author(s): Oporowski; Zhao

For a graph $ G $, we let $ cr(G) $ denote the crossing number of $ G $, and we let $ \omega(G) $ denote the size of the largest complete subgraph of $ G $.

Question   Does every graph $ G $ with $ cr(G) \le 5 $ and $ \omega(G) \le 5 $ have a 5-coloring?

Keywords: coloring; crossing number; planar graph

Posted by mdevos
updated October 9th, 2007
add new comment