Coloring Mixed Hypergraphs : Theory, Algorithms, and Applications

By: Vitaly I. Voloshin

Write A Review

Hardcover

At a Glance

Hardcover
181 Pages

Dimensions(cm)
25.4 x 17.78 x 1.91

Hardcover

$152.25

or 4 interest-free payments of $38.06 with

Aims to ship in 15 to 25 business days

The theory of graph coloring has existed for more than 150 years. Historically, graph coloring involved finding the minimum number of colors to be assigned to the vertices so that adjacent vertices would have different colors. From this modest beginning, the theory has become central in discrete mathematics with many contemporary generalizations and applications. Generalization of graph coloring-type problems to mixed hypergraphs brings many new dimensions to the theory ofcolorings. A main feature of this book is that in the case of hypergraphs, there exist problems on both the minimum and the maximum number of colors. This feature pervades the theory, methods, algorithms, and applications of mixed hypergraph coloring. The book has broad appeal. It will be of interest to bothpure and applied mathematicians, particularly those in the areas of discrete mathematics, combinatorial optimization, operations research, computer science, software engineering, molecular biology, and related businesses and industries. It also makes a nice supplementary text for courses in graph theory and discrete mathematics. This is especially useful for students in combinatorics and optimization. Since the area is new, students will have the chance at this stage to obtain results that maybecome classic in the future.

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Mathematics Combinatorics & Graph Theory Computing & I.T.Computer Science Mathematical Theory of Computation Discrete Mathematics

Preface	p. xiii
Introduction	p. 1
Overview of graph coloring	p. 1
Mixed hypergraphs and their coloring	p. 3
Unforeseen features of mixed hypergraph coloring	p. 3
Philosophical motivation of mixed hypergraph coloring	p. 4
Organization	p. 5
Acknowledgments	p. 9
The Lower Chromatic Number of a Hypergraph	p. 11
General concepts	p. 11
A brief history of coloring theory	p. 16
Basic results on hypergraph coloring	p. 19
Hypertrees and chordal conformal hypergraphs	p. 23
Mixed Hypergraphs and the Upper Chromatic Number	p. 27
Basic definitions	p. 27
Splitting-contraction algorithm	p. 30
Basic properties of the upper chromatic number	p. 34
Greedy C-hypergraph coloring algorithms	p. 37
Algorithmic complexity	p. 42
Open problems	p. 43
Uncolorable Mixed Hypergraphs	p. 45
Minimal uncolorable mixed hypergraphs	p. 45
Uncolorability measures and a greedy algorithm	p. 48
Colorability as an integer programming problem	p. 52
Special types of uncolorable mixed hypergraphs	p. 54
Open problems	p. 57
Uniquely Colorable Mixed Hypergraphs	p. 59
Preliminary	p. 59
Embeddings into uc mixed hypergraphs	p. 60
Separation using uc subhypergraphs	p. 61
Recursive operations	p. 63
Algorithmic complexity	p. 67
UC mixed hypergraphs with x [greater than or equal] n - 2	p. 67
Uniquely colorable mixed hypertrees	p. 71
Open problems	p. 76
C-perfect Mixed Hypergraphs	p. 79
Basic concepts	p. 79
Minimal non-C-perfect mixed hypergraphs	p. 81
C-perfection of mixed hypertrees	p. 84
Algorithmic aspects of C-perfection	p. 85
Open problems	p. 86
Gaps in the Chromatic Spectrum	p. 89
The smallest mixed hypergraphs with gaps	p. 89
Feasible sets and a doubling-shifting algorithm	p. 91
Smaller realization	p. 93
0-1 realization	p. 95
Uniform bihypergraphs may have gaps	p. 96
Separation on uc preserves continuity	p. 98
Open problems	p. 99
Interval Mixed Hypergraphs	p. 101
Colorings	p. 101
Linear time algorithm for the upper chromatic number	p. 104
Chromatic spectrum is continuous	p. 105
Open problems	p. 106
Pseudo-chordal Mixed Hypergraphs	p. 107
Preliminaries	p. 107
Chromatic polynomial	p. 109
Consequences and examples	p. 111
A universal formula for chordal graphs	p. 115
Open problems	p. 117
Circular Mixed Hypergraphs	p. 119
Preliminaries	p. 119
Unique colorability, n even	p. 121
Unique colorability, n odd	p. 123
Colorability and lower chromatic number	p. 125
Open problems	p. 127
Planar Mixed Hypergraphs	p. 129
Classic planar hypergraphs	p. 129
Coloring bitriangulations	p. 130
Bounds for the upper chromatic number	p. 135
Gaps in the chromatic spectrum	p. 137
Open problems	p. 138
Coloring Block Designs as Mixed Hypergraphs	p. 141
Steiner systems	p. 141
Steiner triple systems	p. 143
Steiner quadruple systems	p. 149
Open problems	p. 153
Modelling with Mixed Hypergraphs	p. 155
List colorings without lists	p. 155
Ramsey, anti-Ramsey and related problems	p. 156
Mixed hypergraphs and integer programming	p. 158
Resource allocation	p. 162
Lifetime of set systems	p. 165
Parallel computing	p. 165
Database management	p. 165
Molecular biology	p. 166
Genetics of populations	p. 168
Natural number interpretation	p. 169
Bibliography	p. 171
List of Figures	p. 179
Index	p. 181
Table of Contents provided by Syndetics. All Rights Reserved.

Coloring Mixed Hypergraphs : Theory, Algorithms, and Applications

At a Glance

Hardcover

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Mathematical Theory of Computation

Hands-On Generative AI with Transformers and Diffusion Models

Algorithms in C, Parts 1-4

3rd Edition - Fundamentals, Data Structures, Sorting, Searching

Machine Learning Interviews

Kickstart Your Machine Learning Career

Effective Machine Learning Teams

Best Practices for ML Practitioners

Practical Weak Supervision

Doing More with Less Data

Machine Learning Pocket Reference

Working with Structured Data in Python

Microsoft 365 Copilot At Work

Using AI to Get the Most from Your Business Data and Favorite Apps

Estimation of Mutual Information

Behaviormetrics: Quantitative Approaches to Human Behavior

Institution-Independent Model Theory

Studies in Universal Logic

Quantum Biocomputing in Quantum Biology Volume I

Arithmetic and Combinational Circuits

Quantum Computing Strategy

Foundations and Applicability

Initial Algebras and Terminal Coalgebras

The Theory of Fixed Points of Functors

Quantum Biocomputing in Quantum Biology Volume II

Memory Devices, Programmable Logic Devices, Nanoprocessors, Heat, Speed, and Data Related Issues

GenAI on AWS

A Practical Approach to Building Generative AI Applications on AWS

Advances in Machine Learning and Big Data Analytics II

ICMLBDA 2023, NIT Arunachal Pradesh, India, May 29-30

Planetary Spacecraft Navigation

General Relativity for Planetary Navigation

Quantum Computing Strategy

Foundations and Applicability

Frontiers of Algorithmics

18th International Joint Conference, IJTCS-FAW 2024, Hong Kong SAR, China, July 29-31, 2024, Proceedings

Machine Learning Production Systems

Engineering Machine Learning Models and Pipelines

The Computer Algebra System Oscar

Algorithms and Examples

Time Series Analysis and Forecasting

Selected Contributions from ITISE 2023

Theory of Computation

Automata, Formal Languages, Computation and Complexity

Effective DevOps

PyTorch Pocket Reference

Building and Deploying Deep Learning Models

This product is categorised by