复旦大学：《离散数学》PPT教学课件（赵一鸣）20/28

2. Region(face) colourings Definitions 46: A edge of the graph is called a bridg if the edge is not in any circuit. a connected planar graph is called a map, If the graph has not any bridge Definition 47: A proper region coloring of a map g is an assignment of colors to the region of G, one color to each region, such that adiacent regions receive different colors. An proper region coloring in which k colors are used is a k-region coloring. A map g is k-region colorable if there exists an s coloring of g for some s sk. The minimum integer k for which G is k- region colorable is called the region chromatic number. We denoted by x (G). If x (G) k, then g is k-region chromatic

▪ 2. Region(face) colourings ▪ Definitions 46: A edge of the graph is called a bridge, if the edge is not in any circuit. A connected planar graph is called a map, If the graph has not any bridge. ▪ Definition 47: A proper region coloring of a map G is an assignment of colors to the region of G, one color to each region, such that adjacent regions receive different colors. An proper region coloring in which k colors are used is a k-region coloring. A map G is k-region colorable if there exists an s￾coloring of G for some s  k. The minimum integer k for which G is k- region colorable is called the region chromatic number. We denoted by *(G). If *(G) = k, then G is k-region chromatic

Four Colour Conjecture Every map(plane graph) is 4-region colourable Definition 48: Let g be a connected plane graph. Construct a dual gd as follows: PLace a vertex in each region of G; this forms the vertex set of gd. 2)Join two vertices of Gd by an edge for each edge common to the boundaries of the two corresponding regions of G 3)Add a loop at a vertex v of Gd for each bridge that belongs to the corresponding region of G. moreover, each edge of ga is drawn to cross the associated edge of G, but no other edge of g or gd

▪ Four Colour Conjecture Every map (plane graph) is 4-region colourable. ▪ Definition 48：Let G be a connected plane graph. Construct a dual Gd as follows: ▪ 1)Place a vertex in each region of G; this forms the vertex set of Gd . ▪ 2)Join two vertices of Gd by an edge for each edge common to the boundaries of the two corresponding regions of G. ▪ 3)Add a loop at a vertex v of Gd for each bridge that belongs to the corresponding region of G. Moreover, each edge of Gd is drawn to cross the associated edge of G, but no other edge of G or Gd

Theorem 5.31 Every planar graph with no loop is 4-colourable if and only if its dual is 4-region colourable

▪ Theorem 5.31 Every planar graph with no loop is 4-colourable if and only if its dual is 4-region colourable

3. Edge colorings Definition 49: An proper edge coloring of a graph g is an assignment of colors to the edges of G, one color to each edge, such that adjacent edges receive different colors. An edge coloring in which k colors are used is a k-edge coloring. a graph g is k-edge colorable if there exists an s-edge coloring of G for some ss k. The minimum integer k for which G is k-edge colorable is called the edge chromaticumber or the chromatic index x'(G) of G. If x' (G)=k, then g is k-edge chromatic

▪ 3. Edge colorings ▪ Definition 49:An proper edge coloring of a graph G is an assignment of colors to the edges of G, one color to each edge, such that adjacent edges receive different colors. An edge coloring in which k colors are used is a k-edge coloring. A graph G is k-edge colorable if there exists an s-edge coloring of G for some s k. The minimum integer k for which G is k-edge colorable is called the edge chromaticumber or the chromatic index ’(G) of G. If ’(G) = k, then G is k-edge chromatic

4. Chromatic polynomials Definition 50: LetG =(, e) be a simple graph We let pg(h)denote the number of wavs of proper coloring the vertices of G with k colors P will be called the chromatic function of g Example For the graphG PG(h)=k(k-1)2

▪ 4. Chromatic polynomials ▪ Definition 50: Let G =(V, E) be a simple graph. We let PG(k) denote the number of ways of proper coloring the vertices of G with k colors. PG will be called the chromatic function of G. ▪ Example For the graph G PG(k) =k (k-1) 2

IfG =(e)with v= n ande =o, then G consists of n isolated points and by the product rule pg(h)=k IfG =Kn, the complete graph on n vertices, then at least n colors must be available for a proper coloring of G. Here by the product rue Pc()=k(k-1)(k-2)、k-n+1). We see that for k n, PG(k)=0, which indicates there is no proper k-coloring of Kn

▪ If G = (V, E ) with |V | = n and E =, then G consists of n isolated points, and by the product rule PG(k ) = k n . ▪ If G =Kn , the complete graph on n vertices, then at least n colors must be available for a proper coloring of G. Here, by the product rule ▪ P G(k ) = k (k-1)(k-2)...(k-n + 1). ▪ We see that for k < n, P G(k ) = 0, which indicates there is no proper k -coloring of Kn