THE UN I VE RS I TY OF MI CH I GAN COLLEGE OF LITERATURE, SCIENCE. AND THE ARTS Communication Sciences Department Technical Report SOME INTERPOLATION THEOREMS FOR PARTITIONS OF GRAPHS Stephen Hedetniemi ORA Projects 03105, 08226, and 08333 Supported by; DEPARTMENT OF THE NAVY OF F:CE O NAVAt RESEARCH CONTRACT NO. N nr4 1224(21) W'AStINGTON; D C. and U.S, ARMY RESEARCH OFFICE (DURHAM) CONTRACT NO, DA-31- 124 -ARO-D=483 DURHAM, NORTH CAROLINA and NATIONAL INSTITUTES OF HEALTH PUBLIC HEALTH SERVICE GRANT NO. GM-12236-03 BETHESDA, MARYLAND admi nlstr dIt th. roughi OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR March 1967 Distribution of this document is unlimited

RESEARCH PROGRESS REPORT Title: "Some Interpolation Theorems for Partitions of Graphs," S. Hedetniemi, The University of Michigan Technical Report 03105-47-T. Background: The Logic of Computers Group of the Communication Sciences Department of The University of Michigan is investigating the application of logic and mathematics to the theory of the design of computing automata. Condensed Report Contents: In this paper we consider certain partitions of the set of points and of the set of lines of a graph and we define for each such partition a corresponding factor graph, The concepts of a complete P-partition and a complete P-line partition of order m are then defined for an arbitrary property P of a graph G. Two results are then obtained which answer the following questions: for what properties P of a graph G does it follow that if G has complete P-partitions (P-line partitions) or orders m and n, then G has complete P-partitions (P-line partitions) of orders k for any k, m < k < n, For further information: The complete report is available in the major Navy technical libraries and can be obtained from the Defense Documentation Center, A few copies are available for distribution by the author,

SOME INTERPOLATION THEOREMS FOR PARTITIONS OF GRAPHS In this paper we consider certain partitions of the set of points and of the set of lines of a graph and we define for each such partition a corresponding factor graph. The concepts of a complete P-partition and a complete Paline partition of order m are then defined for an arbitrary property P of a graph G, Two results are then obtained which answer the following questions: for what properties P of a graph G does it follow that if G has complete P-partitions (Pline partitions) or orders m and n, then G has complete P-partitions (P-line partitions) of orders k for any k, m < k < n, The author wishes to acknowledge that the proof techniques used here were originally developed by Geert Prins in an unpublished manuscript in which an Interpolation Theorem was proved for the class of partitions which correspond to homomorphisms of graphso By a grph G we mean a set V = V(G) of points together with a set E = E(G) of unordered pairs (uv) of distinct elements of V(G). called lines of Ge A graph G' is a subgraph of G GG C G, if V' C V and E' C E; G' is an induced subgraph if for every pair of points u, v e V', (usv) e E implies (uvv) C El, The subgraph induced by a set of oints S <S> is the induced subgraph GI for which V(G") = S, The subgraph induced b a set of lines T, <T> D is the minimal subgraph of G containing all the lines of T. A graph G is called complete if for every pair of distinct points uv e V(G) (uv) e E(G). Given two subgraphs G1 and G2 of G, G1 U G2 is the subgraph of G for which V(G1UG2) = V(GI)UV(G2) and E(G1U G2) = E(G1)kE(G2). Two subgraphs C1 and G2 of G are said to be line adjacent if there exist points u c V(G1), v e V(G2) such that (u,v) E E(G), G and GC are oint adjacent

