✦ LIBER ✦

On complete subgraphs of r-chromatic graphs

✍ Scribed by B. Bollobás; P. Erdös; E. Szemerédi

Publisher: Elsevier Science
Year: 1975
Tongue: English
Weight: 518 KB
Volume: 13
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(75)90011-4

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Finite subgraphs of uncountably chromati

Finite subgraphs of uncountably chromatic graphs

✍ Péter Komjáth; Saharon Shelah 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

## Abstract It is consistent that for every function __f__:ω → ω there is a graph with size and chromatic number ℵ~1~ in which every __n__‐chromatic subgraph contains at least __f__(__n__) vertices (__n__ ≥ 3). This solves a $ 250 problem of Erdős. It is consistent that there is a graph __X__ with

On complete subgraphs of color-critical

On complete subgraphs of color-critical graphs

✍ Xiang-Ying Su 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 488 KB

A graph G is called k-critical if x(G) = k and x(G -e) -C x(G) for each edge e of G, where x denotes the chromatic number. T. Gallai conjectured that every k-critical graph of order n contains at most n complete (kl)-subgraphs. In 1987, Stiebitz proved Gallai's conjecture in the case k = 4, and in 1

Total chromatic number of complete r-par

Total chromatic number of complete r-partite graphs

✍ K. H. Chew; H. P. Yap 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 284 KB 👁 1 views

## Abstract Rosenfeld (1971) proved that the Total Colouring Conjecture holds for balanced complete __r__‐partite graphs. Bermond (1974) determined the exact total chromatic number of every balanced complete __r__‐partite graph. Rosenfeld's result had been generalized recently to complete __r__‐par

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.

The chromatic index of complete multipar

The chromatic index of complete multipartite graphs

✍ D. G. Hoffman; C. A. Rodger 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB

## Abstract We show that a complete multipartite graph is class one if and only if it is not eoverfull, thus determining its chromatic index.

The chromatic uniqueness of complete bip

The chromatic uniqueness of complete bipartite graphs

✍ Shaoji Xu 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 585 KB

Xu, S., The chromatic uniqueness of complete bipartite graphs, Discrete Mathematics 94 (1991) 153-159. This paper is partitioned into two parts. In the first part we determine the maximum number of induced complete bipartite subgraphs in graphs with some given conditions. Using a theorem given in th