✦ LIBER ✦

The minimum number of subgraphs in a graph and its complement

✍ Scribed by Lane Clark

Publisher: John Wiley and Sons
Year: 1992
Tongue: English
Weight: 265 KB
Volume: 16
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190160506

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For a graphb F without isolated vertices, let M(F; n) denote the minimum number of monochromatic copies of F in any 2‐coloring of the edges of K~n~. Burr and Rosta conjectured that
when F has order t, size u, and a automorphisms. Independently, Sidorenko and Thomason have shown that the conjecture is false. We give families of graphs F of order t, of size u, and with a automorphisms where
.

📜 SIMILAR VOLUMES

On the number of maximal bipartite subgr

On the number of maximal bipartite subgraphs of a graph

✍ Jesper Makholm Byskov; Bolette Ammitzbøll Madsen; Bjarke Skjernaa 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB 👁 2 views

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105 n=10 % 1:5926 n ; such subgraphs show an upper bound of O(12 n=4 ) ¼ O(1:8613 n ) and give an algorithm that finds all maximal

Packing triangles in a graph and its com

Packing triangles in a graph and its complement

✍ Peter Keevash; Benny Sudakov 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 1 views

## Abstract How few edge‐disjoint triangles can there be in a graph __G__ on __n__ vertices and in its complement $\overline {G}$? This question was posed by P. Erdős, who noticed that if __G__ is a disjoint union of two complete graphs of order __n__/2 then this number is __n__^2^/12 + __o__(__n__

Subgraphs of large connectivity and chro

Subgraphs of large connectivity and chromatic number in graphs of large chromatic number

✍ N. Alon; D. Kleitman; C. Thomassen; M. Saks; P. Seymour 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB

For each pair k, rn of natural numbers there exists a natural number f(k, rn) such that every f ( k , m)-chromatic graph contains a k-connected subgraph of chromatic number at least rn.

Light subgraphs in planar graphs of mini

Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9

✍ B. Mohar; R. Škrekovski; H.-J. Voss 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 326 KB 👁 1 views

## Abstract A graph __H__ is light in a given class of graphs if there is a constant __w__ such that every graph of the class which has a subgraph isomorphic to __H__ also has a subgraph isomorphic to __H__ whose sum of degrees in __G__ is ≤ __w__. Let $\cal G$ be the class of simple planar graphs

The Spectra of Complementary Subgraphs i

The Spectra of Complementary Subgraphs in a Strongly Regular Graph

✍ D. de Caen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 117 KB

Forbidden subgraphs and hamiitonian prop

Forbidden subgraphs and hamiitonian properties in the square of a connected graph

✍ Ronald J. Gould; Michael S. Jacobson 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 331 KB 👁 1 views

Various Hamiltonian-like properties are investigated in the squares of connected graphs free of some set of forbidden subgraphs. The star K,+ the subdivision graph of &, and the subdivision graph of K1,3 minus an endvertex play central roles. In particular, we show that connected graphs free of the