2 if there exist points uv,w such that (u,v) E (G1) and (utw) a ELG2). Any definitions not given here can be found in [2], Let =- {V1, V2..,, V } be a partition of the set of points of a graph G. By the factor grap.h G/T. we mean the graph for which "V(G/;i) = (~ v2,a.,,I V } and (' Vj C E(G/n) if and only if (<Vi and <Vj> are line adjacent, A partition it of G is complete if G/n is complete. Let P denote any property of a graph G. A subset S C V(G) is a P-sec if /S> has property P. A P-arttition of G of order m is a partition a = {Vl V2,,,, V } of V(G) such that for every i, 1 s i s m, V. is a P-set. The P-chromatic number of a graph G, Xv(G), is the minimum order of all complete P-partitions of G. Similarly, the P-achromatic number of G, Vp(G), is the maximum order of all complete P-partitions of G, We will be interested in pronerties )' oi a gP.raph (; which satisfy't.i following two conditions. For any graph G and any subsets Vi, Vj C V(G) (i) if V. is a P-set and V. C V.. then V. is a P-set. and (ii) if V. and J k. V.j are disjoitntPctan, V.:';Y **<V.W.::-c not iine adlacent, t'h'i V'.~'..5 al so:( a tP-Cc. he will say that any property P which satisfies these two conditions is homoeneous, Examples of homogeneous properties. e...... ~:........_...... are numerous. We will mention two exailples in particular because of their connections wi th:;the'r estab lished con: et'; n:raiph theorn. The property P. oaf being a pla::nr r:.; i.a can,. ee i..'..l-,':,':, The Pl chromatic number of a, graph G then is the minimum number oi Cplal ar, point disjoint, full subgraphs into which G can be decomposed. It would seem t that this parmer is closely related to the thickness of a graph 6(G),. ige.- the minimum number of planar subgraphs of G whose union equals G,

3 The property P2 that a graph can be totally disconnected, iee,, contain no lines, is also homogeneous, It can be shown without much difficulty that the P2-chromatic number is what is traditionally called the chromatic number, X(G). Consider the following algorithm for obtaining a P-partition of a given graph G, Let V1 be any maximal P-set of G, ie,, for any point u e Vi, <V1 U {u}> does not have property P, Remove the set V1 from G and select a second maximal P-set V2 of G1 G- V1 = <V(G) - V>. Next, select a third maximal P-set V3 of G2 = G1 - V2, etc, until we obtain a partition V1, V2,,,, V of V(G) such that for every i, 1 a i s m, Vi is a P-set, We will say that any P-partition of G which can be obtained in this way is of type-1, Lemma 1, If P is a homogeneous property of a graph G, then every P-partition of G of type-1 is complete. Proof. Let T = {VX V2,.. V } be a P-partition of G of type-1 which is not complete; then there exist two subsets V. and V., i < j, such that Vi and V. are P-sets and <Vi> and <,> are not line adjacent. But since P is homogeneous Vi U Vj is also a P-set, and hence Vi is not i-i a maximal P-set of G - UV V Therefore t is not of type-i; a contradick=l k" tion || If P is a homogeneous property of a graph G and n = {V1, V2,,., Vm} is a P-partition of G which is not complete, it readily follows that we can obtain from Tr a P-partition n' of order m' < m by adding together two sets V. and V. of T which are not line adjacent Thus we obtain the following, Lemma 2/ For any homogeneous property P and any graph G, if Xp(G) = m

4 then every P-partition of G of order m is complete. Theorem 1, For any homogeneous property P, if a graph G has a Ppartition of order m, then G has a P-partition of type-1 of order m' s m, Prooff Let i = {V1, V2, 2,, V } be a P-partition of G of order m,' m and let ul, u2,.,, up be an ordering of the points of G such that the points in V. precede the points in V. for i < j. Define the set W = }; i+l = i then define WJ1 _ WiWtui{} is a P-set, otherwise define W Define W WP; clearly V1 C W1, since P is homogeneous. Now form W2 in the same way from the set of points V - W1, ieeo, set 0 it i W2=, and set W i+l ti {u } if u+ W and W U{ui+} is a P-set:. + i1 1 otherwise set W = W2 Continuing in this way we will obtain partition i' = {Wl, W^,!,,, W}, with the property that Vi C UWi, which corresponds 1 m i W to a P-partition of type-1 of order m' < ml Theorem 2, If property P is homogeneous and a graph G has a (complete) P-partition of type-1 of orders k and m, then for all Q, k < Z < m, G has a (complete) P-partition of type-1 of order Q., Proof. Let t = {V1 V2, ~* V} and T = {W W,,,,, W } be the P-partitions of type-1 of orders k and m, respectively, Form the new partition T* = {W, V1 w!" f. V =W1} Since P is homogeneous!, * is also a P-partition. Applying the construction used in Theorem 1 we can obtain a partition T1 = (W1, Vl,1lV1.2,."' Vl k()} from which corresponds to a P-partition of type-1 of order k(l) < k + 1, Note that the first member of 71 is W1 because T is of type-l. Next we form the partition IT = (W1 W^2 V1l,W2 Vl,2-W2,., Vlkl)-W2} and then the partition t2 = (W1, W2* V203' E ^ V2k(2)} which corresponds to a P-partition of type-1 of order k(2?) k 2D Continuing in this way

5 we obtain a series of P-partitions of type-, r, 1 Tr 2, "f2 "m0k in which Tmk T and the order of nT.1 is at most one greater than the order of r., Theorem 3 For any homogeneous property P and any graph G, if G has a complete P-partition of order m which is not of type-1. then G has either a complete P-partition of type-1 of order m or a complete P-partition of order m - 1, Proof, Let -f = "V, V2 * * Vl} be a complete P-partition of G of order m. If r is not of type-1, let V. be the first set for which there exists a point u E Vj, i < j, such that V. U {u} is a P-set,, Consider the partition i' = {V1,'., Vi U (u)A},, V.-{u}., { u., V } and note that if V. - u} is empty then we have obtained a complete P-partition of order m 1 If on the other hand, V - {u} is not empty, then V. - {u} is still a P-set, since P is homogeneous, Thus r' is also a P-partition, If n' is not complete then there exists a set Vk such that <Vj {u}> and'k) not line adjacent. Then since P is homogeneous, the partition,T' = {Vi,., ViUtu},., Vj-{u} UVk,., V } is a complete P-partition of order m I 1 If on the other hand n' is complete, then either it is of type-I, and the theorem is proved, or it is not of type-1 and we repeat the above process, Eventually we must find either a P-partition of type-l of order m or a complete P-partition of order m - 1,i Finally, we obtain as in immediate consequence of Lemma 2 and Theorems 2 and 3 the following general Tinterpolation Theorem for complete partitions of graphs, Theore- m 4 For any homogeneous pro perAty Pi any graph G, and any integer k, Xp(G); k p(C(;), GC has a co;mplete P-partition of order k.

6 Since homomorphisms correspond one-to-one with P2-partitions, where for each subset Vi, <Vi> is totally disconnected, and since the property P2 that a graph be totally disconnected is homogeneous, the Homomorpi: sm i'nte rpo. iati on iTheorem o f c 3 is | an i:n,;dia:e coroa r r i y o! i heor em 4. iWe now detvelop fi or:a each of th.e above concepts and results for partitions of the set of points of a graph, corresponding concepts and results for partitions of the set of lines of a graph, Since proofs of the ccrprespond inr, l ine -results are nea. rly iidentical to those given already, they are omitted. Let = {E1, E2,.., E} be a partition of the set of lines of a graph G, By the factor nraph G/T we mean the graph for which V(G/T) = {E1' E2.. Er}, and (Ei. Ej) F E(G/rT) if and only if the subgraphs <Ei and Ej) are pi Ofnt a:.Ii /.::-:.; rii of the.ines of G is comlete if G/T is a complete graph. Let P denote any property of a graph G, A set of lines LEC E(G) is a P-line set if the subgraph <E'> has property P. A P-line partition of G of order m is a partition T - {E1 E2, f,,, E } of E(C) such that for every i, 1 i 5 m, E. is a P-line set, The P-line chromatic number of a graph G, X(G), is the minimum order of all complete P line partitions of G. The P-line achromatic number, ii'()i, is the maximum order of all compliete P- line partitions of I. We will be interested in properties P of a graph G which satisfy the following two conditions, For any graph G and any subsets r: EC E(C): i) if E. is a P-line set and E. C Ej then E. is also a P-line set, and (ii) if Ei and E. are disjoint P-line sets and the subgraphs <Ej> and Ei) are not point adjacent then Li U Ej is also a Pkline set, K - I

7 We will say that any property P which satisfies these two conditions is line-homo eneous, It'is easy to find line homogeneous properties of graphs, The property P1 of being a planar graph is also line=homogeneous,' he P' -line chromatic number of a graph C is then the minimum number of planar line disjoint subgraphs whose union is G, This parameter Xp'G) is traditionally called the thickness of G, 0(G) (cfo Beineke and Harary [1]), The property P3 that a graph contain no cycles is homogeneous and line homogeneous. The P3-line chromatic number of a graph G is the minimum number of line disjoint graphs, each of which contains no cycles, whose union is G, This parameter x' (G) is traditionally called the a,rborici6 t of G, arb(G) (cfe Nash=Williams ]l), The property P4 that a graph consist of a set of independent lines, i.e., no two lines have a point in co omon, i s zalso l ine; homoo: eneou: The P4 line chromatic number is traditionally called simply the linechromatic number, XC:. Consider the following algorithm for obtaining a P-line partition of a given graph G; Let El be any maximal P-i.i.n set of G, i,e, for any line [uv] t El, the subgraph <E1 U {[uv]}> does not have property P, Remove the set El. from G and select a sec ond maximal P-line set E2 from G1 = G - EI. Next select a third maximal P-line set E3 from G, = G - E etc., until we finally obtain a partitiion E, EL... ^ E of E(G) such that for every i. 1. i: m, E. i s a P in: set h'e will say that any P-line partition of G which can be obtaine;i in this way is of type-1 Lemma 1.. If P is a line-hk omogeineou:;S property of a graph G, then every P-line partition of C of type;-t is ep::'l etie

If P is a line-homogeneous property of a graph G and T = {El, E2,,.. E } is a P-line partition of G which is not complete, m it readily follows that we can obtain from T a P-line partition T' of order m - 1, Simply select two sets E. and E. for which the subgraphs E. 1 j and E. are not point adjacent and form the partition T -3, iUe E.UE,..., E } of order m -1; is still a P-line partition since P is line-homogeneous and Ei U Ej is still a P-line set, Thus we obtain Lemma 2', For any line-homogeneous property P and any graph G, if Xp(G) = m then every P-line partition of G of order m is complete, It follows from this lemma, for example, that if the thickness of a graph G, 0(G), is m, then the factor graph formed from G by any set of m line disjoint planar subgraphs, whose union equals G, is a complete graph. Theorem 1', For any line-homogeneous property P, if a graph G has a P-line partition of order m, then G has a P-line partition of type-1 of order m' < m. It follows from Theorem 1' that if the thickness 6(G) of a given graph G is m then there will exist a type-l partition of the set of lines of G which will produce m planar subgraphs into which G can be decomposed. Theorem 2'. If property P is line-homogeneous and a graph G has (complete) P-line partitions of type-1 of orders k and m, then for all integers,e k < i < mC G has a (complete) P-line partition of type-1 of order,. Theorem 3',. For any line-homogeneous property P and any graph G, if G has a complete P-line partition of order m which is not of type-l,

9 then G has either a complete P-line partition of type-1 of order m or a complete P-line partition of order m - 1, Finally, we obtain as an immediate consequence of Lemma 2' and Theorems 2' and 3' the following general Interpolation Theorem for complete line partitions of graphs. Theorem 4', For any line-homogeneous property P, any graph G, and any integer k, Xp(G) < k s $p(G), G has a complete P-line partition of order k.

REFERENCES 1 L. Beineke and F, Harary, "On the Thickness of the Complete Graph," Bull. Amer, Math. Soc., 70 (1964), pp. 618-620. 2. F. Harary, A Seminar on Graph Theory Holt, Rinehart, and Winston, New York, 196 3. F Harary, S, Hedetniemi and G, Prins, "An Interpolation Theorem for Graphical Homomorphisms," to apiowar, 4. C, St. J. A, Nash-Williams, "Edge-Disjoint Spanning Trees of Finite Graphs," J. London Math. Soc. 36, (1961), pp, 445-450. G r phs:........*10.........: -. 10

