A Guide to Graph Colouring Algorithms and Applications
This book treats graph colouring as an algorithmic problem, with a strong emphasis on practical applications. The author describes and analyses some of the best-known algorithms for colouring arbitrary graphs, focusing on whether these heuristics can prov
- PDF / 3,366,477 Bytes
- 256 Pages / 453.543 x 683.15 pts Page_size
- 86 Downloads / 298 Views
A Guide to Graph Colouring Algorithms and Applications
A Guide to Graph Colouring
R.M.R. Lewis
A Guide to Graph Colouring Algorithms and Applications
123
R.M.R. Lewis Cardiff School of Mathematics Cardiff University Cardiff UK
ISBN 978-3-319-25728-0 DOI 10.1007/978-3-319-25730-3
ISBN 978-3-319-25730-3
(eBook)
Library of Congress Control Number: 2015954340 Springer Cham Heidelberg New York Dordrecht London © Springer International Publishing Switzerland 2016 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. Printed on acid-free paper Springer International Publishing AG Switzerland is part of Springer Science+Business Media (www.springer.com)
For Fifi, Maiwen, Aoibh, and Macsen. Gyda cariad.
Preface
Graph colouring is one of those rare examples in the mathematical sciences of a problem that is very easy to state and visualise, but that has many aspects that are exceptionally difficult to solve. Indeed, it took more than 160 years and the collective efforts of some of the most brilliant minds in nineteenth and twentieth century mathematics just to prove the simple sounding proposition that “four colours are sufficient to properly colour the vertices of a planar graph”. Ever since the notion of “colouring” graphs was first introduced by Frances Guthrie in the mid-1800s, research into this problem area has focussed mostly on its many theoretical aspects, particularly concerning statements on the chromatic number for specific topologies such as planar graphs, line graphs, random graphs, critical graphs, triangle free graphs, and perfect graphs. Excellent reviews on these matters, together with a comprehensive list of open problems in the field of graph colouring, can be found in the books of Jensen and Toft (1994) and Beineke and Wilson (2015). In this book, our aim is to examine graph colouring as an algorithmic problem, with a strong emphasis on practical applications. In particular, we take some time to describe and analyse some of the best-known algorithms for colouring
Data Loading...
