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

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

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

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

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

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

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

7.1 Colorings

7.2 Linear time algorithm for the upper chromatic number

7.3 Chromatic spectrum is continuous

7.4 Open problems

8.1 Preliminaries

8.2 Chromatic polynomial

8.3 Consequences and examples

8.4 A universal formula for chordal graphs

8.5 Open problems

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

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

11.1 Steiner systems

11.2 Steiner triple systems

11.3 Steiner quadruple systems

11.4 Open problems

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