𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On extremal graphs without compatible triangles or quadrilaterals

✍ Scribed by Olof Barr

Book ID
103060454
Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
679 KB
Volume
125
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Letf(n, H, 5) be the maximal number of edges in a graph with n vertices not containing a subgraph H compatible with a transition system X in the family of transition systems !T. Here we will use a family of transition systems X,, defined through local edge colourings. At each vertex the edge set is partitioned into parts containing no more than s+ 1 edges. An allowed transition at a vertex is a pair of incident edges not contained in the same part. In this paper we will give upper and lower bounds for f(n, &, X,) and f(n, C4, X,).

πŸ“œ SIMILAR VOLUMES

Extremal graphs without three-cycles or
Extremal graphs without three-cycles or four-cycles
✍ David K. Garnick; Y. H. Harris Kwong; Felix Lazebnik πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 594 KB

## Abstract We derive bounds for __f(v)__, the maximum number of edges in a graph on __v__ vertices that contains neither three‐cycles nor four‐cycles. Also, we give the exact value of __f(v)__ for all __v__ up to 24 and constructive lower bounds for all __v__ up to 200. Β© 1993 John Wiley & Sons, I

On quadrilaterals in layers of the cube
On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs
✍ Schelp, Richard H.; Thomason, Andrew πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 286 KB πŸ‘ 2 views

ErdΕ‘s has conjectured that every subgraph of the n-cube Q n having more than (1/2+o(1))e(Q n ) edges will contain a 4-cycle. In this note we consider 'layer' graphs, namely, subgraphs of the cube spanned by the subsets of sizes k -1, k and k + 1, where we are thinking of the vertices of Q n as being