Graph Theory » Algebraic G.T.

Triangle free strongly regular graphs ★★★

Author(s):

Problem   Is there an eighth triangle free strongly regular graph?

Keywords: strongly regular; triangle free

Posted by mdevos
updated May 30th, 2020
4 comments
Graph Theory » Coloring » Vertex coloring

Alon-Saks-Seymour Conjecture ★★★

Author(s): Alon; Saks; Seymour

Conjecture   If $ G $ is a simple graph which can be written as an union of $ m $ edge-disjoint complete bipartite graphs, then $ \chi(G) \le m+1 $.

Keywords: coloring; complete bipartite graph; eigenvalues; interlacing

Posted by mdevos
updated February 26th, 2010
1 comment
Graph Theory » Topological G.T. » Coloring

Bounded colorings for planar graphs ★★

Author(s): Alon; Ding; Oporowski; Vertigan

Question   Does there exists a fixed function $ f : {\mathbb N} \rightarrow {\mathbb N} $ so that every planar graph of maximum degree $ d $ has a partition of its vertex set into at most three sets $ \{V_1,V_2,V_3\} $ so that for $ i=1,2,3 $, every component of the graph induced by $ V_i $ has size at most $ f(d) $?

Keywords: coloring; partition; planar graph

Posted by mdevos
updated May 23rd, 2007
add new comment