Burr has shown that if \(G\) is any graph without isolates and \(H_0\) is any connected graph, every graph \(H\) obtained from \(H_0\) by subdividing a chosen edge sufficiently many times to create a long suspended path satisfies \(r(G, H) = (x(G) – 1)(|V(H)| – 1) + s(G)\), where \(s(G)\) is the largest number such that in every proper coloring of \(V(G)\) using \(\chi(G)\) colors, every color class has at least \(s(G)\) elements. In this paper, we prove a companion result for graphs obtained from \(H_0\) by adding sufficiently many pendant edges.

The Ramsey multiplicity \(R(G)\) of a graph \(G\) is defined as the smallest number of monochromatic copies of \(G\) in any two-coloring of the edges of \(K_r(q)\), where \(r(G)\) is the Ramsey number of \(G\). Here, we prove that \(R(K_4) \geq 4\).

In this paper we refine Whitney’s Theorem on \(k\)-connected graphs for \(k \geq 3\). In particular we show the following: Let \(G\) be a \(k\)-connected graph with \(k \geq 3\). For any two distinct vertices \(u\) and \(v\) of \(G\) there are \(k\) internally vertex disjoint paths \(P_1[u,v], P_2[u,v], \dots, P_k[u,v]\) such that \(G – V(P_i(u,v))\) is connected for \(i = 1, 2, \dots, k\), where \(P_i(u, v)\) denotes the internal vertices of the path \(P_i[u, v]\). Further one of the following properties holds:

1. \(G – V(P_i[u, v])\) is connected for \(i = 1, 2, 3\).
2. \(G – V(P_i[u, v])\) is connected for \(i = 1, 2\) and \(G – V(P_i[u, v])\) has exactly two connected components for \(i = 3, 4, \dots, k\).

In addition, some other properties will be proved.

Some results relating to the road-coloring conjecture of Alder, Goodwyn, and Weiss, which give rise to an \(O(n^2)\) algorithm to determine whether or not a given edge-coloring of a graph is a road-coloring, are noted. Probabilistic analysis is then used to show that, if the outdegree of every edge in an \(n\)-vertex digraph is \(\delta = \omega(\log n)\), a road-coloring for the graph exists. An equivalent re-statement of the conjecture is then given in terms of the cross-product of two graphs.

A graph \(G = (V, E)\) is a loop niche graph if there is a digraph \(D = (V, A)\)such that \(xy \in E\) iff there exists \(z \in V\) such that either \(xz\) and \(yz \in A\) or \(zx\) and \(zy \in A\). If \(D\) has no loops, \(G\) is a cyclic niche graph, and if \(D\) is acyclic, \(G\) is a niche graph. We give a characterization of triangle-free cyclic niche graphs, and apply this to classify grids.

Let \(\Phi(N)\) be the maximum number of simple polygons that can be drawn using as vertices a set \(V\) of \(N\) points in the plane. By counting the number of simple polygons of a particular configuration of \(V\), an improved lower bound for \(\Phi(N)\) is obtained. It is proved that \(\Phi(N)^\frac{1}{N}\) is asymptotically greater than \(3.6\).