𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A New Proof of the H -Coloring Dichotomy

✍ Scribed by Siggers, Mark H.

Book ID
118197767
Publisher
Society for Industrial and Applied Mathematics
Year
2010
Tongue
English
Weight
153 KB
Volume
23
Category
Article
ISSN
0895-4801

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A new proof of the 6 color theorem
A new proof of the 6 color theorem
✍ Oleg V. Borodin πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 579 KB

## Abstract In 1965 Ringel raised a 6 color problem for graphs that can be stated in at least three different forms. In particular, is it possible to color the vertices and faces of every plane graph with 6 colors so that any two adjacent or incident elements are colored differently? This 6 color p

A new proof of the colored Kruskalβ€”Katon
A new proof of the colored Kruskalβ€”Katona theorem
✍ Eran London πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 386 KB

An extension of the Kruskal-Katona theorem to colored hypergraphs was given by Frankl, Fiiredi and Kalai in [Shadows of colored complexes, Mathematics Scandinavica]. Here we give a new simple proof.

A short proof of the NP-completeness of
A short proof of the NP-completeness of minimum sum interval coloring
✍ DΓ‘niel Marx πŸ“‚ Article πŸ“… 2005 πŸ› Elsevier Science 🌐 English βš– 154 KB

In the minimum sum coloring problem we have to assign positive integers to the vertices of a graph in such a way that neighbors receive different numbers and the sum of the numbers is minimized. Szkalicki has shown that minimum sum coloring is NP-hard for interval graphs. Here we present a simpler p