- | ||||
|
![]()
|
New descriptions of the Lovász number and a Brooks-type theorem
Ujvári Miklós (ujvarim Abstract: In the seminal work [1] L. Lovász introduced the concept of an orthonormal representation of a graph, and also a related value, now popularly known as the Lováasz number of the graph. One of the remarkable properties of the Lovász number is that it lies sandwiched between the stability number and the complementer chromatic number. This fact is called the sandwich theorem. In this paper, using new descriptions of the Lovász number and linear algebraic lemmas we give three proofs for a weaker version of the sandwich theorem. A Brooks-type theorem is also presented concerning a simple lower bound for the stability number. [1] Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inf. Theory, IT-25 1 (1979) 1-7. Keywords: Category 1: Combinatorial Optimization Citation: unpublished: ORR report 2006-2 Download: [PDF] Entry Submitted: 10/19/2006 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |