GRAPHS AND THEIR CHROMATIC NUMBERS- Thesis for the Dogree of Ph. D. MICHIGAN STATE UNIVERSITY Mahdi Behzad I965 Immummzmmm y 3 1293 170714 3335 x_ Michigan Sm; University This is to certify that the thesis entitled Graphs and their Chromatic Numbers | presented by I Mahdi Behzad has been accepted towards fulfillment l of the requirements for 1 Ph.D. degree in Mathematics éwflm Major professor Date Sept. 11+, 1965 0-189 ABSTRACT GRAPHS AND THEIR CHROMATIC NUMBERS by Mehdi Behzad Two well known numbers associated with a graph G are the (vertex) chromatic number and edge chromatic number, which we denote by kV(G) and ke(G), respectively. Although these concepts are nearly as old as the four color conjecture (whose origin is around 18UO), and although much research has been done in this area, no systematic study of a general nature has been made of chromatic numbers. In the thesis we introduce another chromatic number kt(G), the total chromatic number of G, which is defined to be the minimum number of colors required to color both the edges and vertices of G in such a way that (1) two adjacent vertices are colored differently, (ii) two adjacent edges are colored differently, and (iii) each edge is colored differently than its incident vertices. In addition, for each graph G we define an associated graph T(G), called the total graph of G, having the property that the total chromatic number of G equals the vertex chromatic number of T(G). Mehdi Behzad It is our purpose in this thesis to add to the knowledge of vertex and edge chromatic numbers and to study total chromatic numbers and total graphs. In Section 1, an introduction to the thesis is pre— sented. The following section consists of some of the more basic definitions and a brief history of the literature in which we include those theorems which have inspired us throughout the thesis. In Section 3, we concern ourselves with establishing some basic results dealing with edge chromatic numbers. For example, formulas are obtained for the edge chromatic numbers of special classes of graphs. Moreover, it is proved that if G is a graph with maximum degree 3, then ke(G) ; A. This result is then immediately extended to give us the following theorem: if G is a graph of order n, and maximum degree p, p g 3, then ke (G) ; min (2p-2, 2(2) -l). Edge and vertex critical graphs relative to the edge chromatic number are the major tOpics investigated in the fourth section. Several results pertaining to cut vertices, blocks, and connectivity properties in general are given. We discuss fundamental properties of the total chromatic number and critical graphs relative to the total chromatic number in Sections 5 and 6, respectively. In Section 7, the total graph is introduced. It is here that we prove that if G is a graph of order n and n maximum degree p, p ; 2, then kt(G) E_min (2p, 2[§] +1). Mehdi Behzad Furthermore, several numerical results on the number of triangles in iterated total graphs of regular graphs are obtained. In the next section we characterize graphs with planar total graphs as those graphs whose vertices have degree at most three and if the degree of a vertex is three, it is a cut vertex. The thesis is concluded with Section 9 in which we present results concerning total graphs and Eulerian and Hamiltonian graphs. The major theorem of the section is: if G is any non-trivial connected graph, then T(T(G)) is Hamiltonian. GRAPHS AND THEIR CHROMATIC NUMBERS By Mehdi Behzad A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1965 ACKNOWLEDGMENTS Words can hardly suffice to thank Professor E. A. Nordhaus, under whose inspiration, guidance, and encourage- ment this research was undertaken. For all he has done for me, I am deeply thankful. The author also wishes to indicate his gratitude to Dr. Gary Chartrand for his ever helpful suggestions and constant interest. He is also indebted to Professors Branko Grunbaum, Frank Harary, L. M. Kelly, and B. M. Stewart for their gen- erous help and suggestions. To Professors W. E. Deskins and J. G. Hocking go my sincere thanks for serving on my guidance committee and their interest. DEDICATION to my Father, and N. 111 TABLE OF CONTENTS Page ACKNOWLEDGMENTS. . . . . . . . . . . . . ii Chapter I. PRELIMINARIES . . . . . . . . . . . 1 Introduction . . . . . l Fundamental Definitions and Known Results. . 3 II. THE EDGE CHROMATIC NUMBER . . . . . . . 10 Basic Results . . . . 10 Critical Graphs Relative to the Edge Chromatic Number . . . . . . . . . 19 III. THE TOTAL CHROMATIC NUMBER. . . . . . . 28 Basic Results . . . . . . . . 28 Critical Graphs Relative to the Total Chromatic Number . . . . . . . 37 IV. TOTAL GRAPHS . . . . . . . . . . . Al Fundamental Properties and Preliminary Results . . . . . . . . . Al Planarity of Total Graphs . . . . . . A9 Total Graphs and Hamilton Circuits . . . . 5A INDEX OF DEFINITIONS . . . . . . . . . . . 58 BIBLIOGRAPHY. . . . . . . . . . . . . . 60 iv CHAPTER I PRELIMINARIES Sectionll Introduction With every ordinary graph G, there are associated two non—negative integers, kv(G), and ke(G), called the vertex chromatic number and the edge chromatic number of G, respecv tively. These two concepts are probably two of the oldest terms in graph theory and are closely related to the celebrated four color conjecture, originated around lBAO. Despite the fact that many mathematicians have considered these tOpics, no systematic study of a general nature has been made for chromatic numbers of graphs. The term "vertex chromatic number" in the literature is usually abbreviated to "chromatic number.“ Also the term "edge chromatic" number is alternatively referred to as "the chromatic index" by Berge [I]. It is well known that with every nonempty ordinary graph G there is associated a graph L(G), called the line? graph of G such that the edge chromatic number of G is equal to the vertex chromatic number of L(G). We find it con- venient to associate with every ordinary graph G a number 1 called the total chromatic number, and a graph T(G), which we have termed the "total graph" of G, having the property that the total chromatic number of G is equal to the vertex chromatic number of T(G). Chapter I includes this introduction and some basic definitions along with a brief survey of the literature on the subject. Chapter II is devoted to results related to the edge chromatic number. In particular, the edge chromatic number of several important classes of graphs are obtained and upper boundsfkfl’the edge chromatic number are established. Critical graphs relative to the edge chromatic number and various connectivity questions are also investigated. In Chapter III analogous results fop‘total chromatic numbers are given. Various properties of total graphs are presented in Chapter IV. Among the theorems presented are those dealing with the characterization of graphs with a planar total graph and the existence of Eulerian and Hamiltonian total graphs. Section 2 Fundamental Definitions and Known Results Because of the lack of general agreement concerning definitions used in graph theory it is desirable to define the terms used frequently in this thesis. The graphs with which we are concerned are the ordinary graphs, that is, the finite undirected graphs without loops or multiple edges. In the sequel, a graph will refer to an ordinary graph. More precisely, a graph G consists of a finite nonempty set V, called the vertex set of G, and a set X of unordered pairs of distinct elements of V. Each element of X is called an gdgg of G. V(G) and X(G) denote the vertex set and the edge set of G, respectively. By an element of a graph G, we mean a vertex or an edge of G. I V I and I X I denote the cardinal numbers of the sets V and X, respectively. I V I is called the order of the graph. If I v I = I (so that I x I = 0), then G is called a trivial graph. If I v | = n and I x I = n (n-l) /2, then G is called a complete graph and is denoted by Kn' If we write V = Vl+ V2 as a disjoint union of nonempty subsets of V, and G = G(V) is such that no two vertices of V1, i = l, 2, are adjacent, then G is called a bipartite graph or a bigraph. If I Vl I = m and I V2 I = n, then the bigraph in which all mn edges are present is called a complete bi r“ h and is denoted b K or K . A t A t g ap_ y m,n n,m complete bigraph of the type Kl,n is referred to as a spa; £222- A graph G'(V', X') is a subgraph of a graph G(V ,X) if ¢ # V'fé V and X'gg X. If V' = V, then G' is called a spanning subgraph of G. If V' is a nonempty subset of V, the subgraph G'CV’) whose vertex SEt is V' and whose edge set is the set of all edges of G wnich join two vertices of V' is called the section graph of G determined by V'. An edge x of a graph G is called a circuit edge of G if x belongs to some circuit of G; otherwise, x is called a separating edge (or cut edge). A vertex v is a cut vertex (or separating vertex) of G if its removal (and necessarily all edges incident with it) results in a graph whose number of components is greater than that of G. A plppk_of a graph G is a maximal connected section graph of G containing no cut vertices of itself. A block of G is called a terminal block if it contains only one cut vertex cf G. The thickness t(G) of a graph G having at least one edge is the minimum number of pairwise edge-disjoint planar subgraphs of G whose sum is G. The line—graph L(G) of a nonempty graph G is that graph whose vertex set can be put into a one-to—one corre— spondence with the edges of G in such a way that two vertices of L(G) are adjacent if and only if the corre« sponding edges of G are adjacent. The distance between two connected vertices of a graph is the length of a shortest are joining them. The square G2 of a graph G is that graph whose vertex set can be put into a one—to-one correspondence with the vertices of G in such a way that two vertices of G2 are adjacent if and only if the distance between the corre- sponding vertices of G is one or two. The number of vertices to which a vertex v is adjacent is called the degree 23.x and is denoted by deg (v). By maximum degree pf a gpapp G we mean the degree of a vertex which is maximal over the vertices of G. A graph all of whose vertices have the same degree is called a regular A graph G without isolated vertices is said to contain an Euler path if there exists a cyclic path in G containing every edge of G, and every such cyclic path is called an Euler path. A graph containing an Euler path is called an Eulerian graph. A graph G is called Hamiltonian if it contains a circuit passing through every vertex of G. G (V) and G' (V') are isomorphic if there (1) pk Q) (7—? ”q gr iw‘l o- exists a one-to—one correspondence between V and V' such that two vertices are joined by an edge in one graph if and only if the corresponding vertices are joined by an edge in the other graph. Two graphs are EZFSETEZEREE.if it is possible to insert new vertices of degree two into their edges in such r,- . a way that the two resulting graphs are lsomorp.l-. C) I I An itdeoendent set of vertices (edges) of a graph G is a subset of V (G) (X (G)) having the prOperty that no two vertices (edges) cf the subset are adjacent. The mini« 2)” mum number of sac independent sets into which V(G) (X(G)) can be partitioned is called the ypgtex (edge) chromatic number of G and is denoted by kv (G) (ke(G)). This number is the minimum number of colors required to color the vertlces (edges) 31 G so that no two adjacent vertices (edges) have the same COLOF. . .,_ Q. , r1”) . . ,- n , Finally, in the sequel IE] will denote the greatest integer not exceeding n/2, {f} the least integer not 2 1 - N 5 v V " ' 6 less than n/a, and mn the Kronecker delta, l.e. mn = O 6 . if m i n, and mn = l ll m = n. We now state some of the relevant known results and theorems which will prove useful to us later in the thesis. Although an extensive literature exists on the vertex chromatic number of a graph, the literature on the edge chromatic number is quite limited. A graph G is said to be p,- chromatic if the vertices of G can be colored with p or less colors in such a way that no two adjacent vertices have the same color. In 19H0, R. L. Brooks [3], proved the following theorem: Theorem of Brooks.--A graph G of maximum degree p is p - chromatic except in either of the two following cases: (i) p = 2, and one of the components of G is a circuit of odd length, (ii) a component of G is Kp+l° C. Berge [1] shows that the edge chromatic number of a regular graph of degree three is less than or equal to five. We improve this by proving that ke(G) for such a graph G is never more than four. G. A. Dirac [5], who has written numerous papers on map coloring, the four color conjecture, and the vertex chromatic number of a graph, first introduced the idea of "critical graphs." In 1957, R. C. Read [16] stated: There is a certain ambiguity in the literature con— cerning the use of the term 'critical.‘ The original definition, as given by Dirac, was that a graph was critical if the removal of any node, together with the incident edges, decreases the chromatic number. We may call such graphs 'node critical.‘ In later papers Dirac used a different definition, viz. that a graph is critical if no prOper subgraph has the same chromatic number. We may call such graphs 'edge critica1.' In this thesis, node critical graphs are called vertex critical graphs relative to the vertex chromatic number. Edge critical graphs relative to the vertex chromatic number are those graphs having the pr0perty that the removal of each edge reduces the vertex chromatic number. In a later section, we prove a theorem concerning total graphs analogous to the following theorem due to G. Chartrand [A]. Theorem of Chartrand.--If G is a connected graph of order n which is not an arc, then the repeated linevgraph Lp(G) is Hamiltonian for every p i n — 3. F. Harary, R. M. Karp, and w. T. Tutte [9] prove the following theorem which we use to characterize graphs whose total graphs are planar. Theorem of Harary,rKarp, and Tutte.«eA graph G has a planar square if and only if (a) every vertex of G has degree less than or equal to three, (b) every block of G with more than four vertices is a circuit of even length, and (c) G does not have three mutually adjacent cut vertices. In 1956, E. A. Nordhaus and J. w. Gaddum [13] proved the following theorem which was generalized by G. A. Dirac [6] in 196A. Theorem of Nordhaus and Gaddum.--For the vertex chro- matic number of a graph G of order n and its complementary graph G, one has the following inequalities: kV (G) + kv (a) 2n% n + l “A llA (E) _<_.((I1 + 1) / m2. n [I A kv (c) - kv We conclude this section by stating two classical theorems from graph theory which will be of value to us later. Theorem of Eule:.--A non-trivial graph G is Eulerian if and only if G is connected and all vertices of G are of even degree. Theorem of Kunatgwski.--A graph G is planar* if and only if it contains no subgraph homeomorphic to KS or K3 3. ’ (See [12].) *For definitions of terms not defined in the thesis see [A]. CHAPTER II THE EDGE CHROMATIC NUMBER Section 3 Basic Results We begin this section with a number of elementary remarks concerning the edge chromatic number of a graph. (1) ke (G) = 0 if and only if G is an empty graph. (ii) Let G be a connected graph. Then ke (G) - 1 if and only if G = K2. (iii) Let G be a connected graph. Then ke (G) = 2 if and only ’ifG is a circuit of even length or an arc of length n, n g 2. (iv) Let p be the maximum degree ofGn Then ke(G) ; p. (v) Let G be a complete bipartite graph, i.e., G = Km,n- Then ke (Km,n) = max (m,n). (See [2].) (vi) If G and G' are graphs on the same vertex set V, then ke (G + G') ; ke (G) + ke (G'), where V (G + G') = V, and X (G + G') = X (G) U X (G'). This follows from the fact that the edges of G + G' can be expressed as the union of ke (G) + ke (G') independent sets. 10 ll (vii) In this chapter a "proper coloring" of a graph G will refer to a coloring of the edges of G in such a way that no two adjacent edges haVe the same color. (viii) By "color n" in the sequel we mean color number n, n = 1, 2, 3,’ (ix)‘ Let G be a tree with maximum degree p. Then ke (G) = p. This can be shown by a simple induction on the number of vertices of G. We shall obtain this result as a corollary to a theorem in Section 4. Theorem 3.l.---ke (Kn) = 2 {g} - 1 for n g 2. Proof.--Let n be odd, n = 2 k + 1. Any independent set of edges contains less than or equal [g] = k edges. Since there are n (n — l) /2 k (2 k + 1) edges; we 2 k + l = n colors. But need at least k (2 k + 1) /k this number is also sufficient. Indeed, label the vertices of G as l, 2, 3, . . ., n, and let Sp = {(p - q, p + q) | q = l, 2, . . . ., (n - 1) /2} for p = 1, 2, . . ., n, where for the edge (p - q, p + q) each of the numbers p - q and p + q are expressed as one of the numbers 1, 2, . u n modulo n. It is seen that each Sp is independent and that «1313: X, so that ke (Kn) = n for n odd. If n is even (so that 2<§ - l = n - 1), clearly ke(Kn) ; ke(Kn-l) = n-i.‘ We label the vertices 1, 2,. . ., n as before. and delete the vertex n (and all incident edges). The resulting subgraph Knel has edge chromatic number 12 n — 1 since n - 1 is odd. Define Sp, p = 1, 2,° ° ', n v 1 as before. Letting Tp = Sp U {(p, n)} for p = 1, 2, . . ., n - 1, we then see that the edges of Kn can be partitioned into the n - 1 independent sets Tp. (We note that this result also follows since Kn has a 1 — factorization for n even. See Konig [11], page 157.) Cgrollagy 1.--Let G be a graph of order n. Then n Proof.--G is a subgraph of Kn, n ;2. Corollary 2.--Let G be a regular graph of order n and degree n - 2. Then ke (G) = n — 2. Ergg£.--n must be even. Thus ke (Kn) = n - 1. G can be obtained from Kn by the removal of a suitable l e factor. Since any two regular graphs of order n and degree n - 2 are isomorphic, without loss of generality, we may assume that G is obtained from Kr1 by removing a 1 — factor all of whose edges have the same color. Therefore ke (G) = n - 2. Theorem 3.2.—-For any connected graph G, ke (G) ; kV(G)—1, and equality holds if and only if G = Kn’ n even. figgg£.—-The result is obvious if G is the trivial graph or if G consists of a single edge. Two cases remain: (i) G is a graph with maximum degree two; and (ii) G is a graph with maximum degree p, p > 2. In case (1), either G is an arc of length greater than one, or is a circuit. In the first possibility we have ke(G) = kv(G) = 2, so that ke(G) > kV(G) - 1. In the second possibility, kV(G) = ke(G) = 3, or kV(G) = ke(G) = 2. 13 In case (ii) we use a theorem of Brooks [3]. If a graph G with maximum degree p is p - chromatic, then ke (G) ; p ; kV (G) > kV (G) - 1. If G is not p—chromatic, then G = Kp + 1, and kV (G) = p + 1. By Theorem 3.1, . + ke (G) = 2 — l g p. Thus ke (G) ; p = kV (G) - 1. Now if G = Kn’ n even, then kV (G) = n, and ke (G) = n - 1. Thus ke (G) = kV (G) — 1. Suppose G is a connected graph with ke (G) = kV (G) - 1. Let the maximum degree of G be p. ke (G) ; p implies kV(G) ; p+l. But by the theorem of Brooks kv 2. Suppose Vk and v are two terminal cut vertices of G, and ke (Gk) 1 p ke(Gp), where Gi denotes the subgraph consisting of all blocks of G having vi as a common vertex, i = l, 2, . . ., n. Delete from G all terminal blocks attached to Vk and call the resulting graph G'. Then G' has n - 1 cut vertices. By the induction hypothesis G' contains a section graph H', which has at most one cut vertex of itself and such that ke(G') = ke(H'). Since Gp is a subgraph of G', ke(Gp) ; ke(H'). Thus ke(Gk) ; ke(H'). Now color the edges of G' properly with ke(H') colors, and consider the subgraph G" of G consisting of the blocks of G which are not in G' and all edges x1, x2, . . ., xr in G' which are incident to Vk‘ G" c; Gk (G" g Gk means G" is a subgraph of Gk) implies ke(G") 3 ke(Gk). Thus ke(G") ; ke(H'), and we can color the edges of G" with ke(H') colors properly such that the colors of the edges x1, x2, . . ., Xr are pre-assigned colors. Thus ke(G) "A ke(H‘). Since H' is also a section graph of G, ke(H') IA ke(G). Therefore ke(G) = ke(H'). Corollary l.--A graph with more than one cut vertex is neither edge nor vertex critical. In order to solve the problem of finding edge \ chromatic numbers, by Theorem A.A we must concentrate on graphs having at most one cut vertex. 2A Theorem A.S.--Let G be a connected graph with exactly one cut vertex v, and h = max (ke (B)) taken over all blocks B of G. Then Ke(G) is the maximum of h and deg(v). £399£.--Assume ke (Bi) ;_s, for each i = l, 2, . . ., r, where Bl’ B2, . . ., Br’ r ; 2 are all blocks of G and s = deg (v). Color the edge xi with color 1 ; i = l, 2, . . ., s, where x x ., xS are all edges of G incident to v. 1’ 2’ Since ke (Bi) ; s, Bi’ 1 = l, 2, . . ., r, can be colored prOperly with colors I, 2, . . ., s such that all edges to which v is incident and are in B have pre-assigned colors. 1 Thus ke(G) ; s, so ke(G) = s.- Now suppose h > s and h = ke(Bj) for some je {1, 2, . . ., r}. Clearly ke(G) ; h. Select h colors I, 2, . . ., s, .‘. ., h. Color the edge xi with color 1 ; i = l, 2, . . ., 3. Now each Bi , i = l, 2, . . r can be colored with colors 1, 2, . . . h properly such that all edges to which v is incident and are in Bi have pre— assigned colors. Thus ke(G) ; h. Therefore ke(G) = h. Corollary.--The edge chromatic number of a tree is equal to its maximum degree. Theorems A.A and A.5 reduce the problem of finding edge chromatic number of graphs to those graphs which have no out vertex. Continuing the program begun in Corollary 1 of Theorem A.A, we prove the following theorem: 25 Theorem A.6.--Let G be a connected graph with one cut vertex v.1then: (l) G is edge critical if and only if G is a star graph; (2) G is vertex critical if and only if deg(v) ; ke(B) for each block B of G, and all vertices of G are adjacent to v. Ergg§.--(l) A star graph is obviously edge critical. Conversely, suppose G is a connected edge critical graph with one cut vertex v. By Theorem A.5. There are two cases to be considered: (1) kem) (11) ke des W). h, where h = maximum ke(B) taken over all blocks B of G. In case (ii), G cannot be edge critical, thus (1) must hold. But in this case G is not edge critical unless G is a star graph. (2) Assume deg(v) ; ke(B) for each block B of G. Then by Theorem A.5 we have ke(G) = deg(v). This and the fact that all verticesof G are adjacent to v imply that G is Vertex critical. Conversely, suppose G is vertex critical. We claim that deg(v) ; ke(B) for each block B of G. If not, then deg(v) < ke(B) for some block B of G. Thus by Theorem A.S ke(G) = h, where h is defined as before. But this contradicts the fact that G is vertex critical. Therefore <398(V) ; ke(B) for each block B of G. 26 From this we conclude that ke(G) = deg(v). Now if G has a vertex which is not adjacent to v, then G is not vertex critical, a contradiction. Thus every vertex of G is adjacent Corollary l.——A connected edge critical graph G which is not a star graph has no separating edge. Egggf.-—Suppcse G has a separating edge x = (vl , v2). Then both vertices can not have degree greater than one, because otherwise both v1 and v2 are cut vertices of G, a contradiction to Corollary 1 of Theorem A.A. Thus, I assume deg (v = l and deg (v2) ; 1. If deg (v2) 1) = I, then G = Kl’l and if deg (v2) > 1, then G is a connected edge critical graph with a cut vertex v2. By Corollary 1 of Theorem A.A, this is the only one. Then by Theorem A.6, G is a star graph, a contradiction. Corollary 2.—-Let G be a connected edge critical graph of order n, n ;:3, which is not a star graph or K3. Then the graph G', obtained by the removal of any edge of G, is not edge critical. firgg£.-—By assumption, l V l.> 3. Let Ke(G) = q. Remove an edge x = (v1, v2) from G, and denote the resulting graph by G'. Then Ke(G') = q - I. By Corollary 1 above x is not a separating edge. Thus G' contains two adjacent vertices v 3 a proper coloring of G' we must be able to color only the and VA' Suppose G' is edge critical, then in 27 edge (v3, v”) with one of the q - 1 colors. But this implies ke(G) = q - 1, since (v1, v2) and(v3, VA) are not adjacent, a contradiction. CHAPTER III THE TOTAL CHROMATIC NUMBER sectionl: Basic Results We begin this section with the following definition: Definition 5.l.--An independent set of elements (vertices and edges) of G is a subset, S, of VUX having the properties: (i) no two vertices in S are adjacent, (ii) no two edges in S are adjacent, and (iii) no vertex in S is incident with an edge in S. The minimum number of-such independent sets into which VUX can be partitioned is called the total chromatic number of G and is denoted by kt (G). This number is the minimum number of colors required to color both the vertices and edges of G so that neither two adjacent vertices, nor two adjacent edges are COlOTed the same and so that a vertex and an incident edge are colored differently. We present without proof a number of elementary results concerning the total chromatic number of a graph. (1) kt (G) ; kV (G), and R10 (G) ; ke (G). (11) kt (G) ; xv (G) + ke (G). 1 if and only if G is an empty graph. 28 (111) kt (G) 29 (iv) There is no graph having total chromatic number two. (v) If G is a nonempty graph, then kt (G) ; 3. (vi) If G is an arc of length n, n ; 1, then kt (G) = 3. (vii) If G is a graph with maximum degree p, then kt(G) (viii) In this chapter by a "proper" coloring of a graph G we mean 33 coloring of the elements of G according to the Definition 5.1. Also in the sequel by "color n" we mean color number n. (ix) Let G be a tree with maximum degree p, p > 2. Then kt (G) = p + 1. Proof is by induction on the order of the graph, and use of the fact that every non—trivial tree has a vertex of degree one. (x) The total chromatic number of a circuit whose length is a multiple of three is three. (xi) The total chromatic number of a circuit whose length is not a multiple of three is four. Theorem 5.l.—-kt (Kn) = 2 E%] + l, where Kn denotes a complete graph of order n. Egggf.--We employ the notation used in the proof of Theorem 3.1. Clearly kt (Kn) ; n. If n is odd, we define S'p = Sp U{p} , p = l, 2, . . ., n, where Sp is defined as before. S'p is an independent set of elements of Kn and every element of Knlies in one and only one S'p ; _ _ R1 hence kt (Kn) — n - 2 L2] + l for n odd. 3O ConSider the case where n is even so that 2[g}+ l = n + 1. Note that I VUX I = n(n + l) / 2 and that no independent set of vertices and edges can contain more than n/2 elements, since such a set contains at most one vertex. This implies that for n even, Kt (Kn) ;:n + 1. To Kn we add a vertex labelled n + l and all the edges (j, n + l), J = 1, 2, , , ., n, producing the graph K Since n + l n + l' is odd, kt (K = n + l and because Kn is a subgraph n + 1) of Kn + l’ we clearly have kt (Kn) ; kt (Kn+l). Therefore ’K = kt \ n) n + l. Corollagy l.--Let G be a graph of order n, then kt(G) - n — g Corollary 2.—— k (Kn) = k (Kn) = kt (Kn) = n if n V e k (Kn) + 2 = kt (Kn) = is odd, n > 1, and RV (Kn) + l e n + I if n is even. lheorem 5o2o-—kt (Km, n) = max (m, n) + l + 6m, n where Km n is a complete bipartite graph of order m + n. 5 2329: —-V = Vlu v2 , where I v1 1 = m . o, l V2,, 3 n w O as described in the definition of Km n' Assume 3 m ; n. If V = {u l i = l, 2, . . ., m} and V = 2 I j = 1, 2, . . ., n}, then let Ap = { (ui, v3) | J 5 p + l - 1 mod n, i = l, 2, . . ., n{>, p = l, . . ., n. Each Ap is independent and every edge of Km n appears in one 3 and only one Ap. This proves that ke (Km ) n = max(m,n)o ,n Now there are two cases: 31 (K ) (i) m < n. Clearly kt m,,n i n + 1. For p = and B V . The sets Bp , p = 1, 2. . ., n + l,are n + l 1 independent sets of element of G which partition VUX. Therefore kt (Km, n) g n + 1 so that kt (Km n) a n + l. I (ii) m = n. ,We note that no independent set of vertices and edges in Kh n can contain more than n elements ! and since I VUX l=h2 +_2n, this implies that,kt (Kn. n),; n + 2. However, if we define Ap as before for p = . l, 2, . . ., n, An + l = V1 , and An + 2 a V2 , we then -have a partitioning of'VUX_into n + 2 independent sets, an + 2. and so kt (Kn, n) As was remarked earlier, kv (G) + k8 (G) L'kt (G). For the graph Km, n , we found that kv'(Kn, n) + ker(Kn, n) a ' kt (Kn, n). We shall show that equality holds onlyjif the graph G is bipartite. Theorem 5.3.--If G is a non-trivial graph and kv (G) + ke (G) = kt (G), then G is bipartite. Eggg§,—-Assume G is not bipartite. Then kv (G) g 3. Let UVr bela minimal partition of V into (3 or more) independent sets, and let UXS be a minimal partition of X into independent sets. (UVr) U (UXS) is a partition of VUX into independent sets, but we shall show that this is not a minimal partition., Since kv (G) Lw3: for each edge in X1, say, there exists some Vr whichrhas none of 32 its elements incident with the given edge. If each edge of X1 is added to such a Vr , then the resulting sets are independent sets of vertices and edges. This then implies that the set Xl may be deleted and a smaller partition of VUX into independent sets can be found. Therefore, kv (G) + k e (G) > kt (G), but this is a contradiction. The converse of Theorem 5.3 is not true as can be seen by considering Km,ri’ m # n, for example. Theorem 5;A.--Let G be a connected graph.. Then kV (G) = kt (G) if and only if G is a complete graph of order n,n odd, or a circuit of length 6k + 3, where k is a non-negative integer. Eggg§.--If G is a complete graph of order n, n odd, then by Theorem 5.1, k (G) = n. Also kV (G) = n, and t if G is a circuit of length 6k + 3, then by a previous remark, k (G) = 3. Since G is a circuit of odd length, t kv (G) = 3. Thus, again kV (G) = kt (G). Suppose G is a connected graph with kv (G) = kt (G). Let p be the maximum degree of G. kt (G) ; p + 1 implies kV (G) ; p + 1. By a theorem of Brooks [3] there are two posSibilities. 2 and G is a circuit of odd length. (i) p (11) G = Kp + 1. If G is not a circuit of length 6k + 3 or a complete graph of odd order, then kV (G) < kt (G), a contradiction to the hypothesis. 33 Corollary_l.-—Let G be a connected graph. Then kv (G) = ke (G) = k (G) if and only if G is a complete t graph of order n, n odd, or a circuit of length 6k + 3, where k is a non—negative integer. The following problems remain to be investigated: Problem 5.l.——Characterize graphs G such that kv (G) = ke (G). Problem 5.2.--Characterize graphs G such that ke (G) = ktl(G). Although the removal of an edge from K2 decreases the total chromatic number by two, we have the following general theorem. Theorem 5.5.--The removal of an edge from a graph having more than one edge decreases the total chromatic number by at most one. 3392:.e-Without 103s of generality, we may assume the graph G to be connected. If x = (v1, v2) is a separating edge of G, then let the components of G' = G — X be denoted by G1 and G . Clearly k (G') = maximum 2 t {kt (G1), kt (G2)}. Suppose that kt (G') = kt (G1). If kt (G1) < q - l, where q = kt (G), then G' can be colored with kt (G1) colors in such a way that v1 and v2 are Colored differently. G is then prOperly colored if x is colored with a new color. This, however, implies that kt (G) < q, which is a contradiction. Henceforth we assume that the edge x = (Vl,\f2) to be removed is not a separating edge. 3A Let us assume that kt (G') ; q - r, where r ; 2. We shall show that this assumption leads to a contradiction. Let U and W be those sets of vertices in G' adjacent to v1 and v2, respectively. Any proper coloring of G' which uses q — r colors will necessarily have v1 and v2 colored the same, for otherwise on replacing x and coloring it with any heretofore unused color, we obtain kt (G) 3 q - r + l < q, a contradiction. Let v1 and v2 have color a, where a e {1, 2, . . ., q - r}. There are- two cases to consider: (1) Unws¢s (11) unw=¢ Case (1) : Let V3 6 U n W, and designate the color of the edge (v1, v3) by s, the color of the edge (v2, v3) by 6 , and the color of v3 by y , where a , B, y., and 6 are pairwise distinct elements of {1, 2, . . ., q - r}. Replace the edge x, and introduce the new color q - r + l for this edge. We now give a coloring of G determined by the coloring of G' as follows. Color x with color 6, and replace 6, the color of the edge (v2, v3) by color q - r + 1. Replace a, the color of the vertex v1, by q - r + 1. Now there is a possibility that one edge , say (v1, v*), v* e U has color 6. If so, change the color of such an edge to G. Then it is also possible that there exists an edge incident to v*, say (v*,'v**), with color a. If 80, there are two cases to be considered: 35 (l) v** = v3. In this case we change the color a of the edge (v*, v3) to 6. (2) v** # v3. Then let the edge (v*, v**) have color q — r + 1. In any case we obtain a proper coloring of G with q - r + 1 colors so that kt(G) ; q — r + l < q, a contra— diction. Case (ii): Consider any edge incident with v2, say (v v), and suppose this edge is colored B in G'. Replace 2, x, and color (v2, v) along with any vertices adjacent to v2 and colored 8 in G' with q - r + 1. In addition, color V1 with q - r + l. Coloring x with G and v2 with 8 now produces a proper coloring of G with q - r + 1 colors, so kt(G) ; q - r + l < q ; a contradiction. 36 Section 6 Critical Graphs Relative to the Total Chromatic Number Definition 6.l.--A graph G is called edge critical relative to the total chromatic number if the removal of ‘each edge decreases the total chromatic number. Definition 6.2.--A graph G is called vertex critical. relative to the total chromatic number if the removal-of each vertex(and all edges incident with it) decreases the total chromatic number. Remarks.--(i) In this section by an edge (vertex) critical graph we mean an edge (vertex) critical graph relative to the total chromatic number. 3 (ii) A connected edge critical graph is also-vertex critical, but the converse in general is not true.= For example,,K5 is vertex critical but not edge critical. E, #.2, and circuits ,(iii) Star graphs with n edges, n of length n, where n is not a multiple of three, are edge (thus vertex) critical. Theorem 6.l.--Every graph G contains a section graph H such that H has at most one cut vertex of itself and ktm) = ktm). Proof.--We can prove this theorem exactly by the same method as the proof of Theorem A.A, with appropriate care taken for the coloring of the vertices of G. 37 The number of blocks to which a vertex v belongs is called the connective index of v and is denoted by i(v). Corollary l.--Let G be a graph, r = max (kt(B)) over all blocks B of G, and s = max(i(v))taken over all vertices v of G. Then kt(G) ; r . s. Corollagy 2.--If G is a line-graph and r = max (kt(B)) taken over all blocks B of G, then kt(G) ; 2 r. Pagg§.--Let v be a vertex of G. By a theorem due to G. Chartrand [A], i(v) is either one or two. Thus by Corollary 1, we have kt(G) é 2 r. Corollaryg3.--A graph with more than one cut vertex is neither edge nor vertex critical. Due to Theorem 6.1, we may concentrate on graphs having at most one cut vertex. Theorem 6.2.--Let G be a connected graph with one cut vertex v, and h = maximum kt(B)’ taken over all blocks B of G. Then kt(G) = maximum {h, deg(v) + l}. ngg£.——The method of the proof of this theorem is the same as that of Theorem A.5. Corollary l.--The total chromatic number of a tree G, G ¢ K2, is equal to its maximum degree plus one. Proof.——First apply Theorem 6.1, and then Theorem 6.2. Theorems 6.1 and 6.2 reduce the problem of finding total chromatic numbers of graphs to the study of those graphs which have no out vertex. 38 Continuing the investigation begun in Corollary 3 of Theorem 6.1, we prove the following theorem. Theorem 6.3.--Let G be a connected graph with one cut vertex v. Then: (1) G is edge critical if and only if G is a star -graph with deg(v) # 2 ; ‘ (2) G is vertex critical if and only if deg(v) ; kt(B) for each block B of G, and all vertices of G are adjacent to v. nggf.-—The proof is exactly the same as that of Theorem A.6. Corollagy l.--A connected edge critical graph G does not have a separating edge, unless G is a star graph. Theorem 6.A.--No complete graph other than K2 and K“ is edge critical. gggq£.—-c1ear1y K2 a complete graph Kn“ There are the following cases to be and KA are edge critical. Consider considered, (i) n odd and n > 3 3 (ii) n even and n g 6. In case (i), Kn is not even vertex critical because kt(Kn) = kt(Kn_l) e n. In case (ii) consider Kn, remove an arbitrary edge from Kn and denote the resulting graph by G. Nowkt(Kn) n + I. We shall show kt(G) > n. I G has n (n 4 l) /2 — l + n elements. With one color we can color properly at most n/2 + 1 elements of G. If with the first color we color n/2 + 1 elements of G, then 39 with each of the other colors we can color prOperly at most n/2 elements of G. Thus with n colors we are able to color at most (n - l) n/2 + (n/2 + 1) a n — n/2 + 1 elements of G. But n (n - l) /2 - l + n — (n - n/2 + l) a n/2 - 2 > 0, because n g 6. Thus kt(G) = n + 1. It is easy to see that Kn is vertex critical when n is even and is not vertex critical when n is odd. A connected graph in which every block is a complete graph is called a completed Husimi tree. The following theorem determines the total chromatic number of a completed Husimi tree. Theorem 6.5.--Let G be a completed Husimi tree, with maximum degree p. Then kt(G) = p + 2 if G is a complete graph of even order, and kt(G) = p + 1 otherwise. nggf.—-If G is a complete graph of even order, then the theorem follows from Theorem 5.1. Otherwise G is a complete graph of odd order in which the theorem is trivially true, or G has at least one cut vertex. By Theorem 6.1, G contains a section graph H which has at most one cut vertex of itself and kt(G) = kt(H). Now there are the following cases to be considered: (1) H has exactly one cut vertex V of itself; (ii) H has no cut vertex of itself. In case (i) it is easy to see that we can color H properly with deg(v) + 1 colors. Thus kt(G) = kt(H) = A0 deg(v) + l ; p + l, where p is the maximum degree of G. On the other hand, kt(G) ; p + 1. Thus kt(G) = p + 1. In case (ii), we can select a section graph H with exactly one cut vertex v of itself such that kt(G) = kt(H). Then following the argument given in case (i), we see that again kt(G) = p + l. CHAPTER IV TOTAL GRAPHS Section 7 Fundamental Properties and Preliminary Results Definition 7.1.--Let G (V ,X)be a graph. We define a graph T (G) associated with G in the following manner: (1) Each vertex of T (G) is associated with a unique vertex or edge of G; (2) Two vertices v1 and v2 of T (G) are adjacent in T (G) if and only if,(i) v1 and v2 are associated with 2 are associated 1 and v2 is two adjacent vertices of G,(ii) v1 and v with two adjacent edges of G, or (iii) one of v associated with an edge of G and the other one with a vertex of G which are incident in G. The graph T (G) is called the total graph of the graph G. Now consider a graph G, and on each edge of G insert a vertex (of degree 2), and denote the resulting bipartite graph by B (G). B (G) is homeomorphic to G, has IV(G) I + I X (G) | vertices, and 2 I X (G) I edges. 2 (G), where B2 (G) It is interesting to note that T (G) = B is the square of the bipartite graph B (G). Al A2 Remarks.--(i) The number of components of T(G) is equal to the number of components of G. (ii) G and T(G) are isomorphic if and only if G is an empty graph. (iii) If v1 is a vertex of T(G) which is associated with a vertex Vl of G, then deg(vl) = 2 (deg(vl)), and if it is associated with an edge x = (v1, v2) of G, then deg(vl) = deg(vl) + deg(vz). Thus if G is a regular graph of degree r than T(G) is regular of degree 2 r. (iv) There does not exist a graph G such that the degree of a vertex of T(G) is one. Thus no graph has for its total graph an arc of length n, n g l. (v) There does not exist a graph G whose total graph is a circuit of order n, n g A. If such a graph existed, it would have a vertex of degree at least two. However, such a vertex produces a vertex of degree at least four in T(G). (vi) There does not exist a graph whose total graph has a cut vertex. Thus there does not exist a graph whose total graph has a separating edge, because the only graph which has a separating edge and no out vertex is K2. But by Remark (iv) the total graph of no graph is K2. Theorem 7.l.—-kt(G) = kV(T(G)). Proof.——To find kt(G), there are I V (G) |-+| X (G) I elements to be colored. Let V1 and v2 be two vertices of A3 T(G) which correspond to the elements al and a2 of G, respectively. The elements al and a2 may have the same color in a proper coloring of the vertices and edges of G if and only if v1 and v2 are not adjacent in T(G). Thus kt(G) = kv(T(G)). Theorem 7.2.——The total graph of no graph except the trivial graph and K is a complete graph. 1,1 nggf.--Clearly the total graph of the trivial graph and K1,l are complete. Let G be a graph different from the above and assume T(G) is complete. Then G must be connected and have at least three vertices, v1, v2, v3 and two edges, say, x1 = (v1, v2), x2 = (v2, v3). Let v1 and v2 be the vertices of T(G) which are associated with the vertex v1 and the edge x2 respectively. Then in T(G) the vertices v1 and 2 v are not connected, a contradiction. Corollary l.--Let G be a graph of maximum degree p, 'U = 2. Then kt(G) ; 2 p. ngg£.--By remark (iii) the maximum degree of T(G) is 2p. By Theorem 7.2, T(G) is not a complete graph. By remark (v), T(G) is not a circuit. Thus by a theorem of Brooks [3], T(G) is 2 p—chromatic. Therefore by Theorem 7.1, we have kt(G) ; 2 p. Corollary 2.--Let G be a graph of order n, and maXimum degree p, p ; 2. Then kt(G) ; min <2[g] + l, 2 n). AA Proof.--This follows from Corollary 1 of Theorem 5.1 and Corollary 1 of Theorem 7.2. Now we state the following two conjectures: Conjecture l.--Let G be a graph with maximum degree p. Then p + 1 ; k (G) ; p + 2. t This conjecture and Conjecture 1 of Section 3, if true, imply that for any graph G, k (G) — ke (G) ; 2. t Conjecture 2.--Let G be a graph of order n, and G its complement. Then we have the inequalities: n + l ; k (G) + kt (G) ; 2 n 3 2 t n ; kt (G) - kt (G) ; n Again this conjecture can be proved provided Conjecture l is true. Theorem 7.3.--Let G be a graph with n vertices vl, v2, . . ., vn, and m edges. Then T (G) has n + m n 2 vertices and 2 m + k X (deg(vi)) edges. i=1 nggf.—-Clear1y the number of vertices of T (G) is n + m. The graph T (G) consists of the union of the graph G, the line—graph,L (G), of the graph G, and the edges joining each vertex v of G to vertices of L (G) associated with edges of G incident to v. But L (G) n contains .2 , (See [A]-) 1 (iii) The number of triangles two of whose vertices are "543 0 number is A .+ 3 i associated with vertices of G and the other one with an edge of G is equal to m, the number of edges of G. (iv) The number of triangles of T(G) two of whose vertices are associated with edges of G and the other one n with a vertex of G is Z (deg(viv . i=1 The sum gives the required result. A6 In any graph the section graph determined by three ver‘ tices may consist of three edges (thereby resulting in a tri— angle), two edges, one edge, or no edges at all. Using the terminology employed by Nordhaus and Stewart [1A], we say that a subgraph consisting of three vertices and the j edges, j = O, l, 2, 3, which they determine is a triangle of type A3. A triangle of type 63 is simply a triangle while a triangle of type A0 is a subgraph consisting of three isolated verti- ces, i.e., an "empty" triangle. Let G be a graph. Define Gk+1 = T(Gk) = Tk+l(GO) = O k 0 _ , T(T (GO)), where G0 = T (GO), for k = O, l, 2,. k Denote the number of triangles of type Aj in Gk by A3. Since any three vertices in Gk determine a triangle of type A05 A1, A2, or A3, it follows that: A? + A? + A? + Ag =(pg), where pk denotes the order of G Denote the number of edges k 3 of Gk by qk. We have the following theorem: , k+l k . Theorem 7.5.--Let GO be a graph. Then A 3 = A2 + p k "k deg(vi) 5 A3 + qk +0) 3 , where vi, i = l, 2, . . ., pk, l: is a Vertex of Gk” Proof.—-Let Gk+l = T(TK(GO)), k ; 0. Following the . l k proof of the Theorem 7.A. We conclude that AKIl = 2A3 + 13k 13k 9 k deg(v.) deg(v.) r de v qk +02: ( 2 1) +_E < 3 i o BUT: 2 §( 1) 5: i=1 i=1 i=1 k " ,, . . _ . . - A2 + 3 £3. (See [1Aj.) Thus a, e A? + 5A§ + qk + pk s was required to show. ii {\"J .J\J f4 1 Now we state some numerical relations holding for the repeated total graphs of a regular graph. Let GO be a regular graph of degree rO ; l, with pO 0 ~ . vertices, qO edges, and A, triangles. Let G1 + 1 T (G1) for each i = O, l, 2, . . . . Each G, is clearly regular. .L. In general, let G, be cf orde; pi and degree r,i with qi edges and A For the graph G, we have the relations: 1 l’ ,. _,. 9.. , Kl) pi+l '“’ 91 " “4;: I .. x 1. , . . .. ,. 3, . i + l (2) rinl e 2 ii, and by induction r1+1 - 2 r0. /' ) fl 37.3 M's. ,, all" . (raj ‘x . 1' \ ::-. - ‘c (4/ 2 ql+l pi + l r, +1 Using (A) and (l) we obtain: 1'41 1“ r.“ I \ (v . "“ f o o o > w (5) 2 Plr‘l. {.0 (10+ 2) (fl-I- 2) (r2 +2) (131+ 2)... pc 7‘"? f‘+.£ a J 31:", "'u u I A \ . ‘ ‘ 35 r. A u a ’. V+ . ‘14. \ .4. 7 f I .5. . .L - J. Plcm (6) we zin- (7) q1+l a 90 TI, (: +2), from which by (5) and (7): A8 (8) 21+1 p1+1 ; P qi+1 o By considering the square of the graph obtained from O Q Gi by inserting "midpoints" of all edges, we obtain: ‘ pi Pl <9> as“: 3+ [.g. z (a) +. (1:1)] .— i=1 3 1 i=1 5 PJ- l\) A: 2A: + q, r- “ 1 Relations (9} imply: + Z) /".3 . . .. o , s; .-_ ». (10) élj+l .1: 21+i A. + 1/3 2 21 J q (rd-2). " 3:0 J 3 Define integers Qi+1 by: x N a 2 l (11/ 2Qi+l "" Pl*’l I13": (1"0, 1, 2’ u o «)0 By (11) and (A): (12) Qd a r1 q,, and by (6) and (12) ; From a result given in [IA] we have: ’14) A. + 3A} - Q - q q (r -l) i i i i i (15) 3:. = Al * 2Q - p. q = A1 + q (2 - ) 1 l i 1 i. *1 pi ° “9 Section 8 The Planarity of Total Graphs We begin this section with the following theorem: Theorem 8.l.-—If G is a graph such that L(G) is planar, then T(G) has thickness less than or equal to two. Ergg£.--Since L(G) is planar, G is planar also. (See [4].) Thus consider the planar graph G. Associate with each edge (v1, v2) of G a new vertex v, connect this vertex v to both v1 and v and denote the resulting graph by.G'. 23 Since G is planar, G' is also planar. But T(G) is the sum of pairwise edge..disjoint planar subgraphs G' and L(G). Thus tiliGLE % 2, where tinGl) denotes the thickness of T(G). =1- Kl,# is an example which shows that the upper bound (two) A I f ’5, "f‘. v: fr. \ ‘n -1’ _ 1" g- fl. \: y i taantt be improaev. Theorem 8.2.--Given a graph G, there exists a graph H such that G = B(H), where B(H) is obtained from H by inserting exactly one vertex (of degree 2) on each edge of H, if and only if each circuit of G has even length and each arc which connects two vertices of degrees different from two is also of even length. Ergg£.--(l) Assume there exists a graph H such that G = B(H). Let a and b be two vertices of G which have degrees different from two. If a and b are not connected there is nothing to be proved. Suppose a and b are jOined by an arc A = (a, v1, v2, . . ., Vn—l’ vn = b). deg(a) # 50 2, deg(b) # 2, imply a and b are vertices of H. Also v2, VA’ v6, . . . are all vertices of H, and v1, v3, . . . are not vertices of H. Since b is a vertex of H, and b = v n n’ must be even. Now let C = (v1, v2, . . ., Vr = vi) be a cycle of G. This cycle is obtained from a cycle of H by inserting a vertex of degree two on each edge of it. Thus the length of C is twice the length of the corresponding cycle of H. (2) Let G be a graph with the properties stated in the theorem. If G is an empty graph, let H = G, and if the degree of each vertex of G’is two, then G consists of k cycles of even length. Let H be a graph consisting of k cycles each with length half of the length of the components of G. Thus assume G has a vertex v1 of degree different from two. We construct H in the following manner: Start with v1 and go along each edge incident to vlto the first vertex of degree different from two. On each of these arcs or circuits, remove the first vertex (of degree two) which is adjacent to v1, and the two edges incident with it and replace them by a single edge; leave the' second vertex, remove the third one (which is of degree two) and the two edges incident with it and replace them by a single edge; leave the next vertex, . . . and so on. In this manner, on each such arc or circuit we shall reach a vertex of degree not equal to two whose previous vertex has 51 been removed, since the distance between this vertex and v1 was even by hypothesis. Now start with another vertex v2 of degree different from two of the resulting graph and go along all edges incident to v2 on which a vertex of degree two has not been removed. On each of these arcs or circuits repeat the same thing that was done for the vertex v1. Since G has a finite number of vertices, after a finite number of times we obtain a graph H such that B(H) = G. This completes the sufficiency proof. Harary, Karp and Tutte [9] have characterized graphs which have planar square graphs. The following remark is based on their theorem. Remark (1) T(G) = 82(G) is planar if and only if B(G) satisfies the following conditions: (1) Every vertex of B(G) has degree at most three; (2) Every block containing more than four points is a cycle of even length. Since B(G) is bipartite and does not contain any triangle, the third condition of the theorem of Harary, Karp and Tutte is automatically satisfied. Now using this result and Theorem 8.2 we prove the following theorem: Theorem 8.3.--T(G) is planar if and only if: (1) every vertex of G has degree at most three; (ii) if v is a vertex of degree three, then it is a cut vertex. 52 Proof.--(Necessity.) By remark (i), we must have deg(v) ; 3 for each vertex of B(G) which implies (i) is a necessary condition. Let v be a vertex of degree three of G. Assume v is not a cut vertex. Thus v and the three vertices adjacent to it belong to one block of G. These vertices also belong to one block of B(G). Thus by (2) of remark (i) such a block must be a cycle of even length because this block in B(G) contains more than four points. But such a block cannot contain a vertex of degree three, a contradiction. Thus (ii) is also necessary. (Sufficiency.) Consider a block B of G. B cannot. contain a vertex of degree three. Thus B is a single edge or it is a cycle. If it is Kl,l’ this block does not produce a block with more than four vertices in B(G), and if it is a cycle, it produces a block in B(G) with at least six vertices which is still a cycle in B(G). By Theorem 8.2 this has even length in B(G)» Therefore (1) and (2) of the remark (i) holds. Thus T(G) is planar. This theorem can also be proved directly by using the fundamental theorem of graph theory due to Kuratowski [12]. We give an outline of the proof as follows: (Necessity.) (1) Assume T(G) is planar and G has a vertex of degree four or more. Then it is easy to see that T(G) contains K5 as a subgraph. 53 (ii) Assume v is a vertex of G of degree three which is not a cut vertex. Then it can be shown that T(G) con— tains a subgraph which is homeomorphic to K5, a contradiction to the planarity of T(G). (Sufficiency-) Proof is by induction on the number of vertices of degree three of G. 5A Section 9 Total Graphs and Hamiltonian Circuits Before we consider total graphs and their related Hamiltonian circuits we characterize those total graphs which are Eulerian. Theorem 9.l.--Let G be a nonvtrivial connected graph. Then T(G) is Eulerian if and only if all vertices of G are of the same parity. Eggg£.--(Necessity.) Assume that T(G) is Eulerian and that G has a vertex v1 with odd degree and a vertex v2 with even degree. Then in G,vl and v2 are joined by an arc on which there exist vertices v3 and VA which are adjacent and of opposite parity. Thus in T(G) the vertex which corre- sponds to the edge (v3, VA) of G has odd degree, a contra- diction. (Sufficiency.) Clearly the vertices of T(G) which correspond to the vertices of G have even degrees. But since the sum of two odd or even numbers is always even, then by Remark (iii) of Section 7, vertices of T(G) which correspond to the edgeswng have even degrees too. Thus T(G) is Eulerian. Corollary l.——If a graph G is Eulerian, so is T(G). (The converse is not necessarily true.) 55 Corollary 2.--Let G be a graph such that T(G) is not Eulerian. Then none of the iterated total graphs obtained from G is Eulerian. Corollary 3.-—The total graph of every non—trivial connected regular graph is Eulerian. Two elements a and b of G are said to be neighbors if one of the following cases holds: (1) a and b are two adjacent vertices of G, (ii) a and b are two adjacent edges of G ,(iii) a is a vertex incident to the edge b or b is a vertex incident to the edge a. Theorem 9.2.—-The total graph T(G) of a graph G is Hamiltonian if and only if the set of all elements of G can be ordered in such a way that consecutive elements are neighbors, and the last element is a neighbor of the first. £322£,--The sufficiency is obvious. Thus assume that T(G) contains a Hamiltonian circuit (v0, v1, v2, . . ., Vr—l, Vr - v0). Let a1 be the element of G which is associ- ated with the vertex v1 of T(G), i = O, l, 2, . . ., r. a = a is the required r-l’ r O ordering of the elements of G. Then a0, a1, a2, . . ., a Theorem 9.3.—-If G is Hamiltonian, then T(G) is also Hamiltonian. Ergg£.--Let G have p vertices and q edges, and let H = (v0, v1, . . ., vp = v0) be a Hamiltonian circuit of G. We construct an ordered sequence of p + q labelled elements of G such that consecutive elements are neighbors and the last element is a neighbor of the first, as follows: 56 Let vO be the first labelled element of the sequence, and then label in any order all edges of G incident to V0 (if any) which are not in H, followed by the edge (v0, V1) of H and the vertex v1. Then label those edges (if any) which are incident to v1 and not in H, followed by the edge (v1, v2) of H and the vertex v2. This process is repeated, except that edges not in H are omitted in the ordering if they have been previously labelled. Eventually the edge (Vp—l’ vp) of H is obtained as the final element of this sequence. Thus by Theorem 9.2, T(G) is Hamiltonian. Theorem 9.A.--If a graph G contains a spanning Euler subgraph, then T(G) is Hamiltonian. Proof.--Let H be a spanning Euler subgraph of G. The x I x ). . . ., Xr—l’ r O edges of H form acgwlic paLtiCfi:£1,Xl, Let Vi denote that vertex of G wnich is incident to the con— secutive edges x i = O, l, 2, . . ., r-l. It is i’ Xi+l ’ possible that some of these vertices are identical. We construct an ordered sequence of elements of G such that consecutive elements are neighbors and the last element is a neighbor of the first, as follows: Let x be the first labelled element of the sequence, 0 and then label vO followed by all edges of G incident to V0 (if any) which are not in G. Then label x1 and v1, respectively, followed by those edges (if any) of G which are incident to v1 and not in C. This process is repeated, except that edges and vertices are omitted in the ordering 57 if they have been previously labelled. Eventually the edge Xr-l of C will be obtained followed by the vertex Vrel if it has not been previously labelled. But in any case x0 is a neighbor of both Xr-l and v Then by Theorem 9.2, r—l' T(G) is Hamiltonian. Corollary l.--If G is Eulerian, then T(G) is Hamiltonian and Eulerian. Theorem 9.5.-—The total graph T(G) of every nonetrivial connected graph G contains a spanning Euler subgraph. grggf.-—With each edge x = (v1, v2) of G associate a new vertex and Join it to the vertices v1 and v2. Denote the resulting graph which contains G as a subgraph by H. Each vertex of H has even degree and H is a connected spanning subgraph of T(G). Thus T(G) contains a spanning Euler subgraph. By combining Theorems 9.A and 9.5 we obtain the following interesting result: Corollary l.--If G is a non—trivial connected graph, then T(T(G)) is Hamiltonian. It is not too difficult to see that T(Kl n), n ; 3 is 3 not Hamiltonian, but according to Corollary 1 above, T2 (Kl n) 9 is Hamiltonian. Thus Corollary 1 cannot be improved. INDEX OF DEFINITIONS Definition bipartite graphs . . . . . . . . . block. . . . . . . . . . . . . chromatic condensation graphs. . . . . circuit edge . . . . . . . . . . complete bigraphs. . . . complete graphs I completed Husimi trees . . . . . . . condensation graphs connective index cut edge. . . . . . . . . . . cut vertex degree of a vertex . . . . . . distance between two vertices. 6mm 0 0 a o O O H O O O O O 0 edge chromatic number . . edge critical graphs relative to the edge chromatic number . . . . . . . . edge critical graphs relative to the total chromatic number . . . . . . . . edge critical graphs relative to the vertex chromatic number . . . . . . . Eulerian graphs . . . . . . . . . graphs . . . . . . . . . . . . Hamiltonian graphs homeomorphic graphs - - - - - - - ~ 58 Page* 39 13 37 CD QWWU"! 59 Definition Page* isomorphic graphs . . . . . . . . . . . 5 line-graphs . . . . . . . . . . . . . 5 maximum degree . . . . . . . . . . . 5 neighbor elements . . . . . . . . . . . 55 order of a graph . . . . . . . . . . . 3 ordinary graphs. . . . . . . . . . . . 3 p—chromatic . . . . . . . . . . . . . 7 regular graphs . . . . . . . . . . . . 5 section graph . . . . . . . . . . . . u separating edge. . . . . . . . . . . . u separating vertex . . . . . . . . . . . A spanning subgraph . . . . . . . . . . . u square of a graph . . . . . . . . . . . 5 star graphs . . . . . . . . . . . . . u subgraph . . . . . . . . . . . . . . A terminal block . . . . . . . . . . . . u thickness of a graph . . . . . . . . . . u total chromatic number . . . . . . . . .28 total graph . . . . . . . . . . . . .ul trivial graph . . . . . . . . . . . . 3 vertex critical graphs relative to the edge chromatic number. . . . . . . . . . .19 vertex critical graphs relative to the total chromatic number. . . . . . . . . . .35 vertex critical graphs relative to the vertex chromatic number. . . . . . . . . . . 8 *The number Opposite the term refers to the page on which the term is first defined or explained. BIBLIOGRAPHY 6O l. 10. ll. BIBLIOGRAPHY C. Berge. The Theory of Graphs and its Applications. (London, 1962). C. Berge. Graph Theory. American Math. Monthly, 471—481 (1964). R. L. Brooks. On Colouring the Nodes of a Network. Proc. Cam. Phil. Soc., 194—197 (l9Al). G. Chartrand. Graphs and their Associated Line-Graphs. (Ph. D. Thesis, Michigan State University, 196A). G. A. Dirac. Theorems Related to the Four Colour Conjecture. J. London Math. Soc., lA3-1A9 (1954). G. A. Dirac. Graph Union and Chromatic Number. J. London Math. Soc. ASI—ASA (196A). E. B. Dynkin and V. A. Uspenskii. Multicolor Problems. (D. C. Heath and Company Boston, 1963). Editorial Committee. Theory of Graphs and its Applications. (Academic Press, 1963). F. Harary, R. M. Karp, and W. T. Tutte. A Criterion for Planarity of the Square of a Graph. (To appear.) J. B. Kelly and L. M. Kelly. Paths and Circuits in Critical Graphs. Amer. J. Math., 786-792 (195A). D. Konig. Theorie der endlichen und unendlichen Graphen. (Leipzig, 1936; reprinted New York 1950). 61 62 12. G. Kuratowski. Sur le probleme des courbes gauches en topologie. Fund. Math. 271—283 (1930). 13. E. A. Nordhaus and J. W. Gaddum. On Complementary Graphs. Amer. Math. Monthly, 175-177 (1956). 1A. E. A. Nordhaus and B. M. Stewart. Triangles in an Ordinary Graph. Can. J. Math., 33-41 (1963). 15. O. Ore. Theopy of Graphs. (Providence, 1962). 16. R. C. Read. Maximal Circuits in Critical Graphs. J. London Math. Soc., 456-A62 (1957). nIcwzan snare UNIV. LIBRARIES IIHINNIWIIUINIIIIIW[11111111WWI 31293107143335