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
Graph Theory » Basic G.T. » Cycles

Jones' conjecture ★★

Author(s): Kloks; Lee; Liu

For a graph $ G $, let $ cp(G) $ denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let $ cc(G) $ denote the cardinality of a minimum feedback vertex set (set of vertices $ X $ so that $ G-X $ is acyclic).

Conjecture   For every planar graph $ G $, $ cc(G)\leq 2cp(G) $.

Keywords: cycle packing; feedback vertex set; planar graph

Posted by cmlee
updated December 5th, 2019
3 comments