𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Triangles in a complete chromatic graph with three colors

✍ Scribed by A.W Goodman

Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
556 KB
Volume
57
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let Kr~ be the complete graph on N vertices, and assume that each edge is assigned precisly one of three possible colors. An old and difficult problem is to find the minimum number of monochromatic triangles as a function of N. We are not able to solve this problem, but we can give sharp bounds for certain combinations of the number of triangles of various kinds. These sharp bounds are related to the main problem, and may be of independent interest.

πŸ“œ SIMILAR VOLUMES

A triangle-free circle graph with chroma
A triangle-free circle graph with chromatic number 5
✍ A.A. Ageev πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 170 KB

It follows from the results of , Gyirfis and Lehel (1985), and Kostochka (1988) that 4 ~x\* ## ~5 where x\* = max {X(G): G is a triangle-free circle graph}. We show that X\* ? 5 and thus X\* = 5. This disproves the conjecture of Karapetyan that X\* = 4 and answers negatively a question of Gyirfis

Size and independence in triangle-free g
Size and independence in triangle-free graphs with maximum degree three
✍ Kathryn Fraughnaugh Jones πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 549 KB

## Abstract Let __C__ be the class of triangle‐free graphs with maximum degree at most three. A lower bound for the number of edges in a graph of __C__ is derived in terms of the number of vertices and the independence. Several classes of graphs for which this bound is attained are given. As coroll

Largest bipartite subgraphs in triangle-
Largest bipartite subgraphs in triangle-free graphs with maximum degree three
✍ J. A. Bondy; S. C. Locke πŸ“‚ Article πŸ“… 1986 πŸ› John Wiley and Sons 🌐 English βš– 977 KB

Let G be a triangle-free, loopless graph with maximum degree three. We display a polynomi$ algorithm which returns a bipartite subgraph of G containing at least 5 of the edges of G. Furthermore, we characterize the dodecahedron and the Petersen graph as the only 3-regular, triangle-free, loopless, c

A Circuit Chasing Technique in a Distanc
A Circuit Chasing Technique in a Distance-regular Graph with Triangles
✍ Akira Hiraki πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 171 KB

We give an example of circuit chasing on a distance-regular graph which has triangles. In particular, we show that the number of columns \(\left(c_{i}, a_{i}, b_{i}\right)=(2,2 a, e)\) in the intersection array of a distance-regular graph is at most 1 , if all the preceding columns are \((1, a, b)\)

Edge density and independence ratio in t
Edge density and independence ratio in triangle-free graphs with maximum degree three
✍ Jerrold Griggs; Owen Murphy πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 548 KB

A simple polynomial-time algorithm is presented which computes independent sets of guaranteed size in connected triangle-free noncubic graphs with maximum degree 3. Let nand m denote the number of vertices and edges, respectively, and let c '= m/n denote the edge density where c < 3/2. The algorithm