Perfect Graphs
Book 1
Book 2
Book 3
Book 1
Book 2
Book 3
Book 1
Book 2
Book 3
Book 1
Book 2
Book 3
Home > Mathematics and Science Textbooks > Mathematics > Combinatorics and graph theory > Perfect Graphs: (Wiley Series in Discrete Mathematics & Optimization)
Perfect Graphs: (Wiley Series in Discrete Mathematics & Optimization)

Perfect Graphs: (Wiley Series in Discrete Mathematics & Optimization)


     0     
5
4
3
2
1



International Edition


X
About the Book

The theory of perfect graphs was born out of a conjecture about graph colouring made by Claude Berge in 1960. That conjecture remains unsolved, but has generated an important area of research in combinatorics. This book: * Includes an introduction by Claude Berge, the founder of perfect graph theory * Discusses the most recent developments in the field of perfect graph theory * Provides a thorough historical overview of the subject * Internationally respected authors highlight the new directions, seminal results and the links the field has with other subjects * Discusses how semi-definite programming evolved out of perfect graph theory The early developments of the theory are included to lay the groundwork for the later chapters. The most recent developments of perfect graph theory are discussed in detail, highlighting seminal results, new directions, and links to other areas of mathematics and their applications. These applications include frequency assignment for telecommunication systems, integer programming and optimisation.

Table of Contents:
List of Contributors. Preface. Acknowledgements. 1. Origins and Genesis (C. Berge and J.L. Ramirez Alfonsin). Perfection. Communication Theory. The Perfect Graph Conjecture. Shannon's Capacity. Translation of the Halle-Wittenberg Proceedings. Indian Report. References. 2. From Conjecture to Theorem (Bruce A Reed). Gallai's Graphs. The Perfect Graph Theorem. Some Polyhedral Consequences. A Stronger Theorem. References. 3. A Translation of Gallai's Paper: "Transitiv Orientierbare Graphen" (Frederic Maffray and Myriam Preissmann). Introduction and Results. The Proofs of Theorems (3.12), (3.15) and 3.16). The Proofs of (3.18) and (3.19). The Proofs of (3.1.16). The Proofs of (3.1.17). Determination of all Irreducible Graphs. Determination of the Irreducible Graphs. References. 4. Even Pairs (Hazel Everett et al). Introduction. Even Pairs and Perfect Graphs. Perfectly Contractile Graphs. Quasi-parity Graphs. Recent Progress. Odd Pairs. References. 5. The P_4-Structure of Perfect Graphs (Stefan Hougardy). Introduction. P_4-Stucture: Basics, Isomorphisms and Recognition. Modules, h-Sets, Split Graphs and Unique P_4-Structure. The Semi-Strong perfect Graph Theorem. The Structure of the P_4-Isomorphism Classes. Recognizing P_4-Structure. The P_4-Structure of Minimally Imperfect Graphs. The Partner Structure and Other Generalizations. P_3-Structure. References. 6. Forbidding Holes and Antiholes (Ryan Hayward and Bruce A. Reed). Introduction. Graphs with No Holes. Graphs with No Discs. Graphs with No Long Holes. Balanced Matrices. Bipartitie Graphs with No Hole of Length 4k + 2. Graphs without Even Holes. -Perfect Graphs. Graphs without Odd Holes. References. 7. Perfectly Orderable Graphs: A Survey (Chinh T Hoang). Introduction. Classical Graphs. Minimal Nonperfectly Orderable Graphs. Orientations. Generalizations of Triangulated Graphs. Generalizations of Complements of Chordal Bipartitie Graphs. Other Classes of Perfectly Orderable Graphs. Vertex Orderings. Generalizations of Perfectly Orderable Graphs. Optimizing Perfectly Ordered Graphs. References. 8. Cutsets in Perfect and Minimal Imperfect Graphs (Irena Rusu). Introduction. How Did It Start? Main Results on Minimal Imperfect Graphs. Applications: Star Cutsets. Applications: Clique and Multipartite Cutsets. Applications: Stable Cutsets. Two (Resolved) Conjectures. The Connectivity of Minimal Imperfect Graphs. Some (More) Problems. References. 9. Some Aspects of Minimal Imperfect Graphs (Myriam Preissmann and Andras Sebo). Introduction. Imperfect and Partitionable Graphs. Properties. Constructions. References. 10. Graph Imperfection and Channel Assignment (Colin McDiarmid). Introduction. The Imperfection Ratio. An Alternative Definition. Further Results and Questions. background on Channel Assignment. References. 11. A Gentle Introduction to Semi-definite Programming (Bruce A. Reed). Introduction. The Ellipsoid Method. Solving Semi-definite Programs. Randomized Rounding and Derandomization. Approximating MAXCUT. Approximating Bandwidth. Graph Colouring. 12. The Theta Body. References. The Theta Body and Imperfection (F.B. Shepherd). Background and Overview. Optimization, Convexity and Geometry. The Theta Body. Partitionable Graphs. Perfect Graph Characterizations and a Continuous Perfect Graph Conjecture. References. 13. Perfect Graphs and Graph Entropy (Gabor Simonyi). Introduction. The Information-Theoretic Interpretation. Some Basic Properties. Structural Theorems: Relation to Perfectness. Applications. Generalizations. Graph Capacities and Other Related Functionals. References. 14 A Bibliography on Perfect Graphs (Vaek Chvátal). Index.

About the Author :
Jorge L. Ramírez-Alfonsín is the editor of Perfect Graphs, published by Wiley. Bruce Alan Reed FRSC is a Canadian mathematician and computer scientist, the Canada Research Chair in Graph Theory and a professor of computer science at McGill University. His research is primarily in graph theory.

Review :
"...illuminates the relationships between perfect graph theory and other fields of scientific enquiry..." (SciTech Book News, Vol. 26, No. 2, June 2002)


Best Sellers


Product Details
  • ISBN-13: 9780471489702
  • Publisher: John Wiley & Sons Inc
  • Publisher Imprint: John Wiley & Sons Inc
  • Height: 253 mm
  • No of Pages: 386
  • Returnable: N
  • Spine Width: 28 mm
  • Width: 172 mm
  • ISBN-10: 0471489700
  • Publisher Date: 14 Sep 2001
  • Binding: Hardback
  • Language: English
  • Returnable: N
  • Series Title: Wiley Series in Discrete Mathematics & Optimization
  • Weight: 822 gr


Similar Products

Add Photo
Add Photo

Customer Reviews

REVIEWS      0     
Click Here To Be The First to Review this Product
Perfect Graphs: (Wiley Series in Discrete Mathematics & Optimization)
John Wiley & Sons Inc -
Perfect Graphs: (Wiley Series in Discrete Mathematics & Optimization)
Writing guidlines
We want to publish your review, so please:
  • keep your review on the product. Review's that defame author's character will be rejected.
  • Keep your review focused on the product.
  • Avoid writing about customer service. contact us instead if you have issue requiring immediate attention.
  • Refrain from mentioning competitors or the specific price you paid for the product.
  • Do not include any personally identifiable information, such as full names.

Perfect Graphs: (Wiley Series in Discrete Mathematics & Optimization)

Required fields are marked with *

Review Title*
Review
    Add Photo Add up to 6 photos
    Would you recommend this product to a friend?
    Tag this Book Read more
    Does your review contain spoilers?
    What type of reader best describes you?
    I agree to the terms & conditions
    You may receive emails regarding this submission. Any emails will include the ability to opt-out of future communications.

    CUSTOMER RATINGS AND REVIEWS AND QUESTIONS AND ANSWERS TERMS OF USE

    These Terms of Use govern your conduct associated with the Customer Ratings and Reviews and/or Questions and Answers service offered by Bookswagon (the "CRR Service").


    By submitting any content to Bookswagon, you guarantee that:
    • You are the sole author and owner of the intellectual property rights in the content;
    • All "moral rights" that you may have in such content have been voluntarily waived by you;
    • All content that you post is accurate;
    • You are at least 13 years old;
    • Use of the content you supply does not violate these Terms of Use and will not cause injury to any person or entity.
    You further agree that you may not submit any content:
    • That is known by you to be false, inaccurate or misleading;
    • That infringes any third party's copyright, patent, trademark, trade secret or other proprietary rights or rights of publicity or privacy;
    • That violates any law, statute, ordinance or regulation (including, but not limited to, those governing, consumer protection, unfair competition, anti-discrimination or false advertising);
    • That is, or may reasonably be considered to be, defamatory, libelous, hateful, racially or religiously biased or offensive, unlawfully threatening or unlawfully harassing to any individual, partnership or corporation;
    • For which you were compensated or granted any consideration by any unapproved third party;
    • That includes any information that references other websites, addresses, email addresses, contact information or phone numbers;
    • That contains any computer viruses, worms or other potentially damaging computer programs or files.
    You agree to indemnify and hold Bookswagon (and its officers, directors, agents, subsidiaries, joint ventures, employees and third-party service providers, including but not limited to Bazaarvoice, Inc.), harmless from all claims, demands, and damages (actual and consequential) of every kind and nature, known and unknown including reasonable attorneys' fees, arising out of a breach of your representations and warranties set forth above, or your violation of any law or the rights of a third party.


    For any content that you submit, you grant Bookswagon a perpetual, irrevocable, royalty-free, transferable right and license to use, copy, modify, delete in its entirety, adapt, publish, translate, create derivative works from and/or sell, transfer, and/or distribute such content and/or incorporate such content into any form, medium or technology throughout the world without compensation to you. Additionally,  Bookswagon may transfer or share any personal information that you submit with its third-party service providers, including but not limited to Bazaarvoice, Inc. in accordance with  Privacy Policy


    All content that you submit may be used at Bookswagon's sole discretion. Bookswagon reserves the right to change, condense, withhold publication, remove or delete any content on Bookswagon's website that Bookswagon deems, in its sole discretion, to violate the content guidelines or any other provision of these Terms of Use.  Bookswagon does not guarantee that you will have any recourse through Bookswagon to edit or delete any content you have submitted. Ratings and written comments are generally posted within two to four business days. However, Bookswagon reserves the right to remove or to refuse to post any submission to the extent authorized by law. You acknowledge that you, not Bookswagon, are responsible for the contents of your submission. None of the content that you submit shall be subject to any obligation of confidence on the part of Bookswagon, its agents, subsidiaries, affiliates, partners or third party service providers (including but not limited to Bazaarvoice, Inc.)and their respective directors, officers and employees.

    Accept

    Fresh on the Shelf


    Inspired by your browsing history


    Your review has been submitted!

    You've already reviewed this product!