{VERSION 6 0 "SGI MIPS UNIX" "6.0" } {USTYLETAB {CSTYLE "_cstyle1" -1 201 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "_cstyle2" -1 202 "Times" 1 18 255 0 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "_cstyle3" -1 203 "Times" 1 18 0 255 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "_cstyle4" -1 204 "Times" 1 18 0 0 255 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "_cstyle5" -1 205 "Times" 1 18 102 102 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "_cstyle6" -1 206 "Times" 1 18 0 255 255 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "_cstyle7" -1 207 "Times" 1 18 255 51 204 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "_cstyle8" -1 208 "Times" 1 14 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "_cstyle9" -1 209 "Times" 1 14 0 0 255 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "_cstyle10" -1 210 "Courier" 1 12 255 0 0 1 2 1 2 2 1 2 0 0 0 1 }{CSTYLE "_cstyle11" -1 211 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "_cstyle12" -1 212 "Times" 1 18 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "_cstyle13" -1 213 "Courier" 1 14 255 0 0 1 2 1 2 2 1 2 0 0 0 1 }{CSTYLE "_cstyle14" -1 214 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE " Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }{PSTYLE "_pstyle1" -1 200 1 {CSTYLE "" -1 -1 "Courier" 1 12 255 0 0 1 0 1 0 2 1 2 0 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "_pstyle2" -1 201 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "_p style3" -1 202 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 255 1 0 0 0 2 2 1 0 0 0 1 }3 3 0 -1 -1 -1 1 0 1 0 2 2 -1 1 }{PSTYLE "_pstyle4" -1 203 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 }} {SECT 0 {EXCHG {PARA 3 "" 0 "" {TEXT -1 52 "Polynomial Constructions i n the Graph Theory Package" }}{PARA 0 "" 0 "" {TEXT -1 22 "Jeff Farr, \+ March 2005." }}}{EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 18 "with(Grap hTheory):" }}}{EXCHG {PARA 201 "" 0 "" {TEXT 201 6 "Graph " }{TEXT 202 1 "C" }{TEXT 203 1 "o" }{TEXT 201 1 "l" }{TEXT 204 1 "o" }{TEXT 205 1 "r" }{TEXT 201 1 "i" }{TEXT 206 1 "n" }{TEXT 207 1 "g" }}{PARA 201 "" 0 "" {TEXT -1 0 "" }}{PARA 201 "" 0 "" {TEXT 208 2 "A " }{TEXT 209 15 "proper coloring" }{TEXT 208 116 " of a graph G=(V,E) is a labe lling of V so that adjacent vertices do not have the same label.\n\nTh e chromatic number " }{TEXT 210 6 "chi(G)" }{TEXT 208 45 " is the mini mum k such that V is k-colorable." }}{PARA 201 "" 0 "" {TEXT -1 0 "" } }{PARA 201 "" 0 "" {TEXT 208 10 "Computing " }{TEXT 210 6 "chi(G)" } {TEXT 208 4 " is " }{TEXT 209 7 "NP-hard" }{TEXT 208 78 ". Even for \" small\" graphs, there do not exist effective algorithms to compute " } {TEXT 210 7 "chi(G)." }{TEXT 208 9 "\n\nWe can " }{TEXT 211 5 "bound" }{TEXT 208 1 " " }{TEXT 210 6 "chi(G)" }{TEXT 208 10 " however. " } {TEXT 204 13 "\n\nUpperbound:" }{TEXT 212 1 " " }}{PARA 201 "" 0 "" {TEXT -1 0 "" }}{PARA 201 "" 0 "" {TEXT 208 4 "Use " }{TEXT 209 15 "gr eedy coloring" }{TEXT 208 14 ". The command " }{TEXT 210 14 "GreedyCol or(G)" }{TEXT 208 10 "is in the " }{TEXT 210 11 "GraphTheory" }{TEXT 208 9 " package." }{TEXT 204 14 "\n\nLowerbound: " }}{PARA 201 "" 0 " " {TEXT -1 0 "" }}{PARA 201 "" 0 "" {TEXT 208 8 "Use the " }{TEXT 209 14 "largest clique" }{TEXT 208 6 " size " }{TEXT 210 8 "omega(G)" }} {PARA 201 "" 0 "" {TEXT 208 3 "AND" }}{PARA 201 "" 0 "" {TEXT 208 1 " \+ " }{TEXT 209 23 "largest independent set" }{TEXT 208 2 ", " }{TEXT 210 12 "n / alpha(G)" }}{PARA 201 "" 0 "" {TEXT -1 0 "" }}{PARA 201 " " 0 "" {TEXT 208 14 "Compute using " }{TEXT 210 15 "CliqueNumber(G)" } {TEXT 208 16 " command in the " }{TEXT 210 11 "GraphTheory" }{TEXT 208 9 " package " }}{PARA 201 "" 0 "" {TEXT 208 1 "(" }{TEXT 209 10 "V ERY FAST!" }{TEXT 208 2 ")." }{TEXT -1 1 "\n" }}}{EXCHG {PARA 200 "> \+ " 0 "" {MPLTEXT 1 -1 141 "G := PetersenGraph():\n\nGraphTheory:-Greedy Color(G),\nCliqueNumber(G),\n\nNumberOfVertices(G) / IndependenceNumbe r(G);\n\nChromaticNumberBound(G);\n" }}{PARA 202 "" 1 "" {XPPMATH -1 " 6%\"\"$\"\"##\"\"&F$" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#\"\"$" }}} {EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 51 "G := RandomGraph(100,0.1) :\nChromaticNumberBound(G);" }}{PARA 202 "" 1 "" {XPPMATH -1 "6&\"\"& \"\"'\"\"(\"\")" }}}{EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 76 "G := \+ RandomGraph(1000,100000):\nT:=time(): ChromaticNumberBound(G); time()- T;" }}{PARA 202 "" 1 "" {XPPMATH -1 "60\"#S\"#T\"#U\"#V\"#W\"#X\"#Y\"# Z\"#[\"#\\\"#]\"#^\"#_\"#`" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#$\"&g8 \"!\"$" }}}{EXCHG {PARA 201 "" 0 "" {TEXT 201 21 "Creating graphs with " }{TEXT 204 5 "large" }{TEXT 201 18 " chromatic number." }{TEXT 208 41 "\n\nTrivial: Add a large clique to a graph" }}{PARA 201 "" 0 "" {TEXT -1 0 "" }}{PARA 201 "" 0 "" {TEXT 211 22 "Mycielski construction " }{TEXT 208 2 ": " }}{PARA 201 "" 0 "" {TEXT 208 42 " Given: a triangle-free graph with " }{TEXT 209 1 "n" }{TEXT 208 31 " vertices \+ and chromatic number " }{TEXT 209 1 "k" }}{PARA 201 "" 0 "" {TEXT 208 43 " Return: a triangle-free graph with " }{TEXT 209 6 "(2n+1) " }{TEXT 208 31 " vertices and chromatic number " }{TEXT 209 3 "k+1" } }{PARA 201 "" 0 "" {TEXT -1 0 "" }}{PARA 201 "" 0 "" {TEXT 208 7 "Exam ple" }{TEXT -1 1 "\n" }}{PARA 201 "" 0 "" {TEXT -1 0 "" }}{PARA 201 " " 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 231 " G := CycleGraph(5); ChromaticNumberBound(G);\nG1 := Mycielski(G); Chro maticNumberBound(G1);\nG2 := Mycielski(G1); ChromaticNumberBound(G2); \nG3 := Mycielski(G2); ChromaticNumberBound(G3);\nG4 := Mycielski(G3); ChromaticNumberBound(G4);" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#>%\"GG% 8A~Graph~with~5~verticesG" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#\"\"$" } }{PARA 202 "" 1 "" {XPPMATH -1 "6#>%#G1G%9A~Graph~with~11~verticesG" } }{PARA 202 "" 1 "" {XPPMATH -1 "6$\"\"$\"\"%" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#>%#G2G%9A~Graph~with~23~verticesG" }}{PARA 202 "" 1 "" {XPPMATH -1 "6%\"\"$\"\"%\"\"&" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#>%# G3G%9A~Graph~with~47~verticesG" }}{PARA 202 "" 1 "" {XPPMATH -1 "6&\" \"$\"\"%\"\"&\"\"'" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#>%#G4G%9A~Graph ~with~95~verticesG" }}{PARA 202 "" 1 "" {XPPMATH -1 "6'\"\"$\"\"%\"\"& \"\"'\"\"(" }}}{EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 20 "ChromaticN umber(G2);" }}{PARA 202 "" 1 "" {XPPMATH -1 "6$\"\"&79\"\"!\"\"\"F%F& \"\"#F%F&F%F&F'\"\"$F%F&F%F&F'F%F&F%F&F'F(\"\"%" }}}{EXCHG {PARA 201 " " 0 "" {TEXT 201 17 "Graph Polynomials" }{TEXT 213 26 "\n\nChromaticPo lynomial(G,p)" }{TEXT 208 59 " counts the number of proper colorings o f G using p colors." }}{PARA 201 "" 0 "" {TEXT -1 0 "" }}{PARA 201 "" 0 "" {TEXT 208 62 "Hence, the first nonzero integer root is the chroma tic number." }}{PARA 201 "" 0 "" {TEXT -1 0 "" }}{PARA 201 "" 0 "" {TEXT 208 10 "Computing " }{TEXT 210 24 "ChromaticPolynomial(G,p)" } {TEXT 208 7 " solves" }{TEXT 211 24 " an NP-complete problem " }{TEXT 208 15 "as a subproblem" }{TEXT 211 1 "!" }}{PARA 201 "" 0 "" {TEXT -1 0 "" }}{PARA 201 "" 0 "" {TEXT -1 0 "" }}{PARA 201 "" 0 "" {TEXT 209 25 "ChromaticPolynomial(G,p) " }}{PARA 201 "" 0 "" {TEXT 209 93 " \+ = ChromaticPolynomial( DeleteEdge(G,e), p ) - ChromaticPolynomi al( Contract(G,e), p )" }}{PARA 201 "" 0 "" {TEXT -1 0 "" }}{PARA 201 "" 0 "" {TEXT 213 24 "ChromaticPolynomial(G,p)" }{TEXT 208 22 " is a s pecial case of " }{TEXT 210 22 "TuttePolynomial(G,x,y)" }}{PARA 201 " " 0 "" {TEXT 208 43 "\nOther polynomials that are evaluations of " } {TEXT 210 22 "TuttePolynomial(G,x,y)" }{TEXT 208 1 ":" }}{PARA 201 "" 0 "" {TEXT 208 9 "\n " }{TEXT 210 100 "AcyclicPolynomial(G,x), \+ FlowPolynomial(G,y), \n RankPolynomial(G,x,y), SpanningPolynomi al(G,y)" }{TEXT -1 2 "\n\n" }}}{EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 46 "G := CompleteGraph(4):\nTuttePolynomial(G,x,y);" }}{PARA 202 " " 1 "" {XPPMATH -1 "6#,0*$%\"yG\"\"$\"\"\"*$F%\"\"#F&*&%\"xGF'F%F'\"\" %F%F)F+F)*$F+F)F&*$F+F&F'" }}}{EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 92 "E := Edges(G);\nDeleteEdge(G,E[1],inplace=true):\n\nop(G);\nEdg es(G);\n\nChromaticPolynomial(G,p);" }}{PARA 202 "" 1 "" {XPPMATH -1 " 6#>%\"EG<(<$\"\"#\"\"$<$F(\"\"%<$\"\"\"F'<$F'F*<$F,F(<$F,F*" }}{PARA 202 "" 1 "" {XPPMATH -1 "6(%+undirectedG%+unweightedG7&\"\"\"\"\"#\"\" $\"\"%-%'RTABLEG6%\"(_b@&-%'VECTORG6#7&<%F'F(F)<$F&F)F3<%F&F'F(%&Array G-%&TABLEG6#7\"\"\"!" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#<'<$\"\"$\"\" %<$\"\"\"\"\"#<$F)F&<$F(F%<$F(F&" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#* (%\"pG\"\"\",&F$F%!\"\"F%F%,&F$F%!\"#F%\"\"#" }}}{EXCHG {PARA 201 "" 0 "" {TEXT 201 25 "Multigraphs / Edgeweights" }}{PARA 201 "" 0 "" {TEXT -1 0 "" }}{PARA 201 "" 0 "" {TEXT 208 4 "For " }{TEXT 210 17 "Tu ttePolynomial()" }{TEXT 208 61 ", we had to create capabilites for dea ling with multigraphs. " }}{PARA 201 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 25 "G := RandomGraph(8,0.45):" }}} {EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 37 "Gw := MakeWeighted(G):\no p(G);\nop(Gw);" }}{PARA 202 "" 1 "" {XPPMATH -1 "6(%+undirectedG%+unwe ightedG7*\"\"\"\"\"#\"\"$\"\"%\"\"&\"\"'\"\"(\"\")-%'RTABLEG6%\"(K-e#- %'VECTORG6#7*<#F,<%F(F)F+<$F'F-<%F'F*F-<%F)F+F-<$F'F*<#F&<%F(F)F*%&Arr ayG-%&TABLEG6#7\"\"\"!" }}{PARA 202 "" 1 "" {XPPMATH -1 "6(%+undirecte dG%)weightedG7*\"\"\"\"\"#\"\"$\"\"%\"\"&\"\"'\"\"(\"\")-%'RTABLEG6%\" (K-e#-%'VECTORG6#7*<#F,<%F(F)F+<$F'F-<%F'F*F-<%F)F+F-<$F'F*<#F&<%F(F)F *%&ArrayG-%&TABLEG6#7\"-F/6%\"(wSB&-%'MATRIXG6#7*7*\"\"!FKFKFKFKFKF&FK 7*FKFKF&F&FKF&FKFK7*FKF&FKFKFKFKFKF&7*FKF&FKFKF&FKFKF&7*FKFKFKF&FKF&FK F&7*FKF&FKFKF&FKFKFK7*F&FKFKFKFKFKFKFK7*FKFKF&F&F&FKFKFK%'MatrixG" }}} {EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 16 "Ew := Edges(Gw);" }} {PARA 202 "" 1 "" {XPPMATH -1 "6#>%#EwG<+7$<$\"\"%\"\")\"\"\"7$<$\"\"& \"\"'F*7$<$F-F)F*7$<$\"\"#\"\"$F*7$<$F3F(F*7$<$F*\"\"(F*7$<$F3F.F*7$<$ F4F)F*7$<$F(F-F*" }}}{EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 116 "GwC := Contract(Gw,Ew[1]):\nGC := Contract(G,Ew[1][1],multi=true): # a lso has multi=true feature\n\nop(GwC);\nop(GC);" }}{PARA 202 "" 1 "" {XPPMATH -1 "6(%+undirectedG%)weightedG7)\"\"\"\"\"#\"\"$<$\"\"%\"\") \"\"&\"\"'\"\"(-%'RTABLEG6%\"(3s\"y-%'VECTORG6#7)<#F.<%F(F*F-<$F'F*<%F 'F(F,<$F*F-<$F'F,<#F&%&ArrayG-%&TABLEG6#7\"-F06%\"(Wss(-%'MATRIXG6#7)7 )\"\"!FKFKFKFKFKF&7)FKFKF&F&FKF&FK7)FKF&FKF&FKFKFK7)FKF&F&FKF'FKFK7)FK FKFKF'FKF&FK7)FKF&FKFKF&FKFK7)F&FKFKFKFKFKFK%'MatrixG" }}{PARA 202 "" 1 "" {XPPMATH -1 "6(%+undirectedG%)weightedG7)\"\"\"\"\"#\"\"$<$\"\"% \"\")\"\"&\"\"'\"\"(-%'RTABLEG6%\");8g@-%'VECTORG6#7)<#F.<%F(F*F-<$F'F *<%F'F(F,<$F*F-<$F'F,<#F&%&ArrayG-%&TABLEG6#7\"-F06%\")kRQB-%'MATRIXG6 #7)7)\"\"!FKFKFKFKFKF&7)FKFKF&F&FKF&FK7)FKF&FKF&FKFKFK7)FKF&F&FKF'FKFK 7)FKFKFKF'FKF&FK7)FKF&FKFKF&FKFK7)F&FKFKFKFKFKFK%'MatrixG" }}}{EXCHG {PARA 201 "" 0 "" {TEXT 201 18 "Other Polynomials:" }}{PARA 201 "" 0 " " {TEXT -1 0 "" }}{PARA 201 "" 0 "" {TEXT -1 4 "The " }{TEXT 209 16 "G raph Polynomial" }{TEXT -1 44 " of G is an n-variate polynomial define d by " }}{PARA 203 "" 0 "" {TEXT 210 44 "f := product( (x_i - x_j) : \+ \{i,j\} in E, i" }{TEXT -1 2 " " }}{PARA 201 "" 0 "" {TEXT -1 23 "(over complex numbers)." }}}{EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 105 "G := Graph([1,2,3,4,5,6],\{\{4,5\},\{3,4\},\{4,6\}, \{5,6\},\{3,5\},\{1,4\},\{2,6\}\}):\nf := GraphPolynomial(G);\nEdges(G );" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#>%\"fG*0,&%#x3G\"\"\"%#x4G!\"\" F(,&%#x2GF(%#x6GF*F(,&%#x5GF(F-F*F(,&F)F(F-F*F(,&F'F(F/F*F(,&%#x1GF(F) F*F(,&F)F(F/F*F(" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#<)<$\"\"$\"\"%<$ \"\"#\"\"'<$\"\"&F)<$F&F)<$F%F+<$\"\"\"F&<$F&F+" }}}{EXCHG {PARA 200 " > " 0 "" {MPLTEXT 1 -1 24 "ChromaticNumberBound(G);" }}{PARA 202 "" 1 "" {XPPMATH -1 "6%\"\"#\"\"$\"\"%" }}}{EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 218 "with(PolynomialIdeals):\n\nn:=nops(Vertices(G));\n \nfor k from 2 to 3 do\n xvars := seq( x||j, j=1..n);\n J := < seq( \+ xvars[j]^k -1, j=1..n) >;\n NormalForm(f,J,plex(xvars));\n print(\"- --------------------------\");\nend do;" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#>%\"nG\"\"'" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#>%&xvarsG6(%#x1G %#x2G%#x3G%#x4G%#x5G%#x6G" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#>%\"JG-% $<,>G6(,&*$%#x1G\"\"#\"\"\"!\"\"F,,&*$%#x2GF+F,F-F,,&*$%#x3GF+F,F-F,,& *$%#x4GF+F,F-F,,&*$%#x5GF+F,F-F,,&*$%#x6GF+F,F-F," }}{PARA 202 "" 1 " " {XPPMATH -1 "6#\"\"!" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#Q<--------- ------------------6\"" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#>%&xvarsG6(% #x1G%#x2G%#x3G%#x4G%#x5G%#x6G" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#>%\" JG-%$<,>G6(,&*$%#x1G\"\"$\"\"\"!\"\"F,,&*$%#x6GF+F,F-F,,&*$%#x5GF+F,F- F,,&*$%#x4GF+F,F-F,,&*$%#x3GF+F,F-F,,&*$%#x2GF+F,F-F," }}{PARA 202 "" 1 "" {XPPMATH -1 "6#,\\t*,%#x1G\"\"\"%#x2GF&%#x4GF&%#x5G\"\"#%#x6GF*! \"\"*(F'F&%#x3GF&F(F*F,**F%F&F.F&F)F&F+F&F&*(F'F&F(F*F+F&F,*(F.F*F)F&F +F&F&*(F'F&F.F*F)F&F,*(F(F&F)F&F+F*F,*(F'F&F.F*F+F&F&*(F.F*F(F&F)F&F,* *F.F&F(F&F)F&F+F&F,*,F'F&F.F*F(F&F)F*F+F&F,*(F.F&F)F*F%F&F,*(F.F*F%F&F (F&F,*,F'F&F.F&F(F*F)F*F+F&F&**F'F&F.F&F+F&F)F&F,*,F%F&F'F&F.F*F)F&F+F *F,**F.F&F(F*F)F*F+F*F,*(F%F&F)F&F+F*F&**F%F&F'F&F(F&F+F&F&*,F%F&F'F&F (F*F)F&F+F*F&*(F(F&F)F*F+F&F&*(F'F&F.F&F+F*F&F.F,F+F,F)F&F'F&*.F%F&F'F &F.F&F(F&F)F*F+F&F,**F.F*F(F&F)F*F+F*F&*(F%F&F(F*F+F&F&*,F'F&F.F&F(F&F )F*F+F*F,**F'F&F.F*F(F*F+F*F,*,F%F&F.F&F(F&F)F*F+F*F&**F'F&F.F&F)F&F(F &F&*,F%F&F'F&F.F*F(F&F+F*F&**F%F&F'F&F)F&F+F&F,*(F%F&F(F&F+F*F,*,F%F&F 'F&F.F&F)F*F+F*F&**F%F&F'F&F.F&F(F&F&*.F%F&F'F&F.F&F(F*F)F&F+F&F&*,F%F &F'F&F.F*F)F*F+F&F&*&F(F*F)F*F,*(F.F*F%F&F)F&F&*(F%F&F)F*F+F&F,*,F%F&F 'F&F.F*F(F&F)F*F,**F%F&F.F*F(F*F+F*F&*(F.F&F(F*F+F&F&*(F%F&F'F&F)F*F&* *F.F*F(F*F)F*F+F&F,*(F'F&F)F*F(F&F,**F'F&F(F*F)F*F+F*F&*(F(F&F)F*F%F&F &**F'F&F)F&F+F&F(F&F&*(F.F&F(F&F)F*F&*,F%F&F'F&F.F*F(F*F)F&F&*,F%F&F.F &F(F*F)F&F+F*F,*(F(F*F)F&F%F&F,*(F'F&F)F&F+F*F,**F%F&F'F&F.F&F)F&F,**F 'F&F.F*F(F*F)F*F&*,F%F&F'F&F.F&F(F*F+F*F,**F%F&F.F&F(F&F+F&F,**F%F&F.F *F)F*F+F*F,*(F.F&F+F*F)F&F&*,F%F&F.F*F(F*F)F&F+F&F,*,F'F&F.F*F(F&F)F&F +F*F&*(F%F&F'F&F(F*F,*&F.F*F(F*F&*&F.F*F+F*F,*&F(F*F+F*F&*(F.F&F(F*F%F &F&*,F%F&F.F*F(F&F)F*F+F&F&*,F%F&F'F&F.F*F(F*F+F&F," }}{PARA 202 "" 1 "" {XPPMATH -1 "6#Q<---------------------------6\"" }}}{EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 19 "ChromaticNumber(G);" }}{PARA 202 "" 1 "" {XPPMATH -1 "6$\"\"$7(\"\"!F%\"\"\"\"\"#F%F&" }}}{EXCHG {PARA 201 " " 0 "" {TEXT -1 4 "The " }{TEXT 209 25 "Characteristic Polynomial" } {TEXT -1 266 " of G is a well-known univariate polynomial defined to b e the characteristic polynomial of the adjacency matrix of G. Correspo ndingly, the eigenvalues of the characteristic polynomial are called t he eigenvalues of G. There are many results using these eigenvalues. \+ \n" }}{PARA 201 "" 0 "" {TEXT 214 8 "Result 1" }{TEXT -1 7 " " } {TEXT 210 14 "Diameter(G) < " }{TEXT -1 55 "number of distinct eigenva lues of G (for connected G). " }}{PARA 201 "" 0 "" {TEXT -1 0 "" }} {PARA 201 "" 0 "" {TEXT 214 8 "Result 2" }{TEXT -1 7 " " }{TEXT 210 20 "MinimumDegree(G) <= " }{TEXT -1 23 "largest eigenvalue of G" } {TEXT 210 20 " <= MaximumDegree(G)" }}{PARA 201 "" 0 "" {TEXT -1 0 "" }}{PARA 201 "" 0 "" {TEXT 214 23 "Result 3 (Wilf, 1967) " }{TEXT -1 2 " " }{TEXT 210 25 "ChromaticNumber(G) - 1 <=" }{TEXT -1 25 " larges t eigenvalue of G\n" }}{PARA 201 "" 0 "" {TEXT 214 8 "Result 4" } {TEXT -1 81 " A k-regular connected graph G is a strongly regula r graph with parameters " }{TEXT 210 1 "k" }{TEXT -1 2 ", " }{TEXT 210 6 "lambda" }{TEXT -1 5 " and " }{TEXT 210 2 "mu" }{TEXT -1 76 " if and only if it has exactly three eigenvalues k > r > s satisfying: ( 1) " }{TEXT 210 18 "r+s = lambda - mu " }{TEXT -1 8 "and (2) " }{TEXT 210 10 "r*s = mu-k" }}{PARA 201 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 23 "G := RandomGraph(9,.3);" }}{PARA 202 " " 1 "" {XPPMATH -1 "6#>%\"GG%8A~Graph~with~9~verticesG" }}}{EXCHG {PARA 200 "> " 0 "" {MPLTEXT 1 -1 80 "Diameter(G);\nf := Characteristi cPolynomial(G);\nEv := solve(f=0):\nnops( \{ Ev \} );" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#\"\"$" }}{PARA 202 "" 1 "" {XPPMATH -1 "6#>%\"fG,4 *$%\"xG\"\"*\"\"\"*$F'\"\"(!#8*$F'\"\"'!\"'*$F'\"\"&\"#X*$F'\"\"%\"#G* $F'\"\"$!#Y*$F'\"\"#!#GF'\"#6F4F)" }}{PARA 202 "" 1 "" {XPPMATH -1 "6# \"\"*" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{MARK "0 1 0" 22 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }