Graph Theory » Infinite Graphs

Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

Problem   Does there exist a graph with no subgraph isomorphic to $ K_4 $ which cannot be expressed as a union of $ \aleph_0 $ triangle free graphs?

Keywords: forbidden subgraph; infinite graph; triangle free

Posted by mdevos
updated June 4th, 2007
add new comment
Graph Theory » Algebraic G.T.

Half-integral flow polynomial values ★★

Author(s): Mohar

Let $ \Phi(G,x) $ be the flow polynomial of a graph $ G $. So for every positive integer $ k $, the value $ \Phi(G,k) $ equals the number of nowhere-zero $ k $-flows in $ G $.

Conjecture   $ \Phi(G,5.5) > 0 $ for every 2-edge-connected graph $ G $.

Keywords: nowhere-zero flow

Posted by mohar
updated May 31st, 2007
add new comment
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