Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Gaps in the chromatic spectrum of face-constrained plane graphs. | Gaps in the chromatic spectrum of face-constrained plane graphs Daniel Kobler The Fields Institute 222 College St. Toronto Ont. M5T 3J1 Canada dkobler@ Andre Kundgen Department of Computer Science University of Toronto Toronto Ont. M5S 3G4 Canada kundgen@ Submitted December 20 2000 Accepted March 23 2001. MR Subject Classifications 05C15 Abstract Let G be a plane graph whose vertices are to be colored subject to constraints on some of the faces. There are 3 types of constraints a C indicates that the face must contain two vertices of a Common color a D that it must contain two vertices of a Different color and a B that Both conditions must hold simultaneously. A coloring of the vertices of G satisfying the facial constraints is a strict k-coloring if it uses exactly k colors. The chromatic spectrum of G is the set of all k for which G has a strict k-coloring. We show that a set of integers S is the spectrum of some plane graph with face-constraints if and only if S is an interval s s 1 . t with 1 s 4 or S 2 4 5 . t . there is a gap at 3. Keywords colorings of hypergraphs mixed hypergraphs planar graphs and hypergraphs colorability chromatic spectrum. 2000 Mathematics Subject Classification 05C15. All graphs and hypergraphs in this paper will be loopless . contain no edges of size 1. The problem we consider can be stated in the more general framework of mixed hypergraphs originally proposed by Voloshin 4 5 . A mixed hypergraph is a triple H V C D where V is the vertex set and C and D are families of subsets of V called the C-edges and D-edges. A strict k-coloring of a mixed hypergraph is a surjective mapping Supported by the Swiss National Fund and the Fields Institute. Supported by NSERC grant of Derek Corneil and the CS Theory group. THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 N3 1 c V 1 2 . k from the vertex set V into a set of k colors so that each C-edge contains at least two vertices with a Common color and each P-edge .
