Average Distance and Edge-Connectivity II
The average distance $\mu(G)$ of a connected graph $G$ of order $n$ is the average of the distances between all pairs of vertices of $G$. We prove that for a 3-edge-connected graph $G$ of order $n$ t...
The average distance $\mu(G)$ of a connected graph $G$ of order $n$ is the average of the distances between all pairs of vertices of $G$. We prove that for a 3-edge-connected graph $G$ of order $n$ t...
Nonseparating Induced Cycles Consisting of Contractible Edges in $k$-Connected Graphs
Egawa and Saito proved that every $k$-connected graph with girth at least 4 has an induced cycle $C$ such that $G-V(C)$ is $(k-3)$-connected, and every edge of $C$ is contractible. This means that we...
Egawa and Saito proved that every $k$-connected graph with girth at least 4 has an induced cycle $C$ such that $G-V(C)$ is $(k-3)$-connected, and every edge of $C$ is contractible. This means that we...
You are not logged in to this journal. Log in
Explicit Construction of Small Folkman Graphs
SIAM J. Discrete Math. Volume 21, Issue 4, pp. 1053-1060 (2008)
Published January 22, 2008
Connotea
CiteULike
del.icio.us
BibSonomy
A Folkman graph is a $K_4$-free graph $G$ such that if the edges of $G$ are 2-colored, then there exists a monochromatic triangle. Erdős offered a prize for proving the existence of a Folkman graph with at most 1 million vertices. In this paper, we construct several “small” Folkman graphs within this limit. In particular, there exists a Folkman graph on 9697 vertices.
©2008 Society for Industrial and Applied Mathematics| History: | Received March 29, 2007; accepted August 20, 2007; published January 22, 2008 |
| Permalink: | http://dx.doi.org/10.1137/070686743 |
KEYWORDS and AMS
05C55, 05C35, 05D10
PUBLICATION DATA
0895-4801 (print)
1095-7146 (online)
SIAM