✦ LIBER ✦

Bounds on eigenvalues and chromatic numbers

✍ Scribed by Dasong Cao

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 455 KB
Volume: 270
Category: Article
ISSN: 0024-3795
DOI: 10.1016/s0024-3795(96)00199-1

No coin nor oath required. For personal study only.

✦ Synopsis

We give new bounds on eigenvalue of graphs which imply some known bounds. In particular, if T(G) is the maximum sum of degrees of vertices a~t to a vertex in a graph G, the largest eigenvalue p(G) of G satisfies p(G) <~ ~IT(G) with equality if and only if either G is regular or G is bipartite and such that all vertices in the same part have the same degree. Consequently, we prove that the chromatic number of G is at most ~ + 1 with equality if and only if G is an odd cycle or a complete graph, which implies Brook's theorem. A generalization of this result is also given.

📜 SIMILAR VOLUMES

Some upper bounds on the total and list

Some upper bounds on the total and list chromatic numbers of multigraphs

✍ Roland Häggkvist; Amanda Chetwynd 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 762 KB

## Abstract In this paper we discuss some estimates for upper bounds on a number of chromatic parameters of a multigraph. In particular, we show that the total chromatic number for an __n__‐order multigraph exceeds the chromatic index by the smallest __t__ such that __t__! > __n__.

Bounds on chromatic numbers of multiple

Bounds on chromatic numbers of multiple factors of a complete graph

✍ Ján Plesník 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 306 KB 👁 1 views

## Abstract Bounds on the sum and product of the chromatic numbers of __n__ factors of a complete graph of order __p__ are shown to exist. The well‐known theorem of Nordhaus and Gaddum solves the problem for __n__ = 2. Strict lower and some upper bounds for any __n__ and strict upper bounds for __n

A New Bound on the Cyclic Chromatic Numb

A New Bound on the Cyclic Chromatic Number

✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 116 KB

In 1969, Ore and Plummer defined an angular coloring as a natural extension of the Four Color Problem: a face coloring of a plane graph where faces meeting even at a vertex must have distinct colors. A natural lower bound is the maximum degree 2 of the graph. Some graphs require w 3 2 2x colors in a

On bounding the chromatic number of L-gr

On bounding the chromatic number of L-graphs

✍ Sean McGuinness 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 585 KB

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 cas

A new upper bound on the cyclic chromati

A new upper bound on the cyclic chromatic number

✍ O. V. Borodin; H. J. Broersma; A. Glebov; J. van den Heuvel 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB 👁 1 views

## Abstract A cyclic coloring of a plane graph is a vertex coloring such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a graph is its cyclic chromatic number χ^__c__^. Let Δ^\*^ be the maximum face degree of a graph. There exist

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