5.9.2 Characterizations of Planar Graphs 1930 Kuratowski(库拉托斯基) Two basic nonplanar graphs: Ks and K3.3
▪ 5.9.2 Characterizations of Planar Graphs ▪ 1930 ▪ Kuratowski (库拉托斯基) ▪ Two basic nonplanar graphs: K5 and K3,3
Definition 43: If a graph is planar, so will be any graph obtained by omitted an edge u, vl and adding a new vertex w together with edges u, w) and ww, vg. Such an operation is called an elementary subdivision Definition 44: The graphS G(VE1 and G2=(V2,E2)are called homeomorphic if they can be obtained from the same graph by a sequence of elementary subdivisions
▪ Definition 43: If a graph is planar, so will be any graph obtained by omitted an edge {u,v} and adding a new vertex w together with edges {u,w} and {w,v}. Such an operation is called an elementary subdivision. ▪ Definition 44: The graphs G1=(V1 ,E1 ) and G2=(V2 ,E2 ) are called homeomorphic if they can be obtained from the same graph by a sequence of elementary subdivisions
Theorem 5.29: (1)IfG has a subgraph homeomorphic to Kn, then there exists at least n vertices with the degree more than or equal n (2)IfG has a subgraph homeomorphic to K then there exists at least 2n vertices with the degree more than or equal n. Example: Let G=(V,E), V=7. IfG has a subgraph homeomorphic to Ks, then G has not any subgraph homeomorphic to 3. 3 or
▪ Theorem 5.29: (1)If G has a subgraph homeomorphic to Kn , then there exists at least n vertices with the degree more than or equal n-1. ▪ (2) If G has a subgraph homeomorphic to Kn,n, then there exists at least 2n vertices with the degree more than or equal n. ▪ Example: Let G=(V,E)，|V|=7. If G has a subgraph homeomorphic to K5 , then has not any subgraph homeomorphic to K3.3 or K5 . G
Theorem 5.30: Kuratowski's Theorem (1930) a graph is planar if and only if it contains no subgraph that is homeomorphic of Ks or K3.3 (1)If G is a planar graph, then it contains no subgraph that is homeomorphic of K 5, and it contains no subgraph that is homeomorphic of K3.3 (2)If a graph g does contains no subgraph that is homeomorphic of ks and it contains no subgraph that is homeomorphic of K33 then g is a planar graph (3)If a graph g contains a subgraphs that is homeomorphic of Ks, then it is a nonplanar graph If a graph g contains a subgraph that is homeomorphic of K3.3, then it is a nonplanar graph. (4)If G is a nonplanar graph, then it contains a subgraph that is homeomorphic of Ks or K3.3
▪ Theorem 5.30: Kuratowski’s Theorem (1930). A graph is planar if and only if it contains no subgraph that is homeomorphic of K5 or K3,3. ▪ (1)If G is a planar graph, then it contains no subgraph that is homeomorphic of K5 , and it contains no subgraph that is homeomorphic of K3,3 ▪ (2)If a graph G does contains no subgraph that is homeomorphic of K5 and it contains no subgraph that is homeomorphic of K33 then G is a planar graph ▪ (3)If a graph G contains a subgraphs that is homeomorphic of K5 , then it is a nonplanar graph. If a graph G contains a subgraph that is homeomorphic of K3,3, then it is a nonplanar graph. ▪ (4)If G is a nonplanar graph, then it contains a subgraph that is homeomorphic of K5 or K3,3
Example: Let=(V,E), V=7. IfG has a subgraph homeomorphic to Ks, then it is a nonplanar graph, and G is a planar graph
▪ Example: Let G=(V,E)，|V|=7. If G has a subgraph homeomorphic to K5 , then it is a nonplanar graph, and is a planar graph. G
5.9.3 Graph Colourings 1. Vertex colourings Definitions 45: A proper colouring of a graph g with no loop is an assignment of colours to the vertices of G, one colour to each vertex, such that adjacent vertices receive different colours. A proper colouring in which k colours are used is a k-colouring. A graph G is k-colourable if there exists a S-colouring of G for some s<k The minimum integer k for which g is k- colourable is called the chromatic number. We denoted by X(G).If x(G=k, then g is k-chromatic
5.9.3 Graph Colourings ▪ 1.Vertex colourings ▪ Definitions 45:A proper colouring of a graph G with no loop is an assignment of colours to the vertices of G, one colour to each vertex, such that adjacent vertices receive different colours. A proper colouring in which k colours are used is a k-colouring. A graph G is k-colourable if there exists a s-colouring of G for some s ≤ k. The minimum integer k for which G is kcolourable is called the chromatic number. We denoted by (G). If (G) = k, then G is k-chromatic
米
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 scoloring 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