Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Colouring Preliminaries Read chapter Read first chapter

2002 | OriginalPaper | Chapter

The Method of Conditional Expectations

Authors : Michael Molloy, Bruce Reed

Published in: Graph Colouring and the Probabilistic Method

Publisher: Springer Berlin Heidelberg

Included in: Professional Book Archive

Get Access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Throughout this chapter, we consider hypergraphs for which the expected number of monochromatic edges in a uniformly random 2-colouring is less than one. To begin, we present an efficient algorithm, due to Erdős and Selfridge [46] for finding proper 2-colourings of such hypergraphs.

previous chapter The Asymptotics of Edge Colouring Multigraphs
next chapter Algorithmic Aspects of the Local Lemma
Metadata
Title
The Method of Conditional Expectations
Authors
Michael Molloy
Bruce Reed
Copyright Year
2002
Publisher
Springer Berlin Heidelberg
Book
Graph Colouring and the Probabilistic Method

Print ISBN: 978-3-642-04015-3

Electronic ISBN: 978-3-642-04016-0

Copyright Year: 2002

DOI
https://doi.org/10.1007/978-3-642-04016-0_24