V. Voloshin
Coloring Mixed Hypergraphs: Theory, Algorithms and Applications
Cite this book (BibTeX)
Use the following BibTeX entry for references and bibliographies.
Contents
Introduction
0.1 Overview of Graph Coloring
0.2 Mixed Hypergraphs and their Coloring
0.3 Unforeseen Features of Mixed Hypergraph Coloring
0.5 Organization
0.6 Acknowledgments
Chapter 1. The Lower Chromatic Number of a Hypergraph
1.1 General concepts
1.2 A brief history of Coloring Theory
1.2.1 The Four-Color Problem
1.2.2 Perfect Graphs
1.2.3 Coloring the edges of a graph
1.2.4 Coloring of hypergraphs
1.3 Basic results on hypergraph coloring
1.3.1 Particular kinds of hypergraph coloring
1.3.2 A greedy hypergraph coloring algorithm
1.4 Hypertrees and chordal conformal hypergraphs
Chapter 2. Mixed Hypergraphs and the Upper Chromatic Number
2.1 Basic definitions
2.2 Splitting-contraction algorithm
2.3 Basic properties of the upper chromatic number
2.4 Greedy C-hypergraph coloring algorithms
2.5 Algorithmic complexity
2.6 Open problems
Chapter 3. Uncolorable Mixed Hypergraphs
3.1 Minimal uncolorable mixed hypergraphs
3.2 Uncolorability measures and a greedy algorithm
3.3 Colorability as an integer programming problem
3.4 Special types of uncolorable mixed hypergraphs
3.4.1 Complete (l,m)-uniform uncolorable mixed hypergraphs
3.4.2 A construction from subpaths of a graph
3.4.3 Colorability of mixed hypertrees
3.5 Open problems
Chapter 4. Uniquely Colorable Mixed Hypergraphs
4.1 Preliminary
4.2 Embeddings into UC
4.3 Separation on UC subhypergraphs
4.4 Recursive operations
4.4.1 Subset contraction
4.4.2 Orderings and unique colorability
4.5 Algorithmic complexity
4.6 UC mixed hypergraphs with χ ≥ n-2
4.7 Uniquely colorable mixed hypertrees
4.7.1 Invertors, redundant C-edges and touching graphs
4.7.2 UC-ordering algorithm
4.8 Open problems
Chapter 5. C-Perfect Mixed Hypergraphs
5.1 Basic concepts
5.2 Minimal non C-perfect mixed hypergraphs
5.3 C-perfection of mixed hypertrees
5.4 Algorithmic aspects of C-perfection
5.5 Open problems
Chapter 6. Gaps in the Chromatic Spectrum
6.1 The smallest mixed hypergraphs with gaps
6.2 Feasible sets and a doubling-shifting algorithm
6.3 Smaller realization
6.4 0-1 realization
6.5 Uniform bihypergraphs may have gaps
6.6 Separation on UC preserves continuity
6.7 Open problems
Chapter 7. Interval Mixed Hypergraphs
7.1 Colorings
7.2 Linear time algorithm for the upper chromatic number
7.3 Chromatic spectrum is continuous
7.4 Open problems
Chapter 8. Pseudo-chordal Mixed Hypergraphs
8.1 Preliminaries
8.2 Chromatic polynomial
8.3 Consequences and examples
8.4 A universal formula for chordal graphs
8.5 Open problems
Chapter 9. Circular Mixed Hypergraphs
9.1 Preliminaries
9.2 Unique colorability, n even
9.3 Unique colorability, n odd
9.4 Colorability and lower chromatic number
9.5 Upper chromatic number
9.6 Open problems
Chapter 10. Planar Mixed Hypergraphs
10.1 Classic planar hypergraphs
10.2 Coloring bitriangulations
10.3 Bounds for the upper chromatic number
10.4 Gap in the chromatic spectrum
10.5 Open problems
Chapter 11. Coloring Block Designs as Mixed Hypergraphs
11.1 Steiner systems
11.2 Steiner triple systems
11.3 Steiner quadruple systems
11.4 Open problems
Chapter 12. Modelling with Mixed Hypergraphs
12.1 List colorings without lists
12.2 Ramsey, anti-Ramsey and related problems
12.3 Mixed hypergraphs and integer programming
12.4 Resource allocation
12.5 Lifetime of set systems
12.6 Parallel computing
12.7 Data Base Management
12.8 Molecular biology
12.9 Genetics of populations