V. Voloshin. Coloring Mixed Hypergraphs: theory, algorithms and applications.

© Monograph, PUBLISHED by the AMS

Contents

Introduction

0.1 Overview of Graph Coloring
0.2 Mixed Hypergraphs and their Coloring
0.3 Unforeseen Features of Mixed Hypergraph Coloring
0.4 Philosophical Motivation 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.1Invertors, 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
12.10 Natural number interpretation

Back to Home Page