DISTRIBUTION LIST (One copy unless otherwise noted) Technical Library Naval Electronics Laboratory Director Defense Res. & Eng. San Diego 52, California Room 3C-128, The Pentagon Attn: Technical Library Washington, D.C. 20301 Dr. Daniel Alpert, Director Defense Documentation Center 20 Coordinated Science Laboratory Cameron Station University of Illinois Alexandria, Virginia 22314 Urbana, Illinois Chief of Naval Research 2 Air Force Cambridge Research Labs Department of the Navy Laurence C. Hanscom Field Washington 25, D.C. Bedford, Massachusetts Attn: Code 437, Information Attn: Research Library, CRMXL R Systems Branch U. S. Naval Weapons Laboratory Director, Naval Research Laboratory 6 Dahlgren, Virginia 22448 Technical Information Officer Attn: G. H. Gleissner, Code K4 Washington 25, D.C. Asst. Dir. for Computation Attention: Code 2000 National Bureau of Standards Commanding Officer 10 Data Processing Systems Division Office of Naval Research Room 239, Building 10 Navy 100, Fleet Post Office Box 39 Washington 25, D.C. New York, New York 09599 Attn: A. K. Smilow Commanding Officer George C. Francis ONR Branch Office Computing Laboratory, BRL 207 West 24th Street Aberdeen Proving Ground. Maryland New York 11, New York Office of Naval Research Office of Naval Research Branch Branch Office, Chicago Office 230 North Michigan Avenue 495 Summer Street Chicago, Illinois 60601 Boston, Massachusetts 02110 Commanding Officer Naval Ordnance Laboratory ONR Branch Office White Oaks, Silver Spring 19 1030 E. Green Street Maryland Pasadena, California Attn: Technical Library Commanding Officer David Taylor Model Basin ONR Branch Office Washington,D.C. 20007 1076 Mission Street Attnt Code 042, Technical Library San Francisco, California 94103

DISTRIBUTION LIST (Concluded) The University of Michigan Lincoln Laboratory Department of Philosophy Massachusetts Institute of Technology Attn: Professor A. W. Burks Lexington 73, Massachusetts Attn: Library National Physical Laboratory Teddington, Middlesex, England Office of Naval Research Attn: Dr. A. M. Uttley, Supt. Washington 25, D.C. Autonomies Division Attn: Code 432 Commanding Officer Dr. Kenneth Krohn Harry Diamond Laboratories Krohn Rhodes Research Institute, Inc. Washington, D.C. 20438 328 Pennsylvania Avenue, S. E. Attn: Library Washington 13, D. C. Commanding Officer and Director U. S. Naval Training Device Center Dr. Larry Fogel Port Washington Decision Science, Inc. Long Island, New York 6508 Pacific Highway Attn: Technical Library San Diego, California Department of the Army Office of the Chief of Research National Bureau of Standards and Development Applications Engineering Section Pentagon, Room 3D442 Washington 25, D. C. Washington 25, D.C. Attn: Miss Mary E. Stevens Attn: Mr. L. H. Geiger National Security Agency Fort George G. Meade, Maryland Attn: Librarian, C-332

Unclassified Security Classification DOCUMENT CONTROL DATA R&D (Security classification of title, body of abstract and indexing annotation must be entered when the overall report is claesilfid) 1. ORIGINATING ACTIVITY (Corporate author) 2. REPORT SECURITY C LASSIFICATION Logic of Computers Group Unclassified The University of Michigan 2b GROUP Ann Arbor. Michigan 48104.... 3. REPORT TITLE SOME INTERPOLATION THEOREMS FOR PARTITIONS OF GRAPHS 4 DESCRIPTIVE NOTES (Typ of report and incltusve dates) Technical Report 5. AUTHOR(S) (Laot name, first name, initial) Hedetniemi, Stephen 6. REPORT DATE 7a. TOTAL NO. OF PAGES 7b. NO. OF REPS March 1967 10 4 8a. CONTRACT OR GRANT NO. 9a. ORIGINATOR'S REPORT NUMBER(S) Nonr 1224(21) 03105-47-T b. PROJECT NO. c..6. OTH ERR PORT NO(S) (Any other numbere that may be aesigned tie report d. 1 0. AVA ILABILITY/LIMITAtION NOTICES Distribution of this document is unlimited. 11. SUPPLEMENTARY NOTES 12. SPONSORING MILITARY ACTIVITY 13 ABSTRACT In this paper we consider certain partitions of the set of points and of the set of lines of a graph and we define for each such partition a corresponding factor graph. The concepts of a complete P-partition and a complete P-line partition of order m are then defined for an arbitrary property P of a graph G. Two results are then obtained which answer the following questions: for what properties P of a graph G does it follow that if G has complete P-partitions (P-line partitions) or orders m and n, then G has complete P-partitions (P-line partitions) of orders k for any k, m < k < n. Do D1 JAN 16473 Unclassified Security Classification

_Unclassified Security Classification r14. LINK A LINK B LINK C KEY WORDS 4,DESCRIPTIVENOTKEY WORDSIf_ appropr| ROLE WT ROLE WT ROLE WT graphs partitions invari ants INSTRUCTIONS 1. ORIGINATING ACTIVITY: Enter the name and address imposed by security classification, using standard statements of the contractor, subcontractor, grantee, Department of De- such as: fense activity or other organization (corporate author) issuing (1) "Qualified requesters may obtain copies of this the report. report from DDC." 2 a. REPORT SECUITY CLASSIF-C ATION: En otes. 2a. REPORT SECURTY CLASSIFICATION: Enter the. over (2) "Foreign announcement and dissemination of this all security classification of the report. Indicate whether eor i not au ie "Restricted Data" is included. Marking is to be in accord- y t auoiz ance with appropriate security regulations. (3) "U. S. Government agencies may obtain copies of [ on.^-,-,.....r. -. * r^ TN TNthis report directly from DDC. Other qualified DDC 2b. GROUP: Automatic downgrading is specified in DoD Di- ths report request through rective 5200.10 and Armd rm Forces Industrial Manual. Enter the group number. Also, when applicable, show that optional _ markings have been used for Group 3 and Group 4 as author- (4) "U. S. military agencies may obtain copies of this ized. report directly from DDC. Other qualified users 3. REPORT TITLE: Enter the complete report title in all shall request through capital letters. Titles in all caes should be unclassified. If a meaningful title cannot be selected without classification, show title classification in all capitals in parenthesis (5) "All distribution of this report is controlled Qualimmediately following the title. ified DDC users shall request through 4. DESCRIPTIVE NOTES: If appropriate, enter the type of i_____ report, e.g., interim, progress, summary, annual, or final. If the report has been furnished to the Office of Technical Give the inclusive dates when a specific reporting period is Seryices, Department of Commerce, for sale to the public, indicovered. cate this fact and enter the price, if known. 5. AUTHOR(S): Enter the name(s) of author(s) as shown on 11. SUPPLEMENTARY NOTES: Use for additional explanaor in the report. Entet last name, first name, middle initial tory notes. If military, show rank and branch of service. The name of the principal author is an absolute minimum requirement 12. SPONSORING MILITARY ACTIVITY: Enter the name of the departmental project office or laboratory sponsoring (pay 6. REPORT DATE: Enter the date of the report as day, ing for) the research and development. Include address. month, year; or month, year. If more than one date appears on the report, use date of publication. 13. ABSTRACT: Enter an abstract giving a brief and factual summary of the document indicative of the report, even though 7a. TOTAL NUMBER OF PAGES: The total page count it may also appear elsewhere in the body of the technical reshould follow normal pagination procedures, i.e., enter the port. If additional space is required, a continuation sheet shall number of pages containing information be attached. 76. NUMBER OF REFERENCES: Enter the total number of It is highly desirable that the abstract of classified reports references cited in the report, be unclassified. Each paragraph of the abstract shall end with 8a. CONTRACT OR GRANT NUMBER: If appropriate, enter an indication of the military security classification of the inthe applicable number of the contract or grant under which formation in the paragraph, represented as (TS) (S), (C), or (U) the report was written There is no limitation on the length of the abstract. How8b, 8c, & 8d. PROJECT NUMBER: Enter the appropriate ever, the suggested length is from 150 to 225 words. military department identification, such as project number, 14. KEY WORDS: Key words are technically meaningful terms subproject number, system numbers, task number ette, subproject number, system numberstasknumbec., or short phrases that characterize a report and may be used as 9a. ORIGINATOR'S REPORT NUMBER(S): Enter the offi- index entries for cataloging the report. Key words must be cial report number by which the document will be identified selected so that no security classification is required. Identiand controlled by the originating activity. This number must fiers, such as equipment model designation, trade name, military be unique to this report. project code name, geographic location, may be used as key 9b. OTHER REPORT NUMBER(S): If the report has been words but will be followed by an indication of technical conassigned any other repcrt numbers (either by the originator text. The assignment of links, rules, and weights is optional. or by the sponsor), also enter this number(s),. 10, AVAILABILITY/LIMITATION NOTICES: Enter any lim- itations on further dissemination of the report, other than those _ Unclassi fied Security Classification

UNIVERSITY OF MICHIGAN 3 9III015 03026 9230 3 9015 03026 9230