✦ LIBER ✦

Induced subtrees in graphs of large chromatic number

✍ Scribed by A. Gyárfás; E. Szemeredi; Zs. Tuza

Publisher: Elsevier Science
Year: 1980
Tongue: English
Weight: 469 KB
Volume: 30
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(80)90230-7

No coin nor oath required. For personal study only.

✦ Synopsis

Our paper proves special eases of the following conjecture: for any fined tr~,e "J~ there exists a natural number f = fiT) ~o that every triangle-free graph of chromatic number ] T) contains T as au induced subgraph. The main ;csult concerns the case when T has radius two.

📜 SIMILAR VOLUMES

Induced trees in graphs of large chromat

Induced trees in graphs of large chromatic number

✍ Scott, A. D. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 134 KB 👁 2 views

Gyárfás and Sumner independently conjectured that for every tree T and integer k there is an integer f (k, T ) such that every graph G with χ(G) > f(k, t) contains either K k or an induced copy of T . We prove a `topological´version of the conjecture: for every tree T and integer k there is g(k, T )

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.

List edge chromatic number of graphs wit

List edge chromatic number of graphs with large girth

✍ A.V. Kostochka 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 785 KB

Kostochka, A.V., List edge chromatic number of graphs with large girth, Discrete Mathematics 101 (1992) 189-201. It is shown that the list edge chromatic number of any graph with maximal degree A and girth at least 8A(ln A + 1.1) is equal to A + 1 or to A. Conjecture 1. The list edge chromatic numbe

Fractional chromatic number and circular

Fractional chromatic number and circular chromatic number for distance graphs with large clique size

✍ Daphne Der-Fen Liu; Xuding Zhu 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 136 KB

## Abstract An Erratum has been published for this article in Journal of Graph Theory 48: 329–330, 2005. Let __M__ be a set of positive integers. The distance graph generated by __M__, denoted by __G__(__Z, M__), has the set __Z__ of all integers as the vertex set, and edges __ij__ whenever |__i__

The total chromatic number of graphs hav

The total chromatic number of graphs having large maximum degree

✍ A.J.W. Hilton; H.R. Hind 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 935 KB

Hilton, A.J.W. and H.R. Hind, The total chromatic number ofgraphs having large maximum degree, Discrete Mathematics 117 (1993) 127-140. The total colouring conjecture is shown to be correct for those graphs G having d(G)>21 V(G)I.

The circular chromatic number of series-

The circular chromatic number of series-parallel graphs with large girth

✍ Chien, Chihyun; Zhu, Xuding 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It was proved by Hell and Zhu that, if G is a series-parallel graph of girth at least 2 (3k -1)/2 , then χ c (G) ≤ 4k/(2k -1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series-parallel graph G of girth 2 (3k -1)/2 -1 such that χ c (G) > 4k/(2k -1)