文档介绍：EXdmples
dnd Counterexdmples
in Grdph Theory
Michdel Cdpobidnco
John C. Molluzzo
St. John's University, New York
Staten Island Campus
Foreword by Gdry Chdrtrdnd
Western Michigan University
~ NORTH-HOLLAND· NEW YORK
~ NEW YORK • AMSTERDAM • OXFORD
Elsevier North-Holland, Inc.
52 Vanderbilt Avenue, New York, New York 10017
Distributors outside the United States and Canada:
THOMOND BOOKS
(A Division of Elsevier/North-Holland
SCIentific Publishers, Ltd.)
. Box 85
Limerick, Ireland
© 1978 by Elsevier North-Holland, Inc.
Library of Congress Cataloging in Publication Data
Capobianco, Michael.
Examples and counterexamples in graph theory.
Bibliography: p.
Includes index.
1. Graph theory. I. Mulluzzo, John, JOInt author. II. TItle.
511'.5 77-26857
ISBN 0-444-00255-3
Manufactured in the United States of America
To Teresa and Alberta,
our graph theory widows
Contents
Foreword IX
Preface xi
1. COLORINGS 1
1. Introduction 1
2. Point Colorings 1
3. Line Chromatic Number 12
4. The Total Chromatic Number 13
5. The Achromatic Number 14
2. CONNECTEDNESS 17
3. INDEPENDENCE AND COVERINGS 29
4. EXTREMAL PROBLEMS 39
1. Ramsey Numbers 39
2. Generalized Ramsey Numbers 44
3. Other Extremal Problems 47
5. GRAPH-VALUED FUNCTIONS 59
1. Introduction 59
2. Line Graphs 59
3. Total Graphs 69
4. Entire Graphs 73
5. Sums and Products of Graphs 78
6. Some Handy Tables 86
6. GROUPS 89
1. The Automorphism Groups of a Graph 89
2. Symmetry in Graphs 94
3. Graphs with Given Group and Properties 101
7. TOPOLOGICAL QUESTIONS 115
1. Introduction 115
2. Planar Graphs 115
3. Outerplanar Graphs 122
4. Non-planar Graphs 124
v;;
Contents
8. GRAPH RECONSTRUCTION f35
1. Introduction 135
2. The Original Reconstruction Problem 139
3. Reconstruction from the Set of
Non-Isomorphic Gi 's 142
4. Reconstruction from the Collection G - {Vi} where
Vi is a Pendant Vertex 144
5. The Line Reconstruction