Graph Theory » Coloring » Vertex coloring

Cycles in Graphs of Large Chromatic Number ★★

Author(s): Brewster; McGuinness; Moore; Noel

Conjecture   If $ \chi(G)>k $, then $ G $ contains at least $ \frac{(k+1)(k-1)!}{2} $ cycles of length $ 0\bmod k $.

Keywords: chromatic number; cycles

Posted by Jon Noel
updated September 20th, 2015
add new comment
Combinatorics

The Double Cap Conjecture ★★

Author(s): Kalai

Conjecture   The largest measure of a Lebesgue measurable subset of the unit sphere of $ \mathbb{R}^n $ containing no pair of orthogonal vectors is attained by two open caps of geodesic radius $ \pi/4 $ around the north and south poles.

Keywords: combinatorial geometry; independent set; orthogonality; projective plane; sphere

Posted by Jon Noel
updated September 15th, 2015
add new comment
Graph Theory

Circular flow numbers of $r$-graphs ★★

Author(s): Steffen

A nowhere-zero $ r $-flow $ (D(G),\phi) $ on $ G $ is an orientation $ D $ of $ G $ together with a function $ \phi $ from the edge set of $ G $ into the real numbers such that $ 1 \leq |\phi(e)| \leq r-1 $, for all $ e \in E(G) $, and $ \sum_{e \in E^+(v)}\phi(e) = \sum_{e \in E^-(v)}\phi(e), \textrm{ for all } v \in V(G) $.

A $ (2t+1) $-regular graph $ G $ is a $ (2t+1) $-graph if $ |\partial_G(X)| \geq 2t+1 $ for every $ X \subseteq V(G) $ with $ |X| $ odd.

Conjecture   Let $ t > 1 $ be an integer. If $ G $ is a $ (2t+1) $-graph, then $ F_c(G) \leq 2 + \frac{2}{t} $.

Keywords: flow conjectures; nowhere-zero flows

Posted by Eckhard Steffen
updated August 6th, 2015
add new comment
Graph Theory » Coloring » Nowhere-zero flows

Circular flow number of regular class 1 graphs ★★

Author(s): Steffen

A nowhere-zero $ r $-flow $ (D(G),\phi) $ on $ G $ is an orientation $ D $ of $ G $ together with a function $ \phi $ from the edge set of $ G $ into the real numbers such that $ 1 \leq |\phi(e)| \leq r-1 $, for all $ e \in E(G) $, and $ \sum_{e \in E^+(v)}\phi(e) = \sum_{e \in E^-(v)}\phi(e), \textrm{ for all } v \in V(G) $. The circular flow number of $ G $ is inf$ \{ r | G $ has a nowhere-zero $ r $-flow $ \} $, and it is denoted by $ F_c(G) $.

A graph with maximum vertex degree $ k $ is a class 1 graph if its edge chromatic number is $ k $.

Conjecture   Let $ t \geq 1 $ be an integer and $ G $ a $ (2t+1) $-regular graph. If $ G $ is a class 1 graph, then $ F_c(G) \leq 2 + \frac{2}{t} $.

Keywords: nowhere-zero flow, edge-colorings, regular graphs

Posted by Eckhard Steffen
updated August 5th, 2015
add new comment