𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On bounding the chromatic number of L-graphs

✍ Scribed by Sean McGuinness

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
585 KB
Volume
154
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We show that the intersection graph of a collection of subsets of the plane, where each subset forms an "L" shape whose vertical stem is infinite, has its chromatic number 1 bounded by a function of the order of its largest clique w, where it is shown that ;1<2"4'3"4"'~'-". This proves a special case of a conjecture of Gyarf& and Lehel.

πŸ“œ SIMILAR VOLUMES

Another bound on the chromatic number of
Another bound on the chromatic number of a graph
✍ Paul A. Catlin πŸ“‚ Article πŸ“… 1978 πŸ› Elsevier Science 🌐 English βš– 422 KB

Let C be a simple graph. let JiGI denote the maximum degree of it\ \erlicek. ,III~ Ic~r \ 1 C; 1 denote irs chromatic pumber. Brooks' Theorem asserb lha1 ytG I'--AI G I. unk\\ C; hd.. .I component that is a COI lplete graph K,,,,\_ ,. or ullesq .I1 G I = 2 and G ha\ ;~n c~rld C\CIC

A bound on the chromatic number of a gra
A bound on the chromatic number of a graph
✍ Paul A. Catlin πŸ“‚ Article πŸ“… 1978 πŸ› Elsevier Science 🌐 English βš– 392 KB

We give an upper bound on the chromatic number of a graph in terms of its maximum degree and the size of the largest complete subgraph. Our result extends a theorem due to i3rook.s.

New bounds for the chromatic number of g
New bounds for the chromatic number of graphs
✍ Manouchehr Zaker πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 184 KB πŸ‘ 1 views

## Abstract In this article we first give an upper bound for the chromatic number of a graph in terms of its degrees. This bound generalizes and modifies the bound given in 11. Next, we obtain an upper bound of the order of magnitude ${\cal O}({n}^{{1}-\epsilon})$ for the coloring number of a graph

Bounds for the harmonious chromatic numb
Bounds for the harmonious chromatic number of a graph
✍ I. Krasikov; Y. Roditty πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 231 KB πŸ‘ 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph given by Zhikang Lu and by C. McDiarmid and Luo Xinhua, independently (__Journal of Graph Theory__, 1991, pp. 345–347 and 629–636) and the lower bound given by D. G. Beane, N. L. Biggs, and B. J. Wilson (__Journal of Graph T

Improved bounds for the chromatic number
Improved bounds for the chromatic number of a graph
✍ S. Louis Hakimi; Edward Schmeichel πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 97 KB πŸ‘ 2 views

## Abstract After giving a new proof of a well‐known theorem of Dirac on critical graphs, we discuss the elegant upper bounds of Matula and Szekeres‐Wilf which follow from it. In order to improve these bounds, we consider the following fundamental coloring problem: given an edge‐cut (__V__~1~, __V_