<ÒchapterÞ÷—¡‘’•£þ¤ýÒlabelÞÐchoos_chapÐ××
<
<·ÒsetcounterÞÐpreathmÐ×ÞÐ0Ð×
<ÒsetcounterÞÐpthmÐ×ÞÐ0Ð×
<·ÒsetcounterÞÐpreconjaÐ×ÞÐ0Ð×
<
<ûõ‘öÚ¯ø¤ÚîùÚ¢¤Úê¬ñÚ•þ©Úª‘¤ùÚª¢ŠÚ÷¡¨—þöÚõêúøõüÚîùÚ¢¤Ú¤÷ïõþ¥ý
<óþ¨—üÚõ¯¤žÚª¢ùÚõêúøôÚ÷—¡‘’•£þ¤ýÚð¤êú‘¨–ÆÚ¢¤ÚþöÚê¬ñÚ“ùÚ“þ‘öÚð¥þ¢ùýÚ¥
<÷—þ›ùû‘ýÚõø›ø¢Ú¢¤“‘¤ùÚþöÚõêúøôÚõü•¤¢¥þôÆ
<
<ð¤Úð¤éÚ$G$Ú“¤ýÚû¤Ú$f$Åóþ¨–¢ûüÚ$L$Ú“ùÚ¤»¨ú‘þ©Ú¢¨–îôÚþíÚ$L$Å¤÷ïõþ¥ý
<¢ª—ùÚ“‘ª¢ŠÚðøþþôÚ$G$Úð¤êüÚÞÒsiahÚ$f$Å÷—¡‘’•£þ¤×ÒindexÞ$f$Å÷—¡‘’•£þ¤×
<¨–Æ
<îøî—¤þöÚä¢¢Ú¢¤¨–Ú$k$ÚîùÚ“ùÚ¥ýÚöÚ$G$Úð¤êüÚ$k$Å÷—¡‘’•£þ¤Ú¨–Ú¤
<ÞÒsiahÚä¢¢Ú¤÷ðüÚóþ¨—ü×ÒfootnoteÞlist chromatic number×ÒindexÞä¢¢Ú¤÷ðüÚóþ¨—ü×
<$G$Úõü÷‘õþôÚøÚ“‘Ú÷õ‘¢
<$\ch(G)$Ú÷õ‘þ©Úõü¢ûþôÒfootnoteÞ¢¤Ú“¤¡üÚõ¤›âÚ¬¯òžÚÞÒsiahÚä¢¢Ú÷—¡‘’×
<¾choice number½ÚÒindexÞä¢¢Ú÷—¡‘’×Ú¤Ú“¤ýÚä¢¢Ú¤÷ðüÚóþ¨—üÚ“ùÚî‘¤Úõü“¤÷¢Úø
<öÚ¤Ú“‘Ú${\rm ch}(G)$Ú÷õ‘þ©Úõü¢û÷¢Æ×Æ
<
<ÒbeginÞexmpl×ÒhspaceÞ.6em×Òrm
<ð¤Ú$G$Úð¤êüÚ—úüÚ“‘ª¢ŠÚ“ùÚ¥ýÚû¤Úóþ¨–¢ûüÚ÷‘—úüÚ“ùÚ¤»¨ú‘þ©ÚþíÚ¤÷ïõþ¥ý
<óþ¨—üÚ¢¤¢ÚøÚ“÷‘“¤þöÚ$\ch(G)=1$ÆÚ¥Ú¯¤êüÚ¤øªöÚ¨–ÚîùÚð¤Úð¤éÚ$G$Ú¢¤ý
<ä¢¢Ú¤÷ðüÚóþ¨—üÚ$1$Ú“‘ª¢ŠÚ$G$ÚûþœÚþ‘óüÚ÷¢¤¢ÆÚ•§Ú$\ch(G)=1$ŠÚð¤ÚøÚ—÷ú‘Úð¤
<$E(G)=\emptyset$Æ
<ÒlabelÞchempty×
<ÒendÞexmpl×
<
<ÒvspaceÞ-1.2em×
<ÒbeginÞexmpl×ÒhspaceÞ.6em×Òrm
<¯“ëÚ÷ùÚ¢¤Úõ™‘ñÉÒrefÞnonch_ex×Ú¢þ¢þôŠÚð¤éÚ÷õ‘þ©Ú¢¢ùÚª¢ùÚ¢¤
<ªîñÉÒrefÞlc_exmpl×¾’½ŠÚ$2$Å÷—¡‘’•£þ¤Ú÷þ¨–ÚøÚ¥ÚþöÉ¤øÚä¢¢Ú¤÷ðüÚóþ¨—üÚö
<¢¨–îôÚ$3$Ú¨–ÆÚ¥Ú¯¤êüÚõü—øöÚ÷ª‘öÚ¢¢ÚîùÚþöÚð¤éÚ$3$Å÷—¡‘’•£þ¤Ú¨–Æ
<“¤ýÚþöÚõ÷àø¤Úê¤­Úî÷þ¢Ú$L$ÚþíÚ$3$Åóþ¨–¢ûüÚ“ùÚ¤»¨ú‘ýÚþöÚð¤éÚ“‘ª¢Úø
<¤÷ðú‘ýÚ$c(a)$ÚøÚ$c(b)$Ú¤Ú“ùÚ—¤—þ’Ú¥Ú$L(a)$ÚøÚ$L(b)$Ú“¤ð¥þ÷þ¢ÆÚŸ‘ñÚ“‘Ú—ø›ù
<“ùÚþöÚîùÚûõùÚóþ¨—ú‘Ú¨ùÚä®øþ÷¢ŠÚ“¤ýÚ$i=1,2$Ú¤÷ðú‘ý
<$c(u_i)\in L(u_i)\setminus \{c(a),c(b)\}$Úø
<$c(v_i)\in L(v_i)\setminus \{c(a),c(b)\}$Úø›ø¢Ú¢¤÷¢ÆÚ“ùÉþöÉ—¤—þ’Úþí
<$L$Å¤÷ïõþ¥ýÉ$c$Ú“¤ýÚð¤éÚªîñÉÒrefÞlc_exmpl×¾’½Ú“ùÚ¢¨–Úõüþ¢Æ
<ÒlabelÞt2222_ch×
<ÒendÞexmpl×
<
<ÒbeginÞrem×ÒhspaceÞ.6em×Þ
<õª‘“ùÚõ™‘ñÚ“‘òÚõü—øöÚ÷ª‘öÚ¢¢Úû¤Ú$\theta_{r_1,\ldots,r_p}$Úð¤êü
<$3$Å÷—¡‘’•£þ¤Ú¨–ÆÚþ‘¢ø¤ýÚõüªø¢Ú$\theta_{r_1,\ldots,r_p}$Úð¤êüÚ¨–Úîù
<¥Ú$p$Úõ¨þ¤Úõ›¥ýÚþ‘óüÚ“ùÚ¯øóú‘ýÚ$r_1,\ldots, r_p$Ú“þöÚ¢øÚ¤»§Ú¾™‘“–½
<$u$ÚøÚ$v$Ú—ªîþñÚª¢ùÚ¨–ÆÚ“ùÚä÷øöÚõ™‘ñÚ$\theta_{1,2,2}$Ú¢¤
<ªîñÉÒrefÞlc_exmpl×¾óé½ŠÚøÚ$\theta_{2,2,2,2}$Ú¢¤ÚªîñÉÒrefÞlc_exmpl×¾’½
<÷õ‘þ©Ú¢¢ùÚª¢ù÷¢Æ
<×ÒendÞrem×
<
<¢¤Ú¢õùÚþöÚê¬ñÚð¥¤ùû‘þüÚ¢¤“‘¤ùÚøþ¦ðþú‘ýÚä¢¢Ú¤÷ðüÚóþ¨—üÚ“þ‘öÚøÚ™‘“–
<õüî÷þôÆ
<
<ÒsectionÞ÷—¡‘’•£þ¤ýÚð¤êú‘ýÚ¡‘«×
<·
<ð¤Ú“ùÚû¤Ú¤»§Úð¤éÚ$G$Úóþ¨–Ú$\{1,2,\ldots,\ch(G)\}$Ú¤Ú÷¨“–Ú¢ûþôŠÚû¤
<¤÷ïõþ¥ýÚóþ¨—üÚ$G$Ú¥ÚþöÚóþ¨–¢ûüÚ¢¤ÚøìâÚþíÚ$\ch(G)$Å¤÷ïõþ¥ýÚ$G$Ú¨–ÚøÚ¥
<—ã¤þéÚä¢¢Ú¤÷ðüÚóþ¨—üÚõü¢÷þôÚîùÚ÷þöÚ¤÷ïõþ¥ýÚóþ¨—üÚø›ø¢Ú¢¤¢ÆÚ¥Úþö¤ø
<“¤ýÚû¤Úð¤éÚ$G$Ú¢¤þô
>$$\Chi(G)\le\ch(G).$$
>\vspace{-\baselineskip}
<
<•¤¨ªüÚîùÚ“ùÚ¯ø¤Ú¯“þãüÚõ¯¤žÚõüªø¢ÚþöÚ¨–ÚîùÚ¢¤ÚùÚ¬ø¤–ÚþöÚ÷‘õ¨‘øýÚîþ¢
<õüªø¢ÚøÚþ‘ÚŸ‘ó—ú‘þüÚø›ø¢Ú¢¤¢ÚîùÚ—¨‘øýÚ¤ Ú¢û¢ŒÚð¥¤ùÚ¥þ¤Ú÷ª‘öÚõü¢û¢Úîù
<õì¢¤Ú$\ch(G)-\Chi(G)$Úõü—ø÷¢Ú“ùÚ¢ó¡øùÚ“¥¤ïÚªø¢Æ
<
<ÒbeginÞprop×ÒciteÞerdos×ÒhspaceÞ.6em×
<ð¤Ú$k\ge 1$ÚøÚ$r={2k-1\choose k}$ŠÚ÷ð‘ùÚ$K_{r,r}$Úð¤êüÚ$k$Å÷—¡‘’•£þ¤
<÷þ¨–Æ
<ÒlabelÞbip_non_k_ch×
<ÒendÞprop×
<
<ÒbeginÞproof×
<ê¤­Úî÷þ¢Ú¥þ¤õ›õøäùû‘ýÚ$k$Éä®øýÚõ›õøäùÚ$A=\{1,\ldots,2k-1\}$Ú¤Ú“‘
<$L_1$ÚŠÚ$\cdots$ÚŠÚ$L_r$Ú÷õ‘þ©Ú¢ûþôÆÚ“ùÚ$i$É²õþöÚ¤»§Ú¢¤Úû¤Ú“¡©Ú$K_{r,r}$Š
<óþ¨–Ú$L_i$Ú¤Ú÷¨“–Ú¢ûþ¢Ú¾$1\le i\le r$½ÆÚð¤Ú$K_{r,r}$Ú¥Úþö
<$k$Åóþ¨–¢ûüÚ“ùÚ¤»¨ú‘þ©ÚþíÚ¤÷ïõþ¥ýÚóþ¨—üÚ¢ª—ùÚ“‘ª¢ŠÚøÚ$X$ÚøÚ$Y$
<“ùÉ—¤—þ’Úõ›õøäùÚ¤÷ðú‘ýÚ“ùÉî‘¤Ú¤ê—ùÚ¢¤Ú“¡©ÚøñÚøÚ“¡©Ú¢øôÚ$K_{r,r}$
<“‘ª÷¢ŠÚ÷ª‘öÚõü¢ûþôÚîùÚû¤ÚþíÚ¥Ú$X$ÚøÚ$Y$Ú¢¨–îôÚ$k$Éä®øÚ¢¤¢ÚøÚ“‘Ú—ø›ù
<“ùÚþöÚîùÚ$X\cap Y=\emptyset$ÚøÚ$|X\cup Y|\le|A|= 2k-1$ŠÚ“¤û‘öÚ“ù
<•‘þ‘öÚõü¤¨¢ÆÚð¤Ú$|X|\le k-1$ŠÚ÷ð‘ùÚ$A\setminus X$Ú¢¨–îôÚ$k$Éä®øÚ¢¤¢
<øÚ“÷‘“¤þöÚ÷¢þ§Ú$i$Úø›ø¢Ú¢¤¢ÚîùÚ$L_i\cap X=\emptyset$ÆÚþöÚ—÷‘ì­Ú÷ª‘ö
<õü¢û¢ÚîùÚ$|X|\ge k$ÚøÚ“ùÚ¯ø¤Úõª‘“ùÚ¢¤þôÉ$|Y|\ge k$Æ
<ÒendÞproof×
<
<ð¥¤ùÚ“‘òÚ÷ª‘öÚõü¢û¢ÚîùÚõø®øáÚ¤÷ïõþ¥ýÚóþ¨—üÚ“‘Ú¤÷ïõþ¥ýÚõãõøóüÚð¤êú‘
<—ê‘ø—ú‘ýÚ¨‘¨üÚ¢¤¢ÚøÚŸ—üÚ“¤ýÚð¤êú‘ýÚ¢ø“¡ªüÚî‘õñÚ÷þ¥Ú÷õü—øöÚ“ùÚ¨‘¢ðü
<¢¤“‘¤ùÚä¢¢Ú¤÷ðüÚóþ¨—üÚ—¬õþôÚð¤ê–Æ
<
<“¤ýÚû¤Ú$k\ge 1$ŠÚ—ã¢¢Ú¤»¨ú‘ýÚîøî—¤þöÚð¤éÚ¢ø“¡ªüÚîùÚ$k$Å÷—¡‘’•£þ¤Ú÷þ¨–
<¤Ú“ùÚ$N(2,k)$Ú÷õ‘þ©Úõü¢ûþôÆÚþîüÚ¥Úð‘õú‘þüÚîùÚõü—øöÚ¢¤Ú¤ùÚª÷‘¨‘þüÚä¢¢Ú¤÷ðü
<óþ¨—üÚð¤êú‘ýÚ¢ø“¡ªüÚ“¤¢ª–ŠÚõŸ‘¨“ùÚ$N(2,k)$Úþ‘Úþ‘ê—öÚî¤÷ú‘ýÚ¡ø’Ú“¤ýÚö
<¨–ÆÚ¢¤ÚÒciteÞerdos×Ú÷ª‘öÚ¢¢ùÚª¢ùÚ¨–ÚîùÚ$N(2,1)=2$ŠÚ$N(2,2)=6$ŠÚø
<$12\le N(2,3)\le 14$ÆÚì®þùÚ¥þ¤Úî¤÷ú‘þüÚ“¤ýÚ$N(2,k)$Ú“ùÚ¥ýÚû¤Ú$k$Ú“ùÚ¢¨–
<õü¢û¢ÚøÚõ‘ÚöÚ¤Ú“¢øöÚ“¤û‘öÚõüø¤þôÆ
<
<ÒbeginÞthm×ÒciteÞerdos×ÒhspaceÞ.6em×
<“¤ýÚû¤Ú$k\ge 2$Ú¢¤þô
>$$2^{k-1}+2<N(2,k)<k^2 2^{k+2}.$$
>\vspace{-\baselineskip}
<ÒlabelÞN2k×
<ÒendÞthm×
<
<“ùÚ›¥Úð¤êú‘ýÚ¢ø“¡ªüÚ¤¢ùÚõúôÚ¢þð¤ýÚ¥Úð¤êú‘ÚîùÚõü—øöÚõ¨ŽóùÚ÷—¡‘’•£þ¤ýÚ¤
<“ùÚ¯ø¤Ú¡‘«Ú“¤ýÚ÷ú‘Úõ¯¤žÚî¤¢ŠÚð¤êú‘ýÚõ¨¯žÚû¨—÷¢ÆÚ¢øÚŸ¢§ÚøÚ•¤¨©Ú¥þ¤
<¢¤ÉÒciteÞerdos×Ú¢¤“‘¤ùÚä¢¢Ú¤÷ðüÚóþ¨—üÚð¤êú‘ýÚõ¨¯žÒindexÞð¤éÚõ¨¯ž×Úõ¯¤ž
<ª¢ùÚ¨–ÆÚ›ø“ú‘ý
<þöÚ¨ùÚ÷ª‘öÚõü¢û÷¢Úä¢¢Ú¤÷ðüÚóþ¨—üÚð¤êú‘ýÚõ¨¯žÚ÷õü—ø÷¢Ú“ùÚ¢ó¡øùÚ“¥¤ïÚ“‘ª¢Æ
<
<ÒbeginÞconj×ÒciteÞerdos×ÒhspaceÞ.6em×
<û¤Úð¤éÚõ¨¯žÚ$5$Å÷—¡‘’•£þ¤Ú¨–Æ
<ÒlabelÞ5chconj×
<ÒendÞconj×
<
<ÒvspaceÞ-1.2em×
<ÒbeginÞconj×ÒciteÞerdos×ÒhspaceÞ.6em×
<ð¤éÚõ¨¯ŸüÚø›ø¢Ú¢¤¢ÚîùÚ$4$Å÷—¡‘’•£þ¤Ú÷þ¨–Æ
<ÒlabelÞ4chconj×
<ÒendÞconj×
<
<ÒvspaceÞ-1.2em×
<ÒbeginÞques×ÒciteÞerdos×ÒhspaceÞ.6em×
<þ‘ÚûþœÚð¤éÚõ¨¯žÚ¢ø“¡ªüÚø›ø¢Ú¢¤¢ÚîùÚ$3$Å÷—¡‘’•£þ¤Ú÷“‘ª¢Œ
<ÒlabelÞbip3chques×
<ÒendÞques×
<
<¢¤¨—üÚŸ¢§ÉÒrefÞ5chconj×Ú—ø¨ÁÚ—øõ‘¨±öÒindexÞ—øõ‘¨±ö×Ú“‘Ú“¤û‘÷üÚ¥þ“‘ÚîùÚö
<¤Ú¢¤Ú¢õùÚþöÚê¬ñÚõüø¤þôŠÚ¢¤ÉÒciteÞthomassen×Ú™‘“–Úª¢ùÚ¨–Æ
<øøþ–ÒindexÞøøþ–×Ú¢¤ÉÒciteÞÐvoigtÐ×Ú¢¤¨—üÚŸ¢§ÉÒrefÞ4chconj×Ú¤Ú“‘Ú¤Žù
<þíÚõ™‘ñÚ$238$Ú¤»¨üÚ÷ª‘öÚ¢¢ùÚøÚõþ¤¥¡‘÷üÒindexÞõþ¤¥¡‘÷ü×
<¢¤ÉÒciteÞÐmirzakhaniÐ×Úõ™‘ñÚ¢þð¤ýÚ“‘Ú$63$Ú¤»§Ú¢¢ùÚ¨–Æ
<Ÿ¢¨üÚõ÷¨ø’Ú“ùÚþ÷¨öÒfootnoteÞT.\,R.~Jensen×ÒindexÞþ÷¨ö×Úø
<ª—þ“þ—¥ÒfootnoteÞM.~Stiebitz×ÒindexÞª—þ“þ—¥×
<ø›ø¢Ú¢¤¢ÚîùÚ¢¤Ú¤¨—‘ýÚŸ¢¨ú‘ýÉÒrefÞ5chconj×ÚøÉÒrefÞ4chconj×Ú¢ä‘Úõüî÷¢Úû¤
<ð¤éÚõ¨¯žÚ$3$Å¤÷ï•£þ¤ŠÚ$4$Å÷—¡‘’•£þ¤Ú¨–ÆÚøóüÚð¤éÚ¤ŽùÚª¢ù
<¢¤ÉÒciteÞÐmirzakhaniÐ×Ú¢¤ýÚä¢¢Ú¤÷ðüÚ$3$Ú¨–ÚøÚ¥ÚþöÉ¤øÚäòøùÚ“¤Ú•‘¨ Ú“ù
<Ÿ¢§ÉÒrefÞ4chconj×ŠÚŸ¢§Úþ÷¨öÚøÚª—þ“þ—¥Ú¤Ú÷þ¥Ú¤¢Úõüî÷¢ÆÚûõ÷þö
<ó²öÒindexÞó²ö×ÚøÚ—‘¤¨üÒindexÞ—‘¤¨ü×Ú¢¤ÉÒciteÞÐalontarsiÐ×Ú“ù
<•¤¨©ÉÒrefÞbip3chques×Ú•‘¨ Ú¢¢ù÷¢ÚîùÚ¢¤Ú•üÚõüþ¢Æ
<
<ÒbeginÞthm×ÒciteÞalontarsi×ÒhspaceÞ.6em×
<û¤Úð¤éÚõ¨¯žÚ¢ø“¡ªüÚ$3$Å÷—¡‘’•£þ¤Ú¨–Æ
<ÒlabelÞbip3ch×
<ÒendÞthm×
<
<þöÚì®þùÚ“ùÚä÷øöÚ÷—þ›ùýÚ¥ÚþíÚì®þùÚ“¨þ‘¤Úîóü—¤Ú¢¤ÉÒciteÞalontarsi×Úõ¢ùŠ
<îùÚ“‘Ú“ú¤ùðþ¤ýÚ¥Ú“¥¤û‘ýÚ›“¤Ú÷¢›õóùþú‘Ú“ùÚ¥þ“‘þüÚ™‘“–Úª¢ùÚ¨–ÚøÚõ‘
<“ùÚ¢óþñÚ¯øò÷üÚª¢öÚõ¯ó’Ú¥Úø¤¢öÚþöÚ“¤û‘öÚªôÉ•øªüÚõüî÷þôÚøÚ¡ø÷÷¢ù
<äòìõ÷¢Ú¤Ú“ùÉÒciteÞalon×Ú¤›øáÚõü¢ûþôÆ
<
<ÒsectionÞ¨‘¡—‘¤Úð¤êú‘ýÚ$k$Å÷—¡‘’•£þ¤×
<·
<¤¢þ©ŠÚ¤ø“þöŠÚøÚ—þóø¤ÒindexÞ¤¢þ©×ÒindexÞ¤ø“þö×ÒindexÞ—þóø¤×Ú¢¤ÉÒciteÞerdos×
<¨‘¡—‘¤Úð¤êú‘ýÚ$2$Å÷—¡‘’•£þ¤Ú¤Ú“ùÚ¯ø¤Úî‘õñÚª÷‘¨‘þüÚî¤¢ù÷¢Æ
<þöÚ¤¢ù“÷¢ýÚ¢¤Úì®þùÚ“ã¢Úõ¢ùÚøóüÚ•þ©Ú¥ÚöÚ“ùÚþíÚ—ã¤þéÚ÷þ‘¥Ú¢¤þôÆ
<ê¤­Úî÷þ¢Ú$G$Úð¤êüÚûõ“÷¢Ú“‘ª¢ÆÚð¤Ú$G$Ú¤»¨üÚ¥Ú¢¤›ùÚþíÚ¢ª—ùÚ“‘ª¢ŠÚöÚ¤»§
<¤ÚŸ£éÚõüî÷þôÚøÚþöÚî‘¤Ú¤Ú—‘Ú›‘þüÚîùÚûþœÚ¤»¨üÚ“‘Ú¢¤›ùÚþíÚ¢¤Úð¤éÚ“‘ìü
<÷õ‘÷¢Ú—î¤¤Úõüî÷þôÆÚ¥þ¤ð¤éÚ¾óì‘þü½Ú$G_0$Ú¥Ú$G$ÚîùÚ“ùÚþöÚ¤ø©Ú“ùÚ¢¨–
<õüþ¢Ú¤ÚÞÒsiahÚû¨—ù×ýÉ$G$ÒindexÞû¨—ù×Úõü÷‘õþôÆÚ“ùÚ¨‘¢ðüÚ¢þ¢ùÚõüªø¢Úîù
<$G_0$Ú¥Ú—¤—þ’ÚŸ£éÚ¤»¨ú‘ýÚ¢¤›ùÚþíÚõ¨—ìñÚ¨–Æ
<
<ÒbeginÞthm×ÒciteÞerdos×ÒhspaceÞ.6em×
<þíÚð¤éÚûõ“÷¢Ú$2$Å÷—¡‘’•£þ¤Ú¨–ŠÚð¤ÚøÚ—÷ú‘Úð¤Úû¨—ùÚöÚþíÚ¤»§Ú—÷ú‘Š
<þíÚ¢ø¤Ú¥øšŠÚþ‘Ú$\theta_{2,2,2r}$Ú“ùÚ¥ýÚþíÚ$1\le r$Ú“‘ª¢Æ
<ÒlabelÞ2choose×
<ÒendÞthm×
<
<¢¤Úþ÷›‘Ú“ùÚ¢óþñÚ¯øò÷üÚ“ø¢öÚ“¤û‘öÚì®þùÉÒrefÞ2choose×Ú¥Ú÷ìñÚöÚ¡ø¢¢¤ý
<õüî÷þôÚøÚ¡ø÷÷¢ùÚäòìõ÷¢Ú¤Ú“ùÚÒciteÞerdos×Ú¤›øáÚõü¢ûþôÆ
<
<þîüÚ¥Úì®þùû‘ýÚõúôÚ÷à¤þùÚ¤÷ïõþ¥ýÚð¤êú‘Úì®þùýÚ¥
<û‘þø©ÒfootnoteÞG.~Haj\'os×ÒindexÞû‘þø©×ÒindexÞì®þùÚû‘þø©×Ú¨–ÚîùÚ“¤ý
<û¤É$k$ŠÚûõùÚð¤êú‘ýÚ“‘Úä¢¢Ú¤÷ðüÚ“¥¤ð—¤Ú¥Ú$k$Ú¤Ú“ùÚ¢¨–Úõü¢û¢ÆÚ¢¤Ú¢õù
<þöÚ“¡©Úì®þùýÚõª‘“ùÚì®þùÚû‘þø©Ú¤Ú“¤ýÚ¤÷ïõþ¥ýÚóþ¨—üÚ“þ‘öÚõüî÷þôÆ
<
<÷¡¨—þöÚð¤êüÚîùÚä¢¢Ú¤÷ðüÚ“þ©Ú¥Ú$k$Ú¢¤¢Úð¤éÚî‘õñÚ$k+1$Ú¤»¨üÚ¨–Æ
<û‘þø©Ú—“¢þóú‘þüÚ¤øýÚð¤êú‘Ú“¢áÚî¤¢ÚîùÚ“‘Ú÷ú‘Úõü—øöÚûõùÚð¤êú‘ýÚ“‘
<ä¢¢Ú¤÷ðüÚ“þ©Ú¥Ú$k$Ú¤Ú¥Úð¤éÚ$K_{k+1}$Ú“ùÚ¢¨–Úø¤¢ÆÚ—“¢þóú‘ýÚøýÚª‘õñ
<¨ùÚäõóð¤Ú¥þ¤Ú¨–Æ
<·
<ÒbeginÞitemize×
<ÒitemÓ(i)ÑÚ“ùÚð¤éÚ¢¢ùÚª¢ùÚþíÚ¤»§Úþ‘ÚþíÚþ‘ñÚ®‘êùÚõüÚî÷þôÆ
<ÒitemÓ(ii)ÑÚð¤Ú$G_1$ÚøÚ$G_2$Ú¢øÚð¤éÚõ›¥ýÚ¤»¨üÚøÚ$u_1v_1$ÚøÚ$u_2v_2$
<“ùÚ—¤—þ’Úþ‘óú‘þüÚ¥Ú$G_1$ÚøÚ$G_2$Ú“‘ª÷¢ŠÚð¤éÚ$G$Ú¤Ú¥Ú$G_1+G_2$Ú“ù
<þöÚ—¤—þ’Úõü¨‘¥þôÚîùÚ$u_1$ÚøÚ$u_2$Ú¤Ú“¤ÚûôÚõ÷¯“ëÚî¤¢ùŠÚþ‘óú‘ýÚ$u_1v_1$
<øÚ$u_2v_2$Ú¤ÚŸ£éŠÚøÚþ‘ñÚ$v_1v_2$Ú¤Ú®‘êùÚõüî÷þôÆ
<¾ªîñÉÒrefÞhajos_fig×Ú¤Ú““þ÷þ¢Æ½
<·
<ÒbeginÞfigure×ÓÐhtÐÑ
<Òcentering
<Òenglish
<·ÒinputÞhajos.pic×
>\special{em:linewidth 0.4pt}
>\unitlength .8mm
>\linethickness{0.4pt}
>\begin{picture}(150.89,35.89)
>\put(9.89,-0.11){\circle*{2.00}}
>\put(30.22,-0.11){\circle*{2.00}}
>\put(-0.11,19.89){\circle*{2.00}}
>\put(39.89,19.89){\circle*{2.00}}
>\put(19.89,34.89){\circle*{2.00}}
>\put(19.89,14.89){\circle*{2.00}}
>\emline{9.89}{-0.11}{1}{29.89}{-0.11}{2}
>\emline{29.89}{-0.11}{3}{19.89}{14.89}{4}
>\emline{19.89}{14.89}{5}{9.89}{-0.11}{6}
>\emline{9.89}{-0.11}{7}{-0.11}{19.89}{8}
>\emline{-0.11}{19.89}{9}{19.89}{34.89}{10}
>\emline{19.89}{34.89}{11}{19.89}{14.89}{12}
>\emline{19.89}{14.89}{13}{39.89}{19.89}{14}
>\emline{39.89}{19.89}{15}{29.89}{-0.11}{16}
>\emline{39.89}{19.89}{17}{19.89}{34.89}{18}
>\emline{19.89}{14.89}{19}{-0.11}{19.89}{20}
>\put(49.89,19.89){\circle*{2.00}}
>\put(69.89,19.89){\circle*{2.00}}
>\put(59.89,-0.11){\circle*{2.00}}
>\put(59.89,14.89){\circle*{2.00}}
>\emline{49.89}{19.89}{21}{69.89}{19.89}{22}
>\emline{69.89}{19.89}{23}{59.89}{-0.11}{24}
>\emline{59.89}{-0.11}{25}{49.89}{19.89}{26}
>\emline{49.89}{19.89}{27}{59.89}{14.89}{28}
>\emline{59.89}{14.89}{29}{69.89}{19.89}{30}
>\emline{59.89}{14.89}{31}{59.89}{-0.11}{32}
>\put(99.89,-0.11){\circle*{2.00}}
>\put(120.22,-0.11){\circle*{2.00}}
>\put(89.89,19.89){\circle*{2.00}}
>\put(129.89,19.89){\circle*{2.00}}
>\put(109.89,34.89){\circle*{2.00}}
>\put(109.89,14.89){\circle*{2.00}}
>\emline{99.89}{-0.11}{33}{119.89}{-0.11}{34}
>\emline{119.89}{-0.11}{35}{109.89}{14.89}{36}
>\emline{109.89}{14.89}{37}{99.89}{-0.11}{38}
>\emline{99.89}{-0.11}{39}{89.89}{19.89}{40}
>\emline{89.89}{19.89}{41}{109.89}{34.89}{42}
>\emline{109.89}{34.89}{43}{109.89}{14.89}{44}
>\emline{109.89}{14.89}{45}{129.89}{19.89}{46}
>\emline{129.89}{19.89}{47}{109.89}{34.89}{48}
>\emline{109.89}{14.89}{49}{89.89}{19.89}{50}
>\put(149.89,19.56){\circle*{2.00}}
>\put(140.09,0.06){\circle*{2.00}}
>\put(139.89,14.56){\circle*{2.00}}
>\emline{129.89}{19.56}{51}{149.89}{19.56}{52}
>\emline{149.89}{19.56}{53}{139.89}{-0.44}{54}
>\emline{129.89}{19.56}{55}{139.89}{14.56}{56}
>\emline{139.89}{14.56}{57}{149.89}{19.56}{58}
>\emline{139.89}{14.56}{59}{139.89}{-0.44}{60}
>\emline{120.22}{-0.11}{61}{139.89}{-0.11}{62}
>\put(41.00,22.67){\makebox(0,0)[cc]{$u_1$}}
>\put(50.67,22.67){\makebox(0,0)[cc]{$u_2$}}
>\put(33.67,1.00){\makebox(0,0)[cc]{$v_1$}}
>\put(56.67,1.00){\makebox(0,0)[cc]{$v_2$}}
>\bezier{70}(72.00,10.83)(76.00,9.33)(78.83,12.33)
>\bezier{70}(78.83,12.33)(81.50,14.67)(83.67,12.83)
>\emline{83.33}{13.00}{91}{81.67}{13.00}{92}
>\emline{83.50}{13.00}{93}{82.33}{14.33}{94}
>\put(120.00,-3.00){\makebox(0,0)[cc]{$v_1$}}
>\put(140.00,-3.00){\makebox(0,0)[cc]{$v_2$}}
>\put(130.00,22.00){\makebox(0,0)[lb]{$u_1(u_2)$}}
>\end{picture}
<Òfarsi
<ÒcaptionÞäõóð¤Ú¢øôÚû‘þø©×
<ÒlabelÞhajos_fig×
<ÒendÞfigure×
<ÒenglishÒfarsi
<·
<ÒitemÓ(iii)ÑÚ¢¤Úð¤éÚ¢¢ùÚª¢ùÚ¢øÚ¤»§Úõ¨—ìñÚ¤Ú“¤ÚûôÚõ÷¯“ëÚõüî÷þôÆ
<ÒendÞitemize×
<
<ì®þùÚîò¨þíÚû‘þø©Ú“ùÚ¬ø¤–Ú¥þ¤Ú¨–Æ
<
<ÒbeginÞthm×ÒciteÞhajos×ÒhspaceÞ.6em×
<û¤Úð¤éÚ“‘Úä¢¢Ú¤÷ðüÚ“þ©Ú¥Ú$k$Ú¤Úõü—øöÚ“‘Ú¢÷“‘óùýÚ$)$õ—÷‘ûü$($Ú¥
<äõóð¤û‘ýÚ(i)ŠÚ(ii)ŠÚøÚ(iii)Ú¥Úð¤éÚ$K_{k+1}$Ú“ùÚ¢¨–Úø¤¢Æ
<ÒendÞthm×
<
<“¤ýÚ“þ‘öÚì®þùýÚõª‘“ùÚ“‘Úì®þùÚû‘þø©Ú“¤ýÚ¤÷ïõþ¥ýÚóþ¨—üŠÚäõóð¤Ú(iii)
<¤Ú“‘Úäõóð¤Ú¢þð¤ýÚîùÚöÚ¤É(iii$'$)Úõü÷‘õþôÚ›‘þð¥þöÚõüî÷þôÆ
<·
<ÒbeginÞitemize×
<ÒitemÓ(iii$'$)ÑÚê¤­Úî÷þ¢Ú$G$Úð¤êüÚ“‘Úä¢¢Ú¤÷ðüÚóþ¨—üÚ“þ©Ú¥Ú$k$ÚøÚ$L$Úþí
<$k$Åóþ¨–¢ûüÚ“ùÚ¤»¨ú‘ýÚ$G$Ú“‘ª¢ÚîùÚ$G$ÚûþœÚ$L$Å¤÷ïõþ¥ýÚ÷¢¤¢ÆÚð¤Ú$u$ÚøÚ$v$
<¢øÚ¤»§Ú$G$Ú“‘ª÷¢Ú“ùÚ¯ø¤ýÚîùÚ$L(u)=L(v)$ŠÚþöÚ¢øÚ¤»§Ú¤Ú“¤ÚûôÚõ÷¯“ëÚî÷þ¢Æ
<ÒendÞitemize×
<
<ð¤Ú${\cal G}_k$Úõ›õøäùÚûõùÚð¤êú‘ýÚ“‘Úä¢¢Ú¤÷ðüÚóþ¨—üÚ“þ©Ú¥Ú$k$Ú“‘ª¢ŠÚ“ù
<¨‘¢ðüÚ¢þ¢ùÚõüªø¢ÚîùÚ${\cal G}_k$Ú—Ÿ–Úäõóð¤û‘ýÚ(i)ÚøÚ(iii$'$)Ú“¨—ùÚ¨–Æ
<ûõ÷þöÚ¢¤ÚóôÚ¥þ¤Úõü“þ÷þôÚîùÚ${\cal G}_k$Ú—Ÿ–Úäõóð¤Ú(ii)Ú÷þ¥Ú“¨—ùÚ¨–Æ
<
<ÒbeginÞlem×ÒciteÞgravier×ÒhspaceÞ.6em×
<õ›õøäùÚ${\cal G}_k$Ú—Ÿ–Úäõóð¤Ú(ii)Ú“¨—ùÚ¨–Æ
<ÒlabelÞhaj2closed×
<ÒendÞlem×
<
<ÒbeginÞproof×
<õ‘Úûõ‘öÚ÷õ‘¢û‘þüÚ¤ÚîùÚ¢¤Ú“þ‘öÚ¬ø¤–Úäõóð¤É(ii)Úõ¢Ú“ùÉî‘¤Úõü“¤þôÆÚê¤­
<î÷þ¢Ú$G_1,G_2\in{\cal G}_k$ÚøÚð¤éÚŸ‘¬ñÚ¥Ú÷›‘ôÚäõóð¤É(ii)Ú¤Ú$G$
<“÷‘õþ¢ÆÚ•§Ú“¤ýÚ$i=1,2$ŠÚÒÚ$k$Åóþ¨–¢ûüÚ$L_i$Ú“ùÚ¤»¨ú‘ýÚ$G_i$Úø›ø¢Ú¢¤¢
<îùÚ$G_i$ÚûþœÚ$L_i$Å¤÷ïõþ¥ýÚ÷¢¤¢ÆÚ“¢øöÚî‘¨—ùÚª¢öÚ¥Úîóþ–ŠÚõü—ø÷þô
<ê¤­Úî÷þôÚ$L_1(u_1)=L_2(u_2)$ÆÚŸ‘ñÚ$k$Åóþ¨–¢ûüÚ$L$Ú“ùÚ¤»¨ú‘ýÚ$G$Ú¤
<÷‘öÚ—ã¤þéÚõüî÷þôÚîùÚ“¤ýÚ$i=1,2$ŠÚ$L|_{V(G_i)}=L_i$ÆÚð¤Ú$G$Úþí
<$L$Å¤÷ïõþ¥ýÚ$c$Ú¢ª—ùÚ“‘ª¢ŠÚ“‘Ú—ø›ùÚ“ùÚþöÚîùÚ¢¤Ú$G$Ú¢øÚ¤»§
<$v_1$ÚøÚ$v_2$Ú“‘ÚûôÚõ›‘ø¤÷¢ŠÚ¢¤þôÚ$c(v_1)\not=c(v_2)$ÆÚ•§Ú$i$Úø›ø¢
<¢¤¢ÚîùÚ$c(v_i)\not=c(u)$Ú¾$u$Ú¤»§ÚŸ‘¬ñÚ¥ÚþîüÚî¤¢öÚ$u_1$ÚøÚ$u_2$
<¨–½ÆÚ“ùÉ¤øª÷üÚ$c|_{V(G_i)}$ÚþíÉ$L_i$Å¤÷ïõþ¥ýÚ“¤ýÚ$G_i$Ú¨–ÚîùÚ“‘
<ê¤­Ú›ø¤Ú¢¤Ú÷õüþ¢ÆÚ•§Ú$G$ÚûþœÚ$L$Å¤÷ïõþ¥ýÚ÷¢¤¢ÚøÚ¥ÉþöÉ¤ø
<$G\in{\cal G}_k$Æ
<ÒendÞproof×
<
<¥Úð¥¤ùÉÒrefÞbip_non_k_ch×Úõü¢÷þôÚ“¤ýÚû¤Ú$k$Úä¢¢û‘ýÚ$r$ÚøÚ$s$
<ø›ø¢Ú¢¤¢ÚîùÚ$K_{r,s}\in{\cal G}_k$ÆÚ¢¤Úì®þùÚõª‘“ùÚû‘þø©Ú¢¤Úøìâ
<÷ª‘öÚõü¢ûþôÚîùÚûõùÚÚä®‘ýÚ${\cal G}_k$Ú¥ÚþíÚ$K_{r,s}$Ú“ùÚ¢¨–Úõüþ÷¢Æ
<
<ÒbeginÞthm×ÒciteÞgravier×ÒhspaceÞ.6em×
<ð¤Ú$K_{r,s}$ŠÚ$k$Å÷—¡‘’•£þ¤Ú÷“‘ª¢ŠÚû¤Úð¤éÚ“‘Úä¢¢Ú¤÷ðüÚóþ¨—ü
<“þ©Ú¥Ú$k$Ú¤Úõü—øöÚ“‘Ú¢÷“‘óùýÚ$)$õ—÷‘ûü$($Ú¥Úäõóð¤û‘ýÚ(i)ŠÚ(ii)Š
<øÚ(iii$'$)Ú¥Úð¤éÚ$K_{r,s}$Ú“ùÚ¢¨–Úø¤¢Æ
<ÒendÞthm×
<
<ì®þùÚ“‘òÚ“ùÚ¨‘¢ðüÚ¥Ú¢øÚóôÚ¥þ¤Ú÷—þ›ùÚõüªø¢Æ
<
<ÒbeginÞlem×ÒciteÞgravier×ÒhspaceÞ.6em×
<û¤Úä®øÚ${\cal G}_k$Ú¤Úõü—øöÚ“‘Ú¢÷“‘óùýÚ$)$õ—÷‘ûü$($Ú¥Úäõóð¤û‘ýÚ(i)ŠÚ(ii)Š
<øÚ(iii$'$)Ú¥Ú—ã¢¢ýÚð¤éÚ÷¢“¡ªüÚî‘õñÚä®øÚ${\cal G}_k$Ú“ùÚ¢¨–Úø¤¢Æ
<ÒendÞlem×
<
<ÒbeginÞproof×
<ê¤­Úî÷þ¢Ú$G\in{\cal G}_k$Ú¤Ú“—øöÚ“‘Ú¢÷“‘óùýÚõ—÷‘ûüÚ¥Úäõóð¤û‘ý
<(i)ŠÚ(ii)ŠÚøÚ(iii$'$)Ú¥Ú—ã¢¢ýÚð¤éÚ÷¢“¡ªüÚî‘õñÚä®øÚ${\cal G}_k$
<“ùÚ¢¨–Úø¤¢ÆÚð¤Ú$G'\in{\cal G}_k$Úª‘õñÚ$G$Ú“ùÚä÷øöÚ¥þ¤ð¤éÚóì‘þüÚ“‘ª¢Š
<¤øªöÚ¨–ÚîùÚ$G'$Ú¤Úõü—øöÚ“‘Ú÷¢“‘¤Ú™¤Úäõóð¤Ú(i)Ú¥Ú$G$Ú“ùÚ¢¨–Úø¤¢Æ
<¥Ú¯¤êüÚõü—øöÚ“‘Ú÷¢“‘¤Ú™¤Úäõóð¤Ú(i)Ú“¤Ú$G$ŠÚþíÚð¤éÚ÷¢“¡ªüÚî‘õñÚä®ø
<${\cal G}_k$Ú¤Ú“ùÚ¢¨–Úø¤¢ÆÚ•§Úð¤Úõ™‘ñÚ÷ì®üÚ“¤ýÚþöÚóôÚø›ø¢Ú¢ª—ùÚ“‘ª¢Š
<þíÚõ™‘ñÚ÷ì­Úõ‘î¨þõ‘ñÚ÷þ¥Úõü—øöÚþ‘ê–Æ
<
<ê¤­Úî÷þ¢Ú$G$ÚþíÚõ™‘ñÚ÷ì­Úõ‘î¨þõ‘ñÚ“‘ª¢ÆÚ¥Ú÷›‘ÚîùÚ$G$Ú÷¢É“¡ªüÚî‘õñ
<÷þ¨–ŠÚ¤»¨ú‘ýÚ$x$ŠÚ$y$ŠÚøÚ$z$Ú¢¤ÚöÚø›ø¢Ú¢¤÷¢ÚîùÚ$xz\not\in E(G)$ÒÚ$xy,$
<øÚ$yz\in E(G)$ÆÚð¤êú‘ýÚ$G_1=G+xy$ÚøÚ$G_2=G+xz$Ú¤Ú¢¤Ú÷à¤Úõüðþ¤þôÚø
<“¤ýÚ—õ‘þ¥Ú“þöÚ¤»¨ú‘ýÚ÷ú‘ŠÚ“¤ýÚû¤Ú¤»§Ú$v$Ú¥Ú$G$ŠÚ¤»§Úõ—÷‘à¤Ú“‘
<öÚ¢¤Ú$G_1$Ú¤Ú“ùÚ$v_1$ŠÚøÚ¤»§Úõ—÷‘à¤Ú“‘ÚöÚ¢¤Ú$G_2$Ú¤Ú“ùÚ$v_2$
<÷õ‘þ©Úõü¢ûþôÆÚ“‘Ú—ø›ùÚ“ùÚõ‘î¨þõ‘ñÚ“ø¢öÚ$G$ŠÚð¤êú‘ýÚ$G_1$ÚøÚ$G_2$Ú¤
<õü—øöÚ“‘Úäõóð¤û‘ýÚ(i)ŠÚ(ii)ŠÚøÚ(iii$'$)Ú¥Ú—ã¢¢ýÚð¤éÚ÷¢“¡ªüÚî‘õñ
<ä®øÚ${\cal G}_k$Ú“ùÉ¢¨–Úø¤¢ÆÚ÷ª‘öÚõü¢ûþôÚ$G$Ú¤Úõü—øöÚ“‘Úäõóð¤û‘ý
<(ii)ÚøÚ(iii$'$)Ú¥Ú$G_1$ÚøÚ$G_2$Ú“ùÉ¢¨–Úø¤¢ÆÚþöÚ“‘Úõ™‘ñÚ÷ì­Ú“ø¢ö
<$G$Ú›ø¤Ú¢¤Ú÷õüþ¢ÚøÚ“÷‘“¤þöÚ“¤û‘öÚ¤Úî‘õñÚõüî÷¢Æ
<
<þ‘óú‘ýÚ$x_1y_1$Ú¥Ú$G_1$ÚøÚ$x_2y_2$Ú¥Ú$G_2$Ú¤Ú¢¤Ú÷à¤Úõüðþ¤þôÚøÚð¤é
<$H$Ú¤Ú“‘Úäõóð¤Ú(ii)Ú“ùÉ¢¨–Úõüø¤þôÚ¾¤»¨ú‘ýÚ$x_1$ÚøÚ$x_2$Ú¤Úþîü
<õüî÷þô½ÆÚð¤Ú$L_0$ÚþíÚ$k$Åóþ¨–¢ûüÚ“ùÚ¤»¨ú‘ýÚ$G$Ú“‘ª¢ÚîùÚ$G$Š
<$L_0$Å¤÷ï•£þ¤Ú÷þ¨–ŠÚ$k$Åóþ¨–¢ûüÚ$L$Ú“ùÚ¤»¨ú‘ýÚ$H$Ú¤Ú“‘
<$L(v_0)=L(v_1)=L_0(v)$Ú“¤ýÚû¤Ú$v\in V(G)$ŠÚ—ã¤þéÚõüî÷þôÆÚ“‘Ú—ø›ùÚ“ù
<“¤û‘öÚóôÉÒrefÞhaj2closed×ŠÚ$H$ÚûþœÚ$L$Å¤÷ïõþ¥ýÚ÷¢¤¢ÆÚŸ‘ñÚøöÚ“¤ýÚû¤
<$v\in V(G)$ÚîùÚ$v\not=x$ŠÚÒÚÚ¢¤þôÚ$L(v_1)=L(v_2)$ŠÚÒÚÚ“‘Úäõóð¤É(iii$'$)
<¤»¨ú‘ýÚ$v_1$ÚøÚ$v_2$Ú¤Ú¢¤Ú$H$ÚÒÚþîüÚõüî÷þôÚ—‘Ú“ùÚð¤éÚ$G$Ú“¤¨þôÆ
<ÒendÞproof×
<
<ÒvspaceÞ-1.2em×
<ÒbeginÞlem×ÒciteÞgravier×ÒhspaceÞ.6em×
<û¤Úð¤éÚ÷¢“¡ªüÚî‘õñÚä®øÚ${\cal G}_k$Ú¤Úõü—øöÚ“‘Ú¢÷“‘óùýÚ$)$õ—÷‘ûü$($Ú¥
<äõóð¤û‘ýÚ(i)ÚøÚ(iii$'$)Ú¥Úû¤Úð¤éÚ¢ø“¡ªüÚî‘õñÚä®øÚ${\cal G}_k$Ú“ùÉ¢¨–
<ø¤¢Æ
<ÒendÞlem×
<
<ÒbeginÞproof×
<ê¤­Úî÷þ¢Ú$G=K_{r_1,\ldots,r_p}\in{\cal G}_k$ÚøÚ$R_1$ÚŠÚ$\cdots$ÚŠÚ$R_p$
<“¡ªú‘ýÚ$G$Ú“‘ª÷¢ÚîùÚ$|R_i|=r_i$ÆÚõü—ø÷þôÚê¤­Úî÷þôÚ$k,p\ge 2$ÆÚŸ‘ñÚð¤
<$K_{r,s}\in{\cal G}_k$ŠÚ“‘Ú“ú¤ùðþ¤ýÚ¥Úäõóð¤É(i)Ú¤»¨ú‘ÚøÚþ‘óú‘þüÚ“ù
<$G$Ú®‘êùÚõüî÷þôÚ—‘Ú“ùÚð¤éÚ$H=K_{s_1,\ldots,s_p}$Ú“‘Ú“¡ªú‘ýÚÚ$S_1$ÚŠ
<$\cdots$ÚŠÚ$S_p$Ú¾$|S_i|=s_i$½Ú“¤¨þôÚîùÚ$r_i\le s_i$ÆÚ•§Úõü—ø÷þôÚ$G$
<¤Ú¥þ¤ð¤êüÚ¥Ú$H$Ú“ðþ¤þôÚøÚê¤­Úî÷þôÚ$R_i\subset S_i$Æ
<
<Ÿ‘ñÚê¤­Úî÷þ¢Ú$G$Ú¥Ú$k$Åóþ¨–¢ûüÚ$L$Ú“ùÚ¤»¨ú‘þ©ÚûþœÚ¤÷ïõþ¥ýÚóþ¨—ü
<÷¢¤¢ÆÚ“¤ýÚû¤Ú$1\le i\le p$Ú¤»¨üÚ$v_i\in R_i$Ú“¤õüð¥þ÷þôÚøÚ“ùÚû¤
<$u\in S_i\setminus R_i$ŠÒÚÚóþ¨–Ú$L(v_i)$Ú¤Ú÷¨“–Úõü¢ûþôÆÚ¤øªöÚ¨–Úîù
<$H$Ú¥ÚþöÚóþ¨–¢ûüÚ“ùÚ¤»¨ú‘þ©ÚûþœÚ¤÷ïõþ¥ýÚóþ¨—üÚ÷¢¤¢ÆÚ•§Ú“‘
<“ú¤ùðþ¤ýÚ¥Úäõóð¤É(iii$'$)ÒÚøÚ“‘Ú—ø›ùÚ“ùÚªþøùÚóþ¨–¢ûüÚ“ùÚä®‘ý
<$S_i\setminus R_i$ŠÒÚõü—ø÷þôÚû¤Ú$u\in S_i\setminus R_i$ÒÚ¤Ú“‘Ú$v_i$
<þîüÚî÷þôÚ—‘Ú“ùÚ$G$Ú“¤¨þôÆ
<ÒendÞproof×
<
<ÒsectionÞð¤êú‘ýÚ$k$Å—“‘ûþ¢ù×
<·
<þíÚð¤éÚ¤ÚÞÒsiahÚ$k$Å—“‘ûþ¢ù×ÒfootnoteÞ$k$--degenerate×ÒindexÞ$k$Å—“‘ûþ¢ù×
<ÒindexÞ—“‘ûþ¢ù×ÚðøþþôŠÚð¤Úû¤
<¥þ¤ð¤éÚöÚ¤»¨üÚ¥Ú¢¤›ùÚŸ¢î™¤Ú$k$Ú¢ª—ùÚ“‘ª¢ÆÚ“‘Ú¨—ì¤Ú¤øýÚ—ã¢¢
<¤»¨ú‘ýÚþíÚð¤éÚ$k$Å—“‘ûþ¢ùÚõü—øöÚ¢¤¨—üÚð¥¤ùÚ¥þ¤Ú¤Ú“ùÚ¨‘¢ðüÚ÷ª‘öÚ¢¢Æ
<
<ÒbeginÞprop×ÒhspaceÞ.6em×
<û¤Úð¤éÚ$k$Å—“‘ûþ¢ùÚ$(k+1)$Å÷—¡‘’•£þ¤Ú¨–Æ
<ÒlabelÞkdeg×
<ÒendÞprop×
<
<¥ÉþöÉ¤øÚð¤Ú$G$ÚþíÚð¤éÚøÚ$k_0$Úîøî—¤þöÚä¢¢ýÚ“‘ª¢ÚîùÚ“ùÚ¥ýÚöÚ$G$Úð¤êü
<$k_0$Å—“‘ûþ¢ùÚ¨–ŠÚ÷ð‘ùÚ$\ch(G)\le k_0+1$ÆÚþöÚ÷‘õ¨‘øýÚ“¤ýÚ“¤¡üÚð¤êú‘Ú“ù
<—¨‘øýÚ—“¢þñÚõüªø¢ÆÚ“ùÚä÷øöÚ÷õø÷ùÚ“¤ýÚð¤éÚî‘õñÚ$n$É¤»¨üŠÚ$k_0=n-1$Ú•§
<$\ch(K_n)\le n$ÚøÚ¥Ú¨øýÚ¢þð¤ÚøöÚ$\Chi(K_n)=n$ŠÚ¢¤þôÚ$\ch(K_n)\ge n$Úø
<“÷‘“¤þöÚ$\ch(K_n)=n$ÆÚûõ÷þöÚ“¤ýÚû¤Ú¢¤¡–±ÒindexÞ¢¤¡–×Ú¢¨–îôÚ¢øÚ¤»¨ü
<¾$k_0=1$½ÚøÚû¤
<¢ø¤Úê¤¢Ú¾$k_0=2$½Ú“ùÚ¨‘¢ðüÚ¢þ¢ùÚõüªø¢ÚîùÚä¢¢Ú¤÷ðüÚóþ¨—üÚ“¤“¤Ú“‘Ú$k_0+1$
<¨–ÆÚøóüÚð¤êú‘þüÚ÷þ¥Úø›ø¢Ú¢¤÷¢ÚîùÚ“¤ýÚ÷ú‘Ú÷‘õ¨‘øýÚ$\ch(G)\le k_0+1$
<îþ¢Ú¨–ÆÚ“ùÚä÷øöÚ÷õø÷ùÚ“¤ýÚ¢ø¤û‘ýÚ¥øšÚ¢¤þôÚ$k_0=2$ÚøóüÚ¥
<ì®þùÉÒrefÞ2choose×Úõü¢÷þôÚîùÚ¢ø¤û‘ýÚ¥øšÚ$2$Å÷—¡‘’•£þ¤Úû¨—÷¢Æ
<
<õü¢÷þôÚð¤Ú$G$Úð¤êüÚõ¨¯žÚ“‘ª¢Ú¢¤þôÚ$\delta(G)\le 5$ÚøÚ“‘Ú—ø›ùÚ“ù
<þöÚîùÚû¤Ú¥þ¤ð¤éÚþíÚð¤éÚõ¨¯žÚ¡ø¢Úõ¨¯žÚ¨–ŠÚ•§Úû¤Úð¤éÚõ¨¯ž
<ÒindexÞð¤éÚõ¨¯ž×Ú$5$Å—“‘ûþ¢ù
<¨–ÚøÚþöÚ÷ª‘öÚõü¢û¢ÚîùÚä¢¢Ú¤÷ðüÚóþ¨—üÚð¤êú‘ýÚõ¨¯žÚŸ¢î™¤Ú$6$Ú¨–ÆÚøóü
<Ÿ¢§ÉÒrefÞ5chconj×Ú¢ä‘Úõüî÷¢ÚîùÚä¢¢Ú¤÷ðüÚóþ¨—üÚð¤êú‘ýÚõ¨¯žÚŸ¢î™¤Ú$5$Ú¨–Æ
<•§Ú¢¤Ú¬ø¤—üÚîùÚ¢¤¨—üÚþöÚŸ¢§Ú÷ª‘öÚ¢¢ùÚªø¢ŠÚ¤¢ùýÚ¢þð¤Ú¥Úð¤êú‘Ú¢¤Ú¢¨–
<¡øûþôÚ¢ª–ÚîùÚ“¤ýÚ÷ú‘Ú÷‘õ¨‘øýÚ$\ch(G)\le k_0+1$Úîþ¢Ú¨–ÆÚì®þùÚ¥þ¤
<¢¤¨—üÚŸ¢§ÉÒrefÞ5chconj×Ú¤Ú“ùÚ¨‘¢ðüÚ÷—þ›ùÚõü¢û¢Ú¾÷—þ›ùÉÒrefÞ5chthm×½Æ
<
<ÒbeginÞthm×ÒciteÞthomassen×ÒhspaceÞ.6em×
<ê¤­Úî÷þ¢Ú$G$Úð¤êüÚõ¨¯žÚøÚûõ“÷¢Ú“‘ª¢ÚîùÚõ¤¥Úû¤Úø›ùÚõ—÷‘ûüÚöÚþíÚõ™ó˜ÚøÚõ¤¥
<ø›ùÚ÷‘õ—÷‘ûüÚöÚ¢ø¤Ú$C:v_1v_2\cdots v_pv_1$Ú¨–ÆÚþíÚóþ¨–¢ûüÚ$L$Ú“ùÚ¤»¨ú‘ý
<$G$Ú¤Ú¢¤Ú÷à¤Ú“ðþ¤þ¢ÚîùÚ$|L(v_1)|=|L(v_2)|=1$ŠÚ$L(v_1)\not=L(v_2)$Š
<$|L(v_i)|=3$Ú“¤ýÚû¤Ú$3\le i\le p$ŠÚøÚ$|L(v)|=5$Ú“¤ýÚû¤
<$v\in V(G\setminus C)$Æ
<¢¤ÚþöÚ¬ø¤–Ú$G$ÚþíÚ$L$Å¤÷ïõþ¥ýÚ¢¤¢Æ
<ÒlabelÞplanarch×
<ÒendÞthm×
<
<ÒbeginÞproof×
<™“‘–Ú¤Ú“ùÚ¨—ì¤Ú¤øýÚ—ã¢¢Ú¤»¨ú‘ýÚ$G$Ú÷›‘ôÚõü¢ûþôÆÚ“‘Ú—ø›ùÚ“ùÚþöÚîù
<$p\ge 3$ŠÚ•‘þùÚ¨—ì¤Ú¤Ú¢ø¤Ú“ùÚ¯øñÚ$3$Úõüðþ¤þôÆÚ¤øªöÚ¨–ÚîùÚ¢¤ÚþöÚŸ‘ó–
<ŸîôÚ“¤ì¤¤Ú¨–ÆÚŸ‘ñÚð¤Ú$G$Úð¤êüÚ›¥Ú$C_3$Ú“ø¢ùÚøÚŸîôÚ“¤ýÚûõùÚð¤êú‘þü
<îùÚîõ—¤Ú¥Ú$n(G)$Ú¤»§Ú¢¤÷¢Ú¢¤¨–Ú“‘ª¢ŠÚ“‘Ú¢¤Ú÷à¤Úð¤ê—öÚ¢øÚŸ‘ó–Ú÷ª‘ö
<õü¢ûþôÚ$G$ÚþíÚ$L$Å¤÷ïõþ¥ýÚ¢¤¢Æ
<
<÷¡¨–Úê¤­Úî÷þ¢Ú$C$ÚþíÚø—¤Ú¢ª—ùÚ“‘ª¢ÆÚð¤ÚþöÚø—¤Úþ‘ñÚ$v_iv_j$Ú“‘ª¢ÚîùÚ$i<j$Š
<¥Úê¤­Ú¨—ì¤ÚþíÚ$L$Å¤÷ïõþ¥ýÚ“¤ýÚ¥þ¤ð¤éÚóì‘ª¢ùÚ¥Ú$G$Ú¤øýÚ¤»¨ú‘ýÚ¢ø¤
<$v_1v_2\cdots v_iv_jv_{j+1}\cdots v_pv_1$ÚøÚ¤»¨ú‘ýÚ¢¤øöÚöÚ“ùÚ¢¨–Úõüþ¢Æ
<Ÿ‘ñÚ“‘Ú™‘“–Ú÷ðùÉ¢ª—öÚ¤÷ïÚ¤»¨ú‘ýÚ$v_i$ÚøÚ$v_j$ÚøÚ“‘Ú“ú¤ùðþ¤ýÚ¥Úê¤­Ú¨—ì¤
<þíÚ$L$Å¤÷ïõþ¥ýÚ“¤ýÚ¥þ¤ð¤éÚóì‘ª¢ùÚ¥Ú$G$Ú¤øýÚ¤»¨ú‘ýÚ¢ø¤
<$v_iv_{i+1}\cdots v_jv_i$ÚøÚ¤»¨ú‘ýÚ¢¤øöÚöÚ“ùÚ¢¨–Úõüþ¢ÆÚ“‘Ú—ø›ùÚ“ùÚþö
<îùÚ¢øÚ¥þ¤ð¤éÚóì‘þüÚõ¥“ø¤Ú—÷ú‘Ú¢¤Ú¢øÚ¤»§Ú$v_i$ÚøÚ$v_j$Úª—¤íÚ¢¤÷¢ŠÚ“ù
<þíÚ$L$Å¤÷ïõþ¥ýÚ“¤ýÚ$G$Úõü¤¨þôÆ
<
<Ÿ‘ñÚê¤­Úî÷þ¢Ú$C$ÚþíÚ¢ø¤Ú“¢øöÚø—¤Ú“‘ª¢ÆÚ“¢øöÚî‘¨—ùÚª¢öÚ¥Úîóþ–Úê¤­Úõüî÷þô
<$L(v_1)=\{1\}$ÚøÚ$L(v_2)=\{2\}$ÆÚûõ÷þöÚ$x$ÚøÚ$y$Ú¤Ú¢øÚ¤÷ïÚõ—õ‘þ¥Ú¢¤
<$L(v_p)\setminus\{1\}$Ú“ðþ¤þ¢ÚøÚê¤­Úî÷þ¢Ú$v_1$ŠÚ$w_1$ŠÚ$\ldots$ŠÚ$w_q$ŠÚø
<${v_p}_{-1}$ÚûõùÚûõ¨‘þùû‘ýÚ$v_p$Ú“‘ª÷¢ÚîùÚ“ùÉ—¤—þ’Ú÷‘ôð£¤ýÚª¢ù÷¢Æ
<óþ¨–¢ûüÚ$L'$Ú“ùÚ¤»¨ú‘ýÚð¤éÚ$G\setminus v_p$Ú¤Ú¢¤Ú÷à¤Úõüðþ¤þôÚîù
<$L'(w_i)=L(w_i)\setminus\{x,y\}$Ú“¤ýÚû¤Ú$1\le i\le q$ŠÚøÚ$L'(v)=L(v)$
<“¤ýÚû¤Ú$v\in V(G)\setminus\{w_1,\ldots,w_q\}$ÆÚ¥Úê¤­Ú¨—ì¤Úþí
<$L'$Å¤÷ïõþ¥ýÚ“¤ýÚ$G\setminus v_p$Ú•þ¢Úõüªø¢ÆÚŸ‘ñÚ¥Ú÷›‘ÚîùÚûþœÚþíÚ¥
<ûõ¨‘þùû‘ýÚ$v_p$ŠÚõð¤ÚŸ—õ‘ò³Ú${v_p}_{-1}$ŠÚ¤÷ðú‘ýÚ$x$ÚøÚ$y$Ú¤Ú¢¤
<óþ¨–É¾$L'$½Ú¡ø¢Ú÷¢¤÷¢ÚøÚ¢¨–îôÚþîüÚ¥Ú¤÷ðú‘ýÚ$x$ÚøÚ$y$Ú¤øýÚ${v_p}_{-1}$
<“ùÚî‘¤Ú÷¤ê—ùŠÚõü—øöÚþöÚ$L'$Å¤÷ïõþ¥ý±Ú$G\setminus v_p$Ú¤Ú“ùÚþí
<$L$Å¤÷ïõþ¥ýÚ“¤ýÚ$G$Úð¨—¤©Ú¢¢Æ
<ÒendÞproof×
<
<ÒvspaceÞ-1.2em×
<ÒbeginÞcor×ÒhspaceÞ.6em×
<û¤Úð¤éÚõ¨¯žÚ$5$Å÷—¡‘’•£þ¤Ú¨–Æ
<ÒlabelÞ5chthm×
<ÒendÞcor×
<
<ÒbeginÞproof×
<þíÚ÷õ‘þ©Úõ¨¯žÚ$G$Ú¤Ú¢¤Ú÷à¤Ú“ðþ¤þ¢ÚøÚ¢¤Ú¬ø¤–Úó¥øôÚ“‘Ú®‘êùÚî¤¢öÚþ‘óú‘þü
<ø›ùû‘ýÚöÚ¤Úõ™ó˜“÷¢ýÚî÷þ¢ÆÚŸ‘ñÚõü—ø÷þôÚ¥Úóþ¨—ú‘ýÚ¤»¨ú‘ýÚø›ùÚ÷‘õ—÷‘ûü
<¤÷ðú‘þüÚ¤ÚŸ£éÚî÷þôÚ—‘Úª¤¯ú‘ýÚì®þùÉÒrefÞplanarch×Ú“¤ø¤¢ùÚªø¢Æ
<ÒendÞproof×
<
<“‘—ø›ùÚ“ùÚþöÚîùÚ“¤ýÚû¤Úð¤éÚ$G$Ú¢¤þôÚ$\Chi(G)\le\ch(G)$ŠÚ•§Ú÷—þ›ù
<“‘òÚ÷ª‘öÚõü¢û¢Úä¢¢Ú¤÷ðüÚû¤Úð¤éÚõ¨¯žÚŸ¢î™¤Ú$5$Ú¨–ÚøÚ¥ÉþöÉ¤øÚ™“‘–
<—‘¥ùýÚ¥Úì®þùÚ•÷šÉ¤÷ïÒindexÞì®þùÚ•÷šÉ¤÷ï×Ú“ùÚ¢¨–Úõü¢û¢ÚîùÚ¨‘¢ù—¤þö
<™“‘—üÚ¨–ÚîùÚ—‘î÷øöÚõüª÷‘¨þôÆÚ—ø›ùÚî÷þ¢ÚîùÚð¤Ú$L$ÚþíÚ$5$Åóþ¨–¢ûüÚ“ù
<ð¤éÚõ¨¯žÉ$G$Ú“‘ª¢ŠÚ“¤û‘öÚì®þùÉÒrefÞplanarch×Úóðø¤þ—õüÚ÷¢›õóùýÚ“¤ý
<þ‘ê—öÚþíÚ$L$Å¤÷ïõþ¥ýÚ“¤ýÚ$G$Ú“ùÚ¢¨–Úõü¢û¢Æ
<
<—øõ‘¨öÚ¢¤ÉÒciteÞthomassen_g5×Ú“‘ÚþíÚ“¤û‘öÚõª‘“ùÚîùÚ¥Ú£î¤ÚöÚ¡ø¢¢¤ýÚõüî÷þôŠ
<ì®þùÚ¥þ¤Ú¤Ú™‘“–Úî¤¢ùÚ¨–Æ
<
<ÒbeginÞthm×ÒciteÞÐthomassen_g5Ð×ÒhspaceÞ.6em×
<û¤Úð¤éÚõ¨¯žÚ“‘Úîõ¤Ú¢¨–îôÚ•÷šŠÚ$3$Å÷—¡‘’•£þ¤Ú¨–Æ
<ÒendÞthm×
<
<“ùÚ¨‘¢ðüÚ¢þ¢ùÚõüªø¢ÚîùÚû¤Úð¤éÚõ¨¯žÚøÚ“¢øöÚõ™ó˜Ú¤»¨üÚ¥Ú¢¤›ùÚŸ¢î™¤Ú$3$
<¢¤¢ÆÚ¥Ú¨øþüÚð¤Ú$G$Úõ¨¯žÚøÚ“¢øöÚõ™ó˜Ú“‘ª¢Úû¤Ú¥þ¤ð¤éÚöÚ÷þ¥Ú÷þöÚ¨–Æ
<•§ÚûõùÚð¤êú‘ýÚõ¨¯žÚ“‘Úîõ¤Ú¢¨–îôÉ$5$ŠÚ$3$Å—“‘ûþ¢ùÚû¨—÷¢ÚøÚþöÚ÷ª‘öÚõü¢û¢
<“¤ýÚû¤Úð¤éÚõ¨¯žÚ$G$Ú“‘Úîõ¤Ú¢¨–îôÚ$5$ÚîùÚ$\delta(G)\ge 3$ÚøÚ$\Chi(G)=3$Š
<¢¤þôÚ$\ch(G)<k_0+1$Æ
<ûõ÷þöÚð¤êú‘ýÚõ¨¯žÚ¢ø“¡ªüÚ÷þ¥Ú“¢øöÚõ™ó˜ÚøÚ¥ÉþöÉ¤øÚ$3$Å—“‘ûþ¢ùÚû¨—÷¢Æ
<•§Ú“‘Ú—ø›ùÚ“ùÚì®þùÉÒrefÞbip3ch×Ú¤¢ùÚ¢þð¤ýÚ¥Úð¤êú‘Ú“‘Ú$\ch(G)<k_0+1$
<•þ¢Úõüªø¢Æ
<
<ÒsectionÞð¤êú‘ýÚ¢¤›ùÅ÷—¡‘’•£þ¤×
<·
<¢¤ÚþöÚ“¡©Ú“ùÚ“¤¤¨üÚð¤êú‘ýÚ¢¤›ùÅ÷—¡‘’•£þ¤Úõü•¤¢¥þôÆÚð¤éÚ$G$Ú¤
<ÞÒsiahÚ¢¤›ùÅ÷—¡‘’•£þ¤×ÒindexÞ¢¤›ùÅ÷—¡‘’•£þ¤×ÚðøþþôÚð¤Ú¥Úû¤Úóþ¨–¢ûü
<$L$Ú“ùÚ¤»¨ú‘þ©Úîù
<$|L(v)|=\deg_{_G}v$Ú“¤ýÚû¤Ú$v\in V(G)$ŠÚ¢¨–îôÚþíÚ¤÷ïõþ¥ýÚóþ¨—üÚ¢ª—ù
<“‘ª¢Ú¾$deg_{_G}$Å÷—¡‘’•£þ¤Ú“‘ª¢½Æ
<
<û¢éÚ¬óüÚþöÚ“¡©Ú™“‘–Úì®þùû‘ýÉÒrefÞnonD×ÚøÉÒrefÞchBrooks×Ú¨–ÚîùÚøóü
<ð¤êú‘ýÚ¢¤›ùÅ÷—¡‘’•£þ¤Ú¤Ú¥Ú÷à¤Ú¨‘¡—‘¤Ú¤¢ù“÷¢ýÚõüî÷¢ÚøÚ¢þð¤ýÚî¤öÚ“‘òý
<õ÷‘¨“üÚ“¤ýÚä¢¢Ú¤÷ðüÚóþ¨—üÚð¤êú‘ýÚ¢ó¡øùÚ“ùÉ¢¨–Úõü¢û¢Æ
<
<ÒbeginÞlem×ÒciteÞerdos×ÒhspaceÞ.6em×
<ê¤­Úî÷þ¢Ú$G_1$ÚøÚ$G_2$Ú¢¤›ùÅ÷—¡‘’•£þ¤Ú÷“‘ª÷¢ÚøÚ$v_1$ÚøÚ$v_2$Ú“ùÚ—¤—þ’
<¤»¨ú‘þüÚ¥ÚþöÚ¢øÚð¤éÚ“‘ª÷¢ÆÚð¤éÚ$G$ÚîùÚ¥ÚþîüÚî¤¢öÚ¢øÚ¤»§Ú$v_1$Úø
<$v_2$Ú¢¤Ú$G_1+G_2$Ú“ùÚ¢¨–Úõüþ¢Ú÷þ¥Ú¢¤›ùÅ÷—¡‘’•£þ¤Ú÷þ¨–Æ
<ÒlabelÞconnect×
<ÒendÞlem×
<
<ÒbeginÞproof×
<“¤ýÚ$i=1,2$ŠÚ¢¤›ùÅóþ¨–¢ûüÚ$L_i$Ú“ùÚ¤»¨ú‘ýÚ$G_i$Ú¤Ú¢¤Ú÷à¤Ú“ðþ¤þ¢Úîù
<$G_i$ŠÚ$L_i$Å¤÷ï•£þ¤Ú÷“‘ª¢ÆÚ“¢øöÚî‘¨—ùÚª¢öÚ¥Úîóþ–Úê¤­Úõüî÷þô
<$L_1(v_1)\cap L_2(v_2)=\emptyset$ÆÚ¢¤›ùÅóþ¨–¢ûüÚ$L$Ú“ùÚ¤»¨ú‘ýÚ$G$Ú¤
<“‘Ú$L(v)=L_1(v)$Ú“¤ýÚû¤Ú¤»§Ú$v$Ú¥Ú$G_1$Ú“ùÉ›¥Ú$v_1$ŠÚ$L(v)=L_2(v)$
<“¤ýÚû¤Ú¤»§Ú$v$Ú¥Ú$G_2$Ú“ùÉ›¥Ú$v_2$ŠÚøÚ$L(v^*)=L_1(v_1)\cup L_2(v_2)$
<—ã¤þéÚõüî÷þôŠÚîùÚ$v^*$Ú¤»§ÚŸ‘¬ñÚ¥ÚþîüÚî¤¢öÚ$v_1$ÚøÚ$v_2$Ú¨–ÆÚð¤Ú$G$
<þíÚ$L$Å¤÷ïõþ¥ýÚ$c$Ú¢ª—ùÚ“‘ª¢ÚøÚ÷¢þ§Ú$i$Ú÷‘öÚ“‘ª¢ÚîùÚ$c(v^*)\in L_i(v_i)$Š
<÷ð‘ùÚ$c|_V(G_i)$ÚþíÚ$L_i$Å¤÷ïõþ¥ýÚ“¤ýÚ$G_i$Ú¨–ÆÚþöÚ—÷‘ì­Ú÷ª‘öÚõü¢û¢
<îùÚ$G$ŠÚ$L$Å¤÷ï•£þ¤Ú÷þ¨–Æ
<ÒendÞproof×
<
<ÒvspaceÞ-1.2em×
<ÒbeginÞlem×ÒciteÞerdos×ÒhspaceÞ.6em×
<û¤Úð¤éÚûõ“÷¢ÚîùÚþíÚ¥þ¤ð¤éÚóì‘þüÚ¢¤›ùÅ÷—¡‘’•£þ¤Ú¢ª—ùÚ“‘ª¢ŠÚ¡ø¢
<¢¤›ùÅ÷—¡‘’•£þ¤Ú¨–Æ
<ÒlabelÞinduced×
<ÒendÞlem×
<
<ÒbeginÞproof×
<ê¤­Úî÷þ¢Ú$G$Úð¤êüÚûõ“÷¢Ú“‘Ú¥þ¤ð¤éÚóì‘þüÚ¢¤›ùÅ÷—¡‘’•£þ¤Ú$H$Ú“‘ª¢Æ
<“‘Ú¨—ì¤Ú¤øýÚ$r=|V(G)\setminus V(H)|$ÚŸîôÚ¤Ú™‘“–Úõüî÷þôÆÚð¤Ú$r=0$Š
<þ¥ýÚ“¤ýÚ™“‘–Ú÷õüõ‘÷¢ÆÚð¤Ú$r\ge 1$ŠÚ$v$Ú¤Ú¤»¨üÚ¥Ú$G$Úõüðþ¤þôÚîù
<“þª—¤þöÚê‘¬óùÚ¤Ú¥Ú$H$Ú¢¤¢ÆÚ“ùÚþöÚ—¤—þ’ÚŸ£éÚ$v$Ú¥Ú$G$ŠÚó¯õùýÚ“ù
<ûõ“÷¢ýÚöÚ÷õü¥÷¢ÆÚŸ‘ñÚð¤Ú$L$ÚþíÚ¢¤›ùÅóþ¨–¢ûüÚ“ùÚ¤»¨ú‘ýÚ$G$Ú“‘ª¢Š
<¤÷ðüÚ¢ó¡øùÚ¥Ú$L(v)$Ú¤Ú“¤ýÚ$v$Ú“¤õüð¥þ÷þôÚøÚ•§Ú¥Ú“¤¢ª—öÚöÚ¥
<óþ¨–ÚûõùÚûõ¨‘þùû‘ýÚ$v$ŠÚ¤»§Ú$v$Ú¤Ú¥Ú$G$ÚŸ£éÚõüî÷þôÆÚ¥Úê¤­Ú¨—ì¤
<õü¢÷þôÚ$G\setminus v$Ú¥Úóþ¨—ú‘ýÚ¢¢ùÚª¢ùÚþíÚ¤÷ïõþ¥ýÚóþ¨—üÚ¢¤¢Æ
<þöÚ¤÷ïõþ¥ýÚ¤Ú“‘Ú¤÷ðüÚîùÚ¥Ú$L(v)$Úî÷‘¤Úð£ª—ùþôÚ“ùÚþíÚ$L$Å¤÷ïõþ¥ý
<“¤ýÚ$G$Úð¨—¤©Úõü¢ûþôÆ
<ÒendÞproof×
<
<“¤ýÚ™“‘–Úì®þùÉÒrefÞnonD×Ú“ùÚì®þùýÚõ÷¨ø’Ú“ùÚ¤ø“þöÒindexÞ¤ø“þö×Ú÷þ‘¥Ú¢¤þô
<îùÚ¢¤Ú•üÚõüþ¢ÚøÚöÚ¤Ú“¢øöÚ“¤û‘öÚõü•£þ¤þôÆ
<
<ÒbeginÞthm×ÒciteÞerdos×ÒhspaceÞ.6em×
<û¤Úð¤éÚ¢øûõ“÷¢Ú“›¥Úð¤êú‘ýÚî‘õñÚøÚ¢ø¤û‘ýÚê¤¢ŠÚþíÚ¥þ¤ð¤éÚóì‘þü
<¢¤¢ÚîùÚ¢ø¤ýÚ¥øšÚþ‘Ú¢ø¤Ú¥ø›üÚ“‘ÚþíÚø—¤Ú¨–Æ
<ÒlabelÞRubin×
<ÒendÞthm×
<
<ÒvspaceÞ-1.2em×
<ÒbeginÞthm×ÒciteÞerdos×ÒhspaceÞ.6em×
<þíÚð¤éÚûõ“÷¢Ú¢¤›ùÅ÷—¡‘’•£þ¤Ú÷þ¨–ŠÚð¤ÚøÚ—÷ú‘Úð¤Úû¤Ú“óøíÚöÚþíÚð¤éÚî‘õñ
<þ‘ÚþíÚ¢ø¤Úê¤¢Ú“‘ª¢Æ
<ÒlabelÞnonD×
<ÒendÞthm×
<
<ÒbeginÞproof×
<ð¤Úû¤Ú“óøíÚð¤éÚ$G$ÚþíÚð¤éÚî‘õñÚþ‘ÚþíÚ¢ø¤Úê¤¢Ú“‘ª¢ŠÚ¥ÚóôÉÒrefÞconnect×
<¢¤õüþ‘“þôÚîùÚ$G$Úð¤êüÚ¢¤›ùÅ÷—¡‘’•£þ¤Ú÷þ¨–ÆÚ¥Ú¨øýÚ¢þð¤Úð¤Ú$G$Ú“óøîü
<¢ª—ùÚ“‘ª¢ÚîùÚð¤éÚî‘õñÚþ‘Ú¢ø¤Úê¤¢Ú÷þ¨–ŠÚ¥Úì®þùÉÒrefÞRubin×Ú¥þ¤ð¤é
<óì‘þüÚ$H$Ú¥Ú$G$Ú¤Úõüþ‘“þôÚîùÚ¢ø¤ýÚ¥øšÚþ‘Ú¢ø¤Ú¥ø›üÚ“‘ÚþíÚø—¤Ú¨–ÆÚ•§
<óôÉÒrefÞinduced×Ú÷ª‘öÚõü¢û¢ÚîùÚ$G$Úð¤êüÚ¢¤›ùÅ÷—¡‘’•£þ¤Ú¨–Æ
<ÒendÞproof×
<
<“‘Ú“ú¤ùÚðþ¤ýÚ¥Úì®þùÉÒrefÞRubin×Úõü—øöÚì®þùÚ“‘òÚ¤Ú“ùÚªîñÚ¥þ¤Ú÷þ¥
<“þ‘öÚî¤¢Æ
<
<ÒbeginÞthm×ÒciteÞerdos×ÒhspaceÞ.6em×
<þíÚð¤éÚûõ“÷¢Ú¢¤›ùÅ÷—¡‘’•£þ¤Ú¨–ŠÚð¤ÚøÚ—÷ú‘Úð¤ÚþíÚ¢ø¤Ú¥øšÚþ‘Úþí
<$\theta_{r,s,t}$Ú¤Ú“ùÚä÷øöÚ¥þ¤ð¤éÚóì‘þüÚ¢ª—ùÚ“‘ª¢Æ
<ÒendÞthm×
<
<óôÚ¥þ¤ÚîùÚ“ùÚ¨‘¢ðüÚ“‘Ú¨—ì¤Ú¤øýÚ—ã¢¢Ú¤»¨ú‘ýÚþíÚð¤éÚ™‘“–Úõüªø¢Ú¢¤Ú“¤û‘ö
<ì®þùÉÒrefÞchBrooks×Ú“ùÚî‘¤Úõü¤ø¢Æ
<
<ÒbeginÞlem×ÒciteÞerdos×ÒhspaceÞ.6em×
<ê¤­Úî÷þ¢Ú$G$ÚþíÚð¤éÚøÚ$v_0$Ú¤»¨üÚ¥ÚöÚ“‘ª¢ÆÚð¤Ú÷ð‘ª–Ú$f(v)=\deg_G v$
<“¤ýÚû¤Ú$v\not=v_0$ÚøÚ$f(v_0)=\deg_G v_0+1$ŠÚ÷ð‘ùÚ$G$Úð¤êüÚ$f$Å÷—¡‘’•£þ¤
<¨–Æ
<ÒlabelÞv0plus1×
<ÒendÞlem×
<
<ì®þùÚ“ã¢ýÚîùÚõª‘“ùÚì®þùÚõã¤øéÚ“¤øî§ÒfootnoteÞR.\,L.~Brooks×ÒindexÞ“¤øî§×
<ÒindexÞì®þùÚ“¤øî§×
<¾ì®þùÉÒrefÞBrooks×½Ú¢¤Ú¤÷ïõþ¥ýÚð¤êú‘Ú¨–ŠÚ÷‘öÉîùÚ¡øûþôÚ¢þ¢Úð¨—¤ªü
<¥ÚþöÚì®þùÚ¨–Æ
<
<ÒbeginÞthm×ÒciteÞerdos×ÒhspaceÞ.6em×
<“¤ýÚû¤Úð¤éÚ$G$Ú¢¤þôÚ$\ch(G)\le\Delta(G)+1$ÚøÚ—¨‘øýÚ“¤ì¤¤Ú¨–ŠÚð¤ÚøÚ—÷ú‘
<ð¤Ú$G$ÚþíÚð¤éÚî‘õñÚþ‘ÚþíÚ¢ø¤Úê¤¢Ú“‘ª¢Æ
<ÒlabelÞchBrooks×
<ÒendÞthm×
<
<ÒbeginÞproof×
<“¤ì¤¤ýÚ÷‘õ¨‘øýÚ$\ch(G)\le\Delta(G)+1$Ú“¤ýÚû¤Úð¤éÚ$G$ŠÚ÷—þ›ù
<êø¤ýÚóôÉÒrefÞv0plus1×Ú¨–ÆÚûõ÷þöÚóôÚõ¥“ø¤Ú÷ª‘öÚõü¢û¢ÚîùÚð¤Ú$G$
<¤»¨üÚ“‘Ú¢¤›ùÚîõ—¤Ú¥Ú$\Delta(G)$Ú¢ª—ùÚ“‘ª¢ŠÚ÷ð‘ù
<$\ch(G)\le\Delta(G)$ÆÚ•§Úð¤Ú$\ch(G)=\Delta(G)+1$ŠÚ÷ð‘ùÚ$G$Úð¤êü
<õ÷—àôÚ¨–ÚîùÚ¢¤›ùÅ÷—¡‘’•£þ¤Ú÷þ¨–ÆÚ¥Ú¨øýÚ¢þð¤ÚûõùÚð¤êú‘þüÚîù
<¢¤›ùÅ÷—¡‘’•£þ¤Ú÷þ¨—÷¢ŠÚ¢¤Úì®þùÉÒrefÞnonD×Úª÷‘¨‘þüÚª¢ù÷¢ÚøÚ“ùÉ¨‘¢ðü
<¢þ¢ùÚõüªø¢ÚîùÚ—÷ú‘Úð¤êú‘ýÚõ÷—àõüÚîùÚû¤Ú“óøíÚ÷ú‘Úî‘õñÚþ‘Ú¢ø¤Úê¤¢
<“‘ª¢ŠÚð¤êú‘ýÚî‘õñÚøÚ¢ø¤û‘ýÚê¤¢Úû¨—÷¢Æ
<ÒendÞproof×
<
<•þ©Ú¥ÚþöÚ÷ª‘öÚ¢¢þôÚ“¤ýÚû¤Úð¤éÚ$G$Ú¤“¯ùÚ$\Chi(G)\le\ch(G)$Ú“¤ì¤¤Ú¨–Æ
<•§Úì®þùÚ“‘òÚ÷ª‘öÚõü¢û¢Ú“¤ýÚû¤Úð¤éÚ$G$Ú¢¤þôÚ$\Chi(G)\le\Delta(G)+1$Æ
<Ÿ‘ñÚð¤Ú$G$Úð¤êüÚ“‘Ú$\Chi(G)=\Delta(G)+1$Ú“‘ª¢ŠÚ¥Ú÷‘õ¨‘øýÚ“‘òÚ÷—þ›ùÚõüªø¢
<îùÚ$\ch(G)=\Delta(G)+1$ÚøÚ¯“ëÚì®þùÉÒrefÞchBrooks×Úì®þùÚ¥þ¤Ú“ùÚ™“‘–Úõü¤¨¢
<îùÚûõ‘öÚì®þùÚõªúø¤Ú“¤øî§Ú¨–Æ
<
<ÒbeginÞthm×ÒhspaceÞ.6em×
<“¤ýÚû¤Úð¤éÚ$G$Ú¢¤þôÚ$\Chi(G)\le\Delta(G)+1$ÚøÚ—¨‘øýÚ“¤ì¤¤Ú¨–ŠÚð¤ÚøÚ—÷ú‘
<ð¤Ú$G$ÚþíÚð¤éÚî‘õñÚþ‘ÚþíÚ¢ø¤Úê¤¢Ú“‘ª¢Æ
<ÒlabelÞBrooks×
<ÒendÞthm×
<
<ÒsectionÞ¤÷ïõþ¥ýÚóþ¨—üÚþ‘óüÒlabelÞÐedgeLC_secÐ××
<·
<õª‘“ùÚ÷ùÚ•þ©Ú¥ÚþöÚõ¯¤žÚª¢ŠÚõü—øöÚóþ¨–¢ûüÚ“ùÚþ‘óú‘ýÚþíÚð¤éÚ¾þ‘
<ð¤éÚ÷¢ð‘÷ù½ÚøÚõêúøôÚ¤÷ïõþ¥ýÚóþ¨—üÚþ‘óüÒfootnoteÞedge list coloring×
<ÒindexÞ¤÷ïõþ¥ýÚóþ¨—üÚþ‘óü×Ú¤Ú“¤¤¨üÚî¤¢Æ
<
<ð¤Ú$G$ÚþíÚð¤éŠÚ$L(G)$Úð¤éÚþ‘óüÚ$G$ŠÚøÚ$f:E(G)\to\N$Ú÷ð‘ª—üÚ¢ó¡øù
<“‘ª¢ŠÚõ÷àø¤Ú¥ÚþíÚÞÒsiahÚ$f$Åóþ¨–¢ûüÚ“ùÚþ‘óú‘ý×Ú$G$Ú¾þ‘ÚÞÒsiahÚ$f$Åóþ¨–¢ûü
<þ‘óü×ÒfootnoteÞedge $f$--list assignment×Ú“ùÚ$G$½ŠÒindexÞ$f$Åóþ¨–¢ûüÚþ‘óü×Ú¢¤
<øìâÚþíÚ$f$Åóþ¨–¢ûüÚ“ùÚ¤»¨ú‘ýÚ$L(G)$Ú¨–ÆÚðøþþôÚ$G$Úð¤êü
<ÞÒsiahÚ$f$Å÷—¡‘’•£þ¤Úþ‘óü×ÒfootnoteÞedge $f$--choosable×
<ÒindexÞ$f$Å÷—¡‘’•£þ¤Úþ‘óü×Ú¨–ŠÚð¤Ú$L(G)$Úð¤êüÚ$f$Å÷—¡‘’•£þ¤Ú“‘ª¢Æ
<
<ÞÒsiahÚ÷¢þ§Ú¤÷ðüÚóþ¨—ü×ÒfootnoteÞlist chromatic index×
<ÒindexÞ÷¢þ§Ú¤÷ðüÚóþ¨—ü×Úð¤éÚ$G$ÚîùÚ“‘É$\ech(G)$
<÷õ‘þ©Ú¢¢ùÚõüªø¢Ú“¤“¤Ú“‘Úä¢¢Ú¤÷ðüÚóþ¨—üÚð¤éÚ$L(G)$Ú—ã¤þéÚõüð¤¢¢ÚøÚ¤øªö
<¨–ÚîùÚ¢¤þôÚ$\Chi'(G)\le\ech(G)$Æ
<
<þîüÚ¥Úõúõ—¤þöÚõ¨Žóùû‘ýÚõ“Ÿ˜Ú¤÷ïõþ¥ýÚóþ¨—üÚð¤êú‘ŠÚŸ¢§Ú¤÷ïõþ¥ý
<óþ¨—üÚ¨–ÚîùÚ“¨þ‘¤ýÚ¥Ú•¦øûªú‘ýÚî÷ø÷üÚ¢¤Ú¤¨—‘ýÚ™“‘–ÚöÚ÷›‘ôÚõüðþ¤¢Æ
<“¤Ú¨‘§Ú—‘¤þ¡ùýÚîùÚ¢¤ÉÒciteÞgraphcoloring×Úõ¢ùŠ
<þöÚŸ¢§Ú÷¡¨—þöÚ“‘¤Ú—ø¨ÁÚ“øóø“‘©ÒindexÞ“øóø“‘©×ÚøÚû¤þ§ÒindexÞû¤þ§×
<¢¤ÉÒciteÞLCCref×Ú“ùÚ‘”Ú¤¨þ¢ùÚ¨–ÚøóüÚ•þ©Ú¥Úö
<øþ¥þ÷ïÒindexÞøþ¥þ÷ï×ŠÚðø•—‘ÒfootnoteÞR.\,P.~Gupta×ÒindexÞðø•—‘×ŠÚø
<ó“¤—¨øöÒfootnoteÞM.\,O.~Albertson×ÒindexÞó“¤—¨øö×Úø
<îøóþ÷¥ÒfootnoteÞK.\,L.~Collins×ÒindexÞîøóþ÷¥×Ú÷þ¥Ú“ùÚöÚ÷¢þªþ¢ùÚ“ø¢÷¢Æ
<
<ÒbeginÞconj×ÒciteÞLCCref×ÒhspaceÞ.6em×
<ÞÒnazokÚ¾ÞÒbfÚŸ¢§Ú¤÷ïõþ¥ýÚóþ¨—ü×½×ÒindexÞŸ¢§Ú¤÷ïõþ¥ýÚóþ¨—ü×
<“¤ýÚû¤Úð¤éÚ$G$Ú¢¤þôÚ$\ech(G)=\Chi'(G)$Æ
<ÒlabelÞLCC×
<ÒendÞconj×
<
<ì‘“ñÚ—ø›ùÚ¨–ÚîùÚ¢¤Úð¤¢ûõ‘þüÚÃ÷à¤þùÚð¤éÚ“ùÚî›‘Úõü¤ø¢ŒÀÚîùÚ“‘Úû¢éÚ—ãþþö
<õ¨þ¤Ú•¦øûªú‘ýÚþ÷¢ùÚ¢¤Ú÷à¤þùÚð¤éŠÚ¢¤Úè‘¥Ú¢ûùÚ€‰‰Ú¢¤Úò¨î‘Ú“¤ð¥¤Úª¢Š
<þöÚŸ¢§Ú“ùÚä÷øöÚþîüÚ¥Úõ¨Žóùû‘ýÚõúôÚõ¯¤žÚª¢ùÚ¨–Æ
<
<¥Ú÷›‘ÚîùÚð¤éÚþ‘óüÚû¤Ú¢ø¤Ú$C_n$Ú“‘Ú$C_n$Úþî¤þ¡–Ú¨–ŠÚ“ùÚ¨‘¢ðüÚ¢þ¢ùÚõüªø¢
<îùÚŸ¢§Ú¤÷ïõþ¥ýÚóþ¨—üÚ“¤ýÚ¢ø¤û‘Ú“¤ì¤¤Ú¨–Æ
<ûõ÷þöÚ“‘Ú“¤¤¨üÚ¨‘¢ùýÚõü—øöÚ¢þ¢ÚîùÚþöÚŸ¢§Ú“¤ýÚû¤Ú¨—‘¤ùÚ¾$K_{1,r}$½Ú÷þ¥
<¢¤¨–Ú¨–Æ
<
<Ÿ¢§Ú¤÷ïõþ¥ýÚóþ¨—üÚ¢¤ÚŸ‘ó—üÚîùÚ$G=K_{n,n}$ŠÚûõ‘öÚŸ¢§Úõã¤øé
<¢þ÷þ—¥ÒindexÞ¢þ÷þ—¥×ÒindexÞŸ¢§Ú¢þ÷þ—¥×Ú¾Ÿ¢§ÉÒrefÞdinitz_conj×½Ú¨–Úîù
<õ¢—üÚþîüÚ¥Úõ¨Žóùû‘ýÚõúôÚõ“Ÿ˜Úõ¤“ãú‘ýÚò—þöÚ“ùÚªõ‘¤Úõü¤ê–ÚøÚ¨¤÷›‘ô
<—ø¨ÁÚð‘óøþöÒindexÞð‘óøþö×Ú™‘“–Úª¢Ú¾ì®þùÉÒrefÞgalLCC×½Æ
<
<—‘î÷øöÚõì‘óùû‘ýÚ•¦øûªüÚ“¨þ‘¤ýÚ¢¤Ú¤¨—‘ýÚ™“‘–ÚŸ¢§Ú¤÷ïõþ¥ýÚóþ¨—üÚ÷ð‘ª—ù
<ª¢ùÚ¨–ÚîùÚ“¤¡üÚ“‘Ú™“‘–ÚöÚ“¤ýÚ¤¢ùû‘þüÚ¥Úð¤êú‘ÚøÚ“¤¡üÚ¢þð¤Ú“‘Ú¤Žù
<î¤÷ú‘þüÚ“¤ýÚ$\ech(G)$Ú“ùÚþöÚŸ¢§ÚŸõóùÚ“¤¢ù÷¢Æ
<
<õü¢÷þôÚ÷¢þ§Ú¤÷ðüÚð¤éÚî‘õñÚ$n$Ú¤»¨üÚ“¤ýÚ$n$Éû‘ýÚê¤¢Ú“¤“¤Ú“‘Ú$n$Úø
<“¤ýÚ$n$Éû‘ýÚ¥øšÚõ¨‘øýÚ$n-1$Ú¨–ÆÚ¥Ú¯¤êüÚûðøþ¨–ÒindexÞûðøþ¨–×Úø
<þ‘÷¨öÒindexÞþ‘÷¨ö×Ú¢¤ÉÒciteÞhaggjans×Úì®þùÚ¥þ¤Ú¤Ú™‘“–Úî¤¢ù÷¢Æ
<
<ÒbeginÞthm×ÒciteÞhaggjans×ÒhspaceÞ.6em×
<“¤ýÚû¤Ú$n$Ú¢¤þôÚ$\ech(K_n)\le n$Æ
<ÒendÞthm×
<
<•§ÚŸ¢§Ú¤÷ïõþ¥ýÚóþ¨—üÚ“¤ýÚû¤Úð¤éÚî‘õñÚ“‘Ú—ã¢¢Úê¤¢ýÚ¤»§Ú¢¤¨–Ú¨–Æ
<
<“ùÚä÷øöÚ¤¢ùÚ¢þð¤ýÚ¥Úð¤êú‘ÚîùÚŸ¢§Ú¤÷ïõþ¥ýÚóþ¨—üÚ¤Ú“¤ø¤¢ùÚõüî÷¢Š
<“ø¤ø¢þöÒfootnoteÞO.\,V.~Borodin×ÒindexÞ“ø¤ø¢þö×Úì®þùÚ¥þ¤Ú¤Ú™‘“–Úî¤¢ùÚ¨–Æ
<
<ÒbeginÞthm×ÒciteÞboroding14×ÒhspaceÞ.6em×
<“¤ýÚû¤Úð¤éÚõ¨¯žÒindexÞð¤éÚõ¨¯ž×Ú$G$Ú“‘Úîõ¤Ú¢¨–îôÚ$14$Ú¢¤þô
<$\ech(G)=\Delta(G)$Æ
<ÒlabelÞplan14×
<ÒendÞthm×
<
<“‘Ú—ø›ùÚ“ùÚþöÚîùÚ“¤ýÚû¤Úð¤éÚ$G$Ú¢¤þôÚ$\Chi'(G)\ge\Delta(G)$ŠÚì®þù
<“‘òÚ÷ª‘öÚõü¢û¢ÚîùÚ“¤ýÚð¤êú‘ýÚõ¨¯žÚ$G$Ú“‘Úîõ¤Ú¢¨–îôÚ$14$ŠÚ¢¤þô
<$\Chi'(G)=\ech(G)=\Delta(G)$Æ
<
<¤¢ùÚ¢þð¤Ú¥Ú¥Úð¤êú‘þüÚîùÚŸ¢§Ú¤÷ïõþ¥ýÚóþ¨—üÚ¤Ú“¤ø¤¢ùÚõüî÷÷¢Š
<ð¤êú‘ýÚ¢ø“¡ªüÚû¨—÷¢ÆÚþöÚõø®øáÚ—ø¨ÁÚð‘óøþöÒindexÞð‘óøþö×Ú™‘“–Úª¢ùÚ¨–Úø
<õ‘ÚöÚ¤Ú“¢øöÚ£î¤Ú“¤û‘öÚõüø¤þôÆ
<
<ÒbeginÞthm×ÒciteÞgalvin×ÒhspaceÞ.6em×
<“¤ýÚû¤Úð¤éÚ¢ø“¡ªüÚ$G$Ú¢¤þôÚ$\ech(G)=\Chi'(G)$Æ
<ÒlabelÞgalLCC×
<ÒendÞthm×
<
<þöÚ“¡©Ú¤Ú“‘Úª‘¤ùÚ“ùÚ“¤¡üÚî¤÷ú‘ýÚ÷¢þ§Ú¤÷ðüÚóþ¨—üÚ“ùÚ•‘þ‘öÚõü“¤þôÆ
<“¤ýÚû¤Úð¤éÉ$G$Úõü¢÷þôÚ$\Delta(L(G))\le 2\Delta(G)-2$ÆÚ•§
<ì®þùÉÒrefÞchBrooks×Úî¤öÚ¥þ¤Ú¤Ú“ùÉ¢¨–Úõü¢û¢Æ
>$$\ech(G)\le 2\Delta(G)-1$$
>\vspace{-\baselineskip}
<
<øóüÚ“‘Úõì‘þ¨ùÚþöÚî¤öÚ“‘Úì®þùÚøþ¥þ÷ïÒindexÞøþ¥þ÷ï×ÒindexÞì®þùÚøþ¥þ÷ï×
<¾$\Chi'(G)\le\Delta(G)+1$½ŠÚ¢¤õüþ‘“þô
<îùÚ“‘þ¢Úî¤÷ú‘ýÚ¡þóüÚ“ú—¤ýÚ•þ¢Úî÷þôÚøÚ¥Ú›õóùÚî¤÷ú‘þüÚ“¤Ÿ¨’Ú$\Delta(G)$
<“þ‘“þôÚîùÚ®¤þ’ÚÚ$\Delta(G)$Ú¢¤Ú÷ú‘Úîõ—¤Ú¥Ú$2$Ú“‘ª¢ÆÚþîüÚ¥Ú÷—þ›ùû‘Ú¢¤Úþö
<¥õþ÷ùÚ¢¤Úì®þùÚ“ã¢Úõüþ¢Æ
<
<ÒbeginÞthm×ÒciteÞchethagg×ÒhspaceÞ.6em×
<“¤ýÚû¤Úð¤éÚ“¢øöÚõ™ó˜Ú$G$Ú¢¤þô
>$$\ech(G)\le\frac{9}{5}\Delta(G).$$
>\vspace{-\baselineskip}
<ÒendÞthm×
<
<þöÚì®þùÚ÷—þ›ùÚ¬óüÚõ¤›âÉÒciteÞchethagg×Ú¨–ÚøÚ“¤ýÚ›óøðþ¤ýÚ¥Ú¯øò÷ü
<ª¢öÚõ¯ó’ŠÚ¥Ú£î¤Ú“¤û‘öÚöÚªôÚõü•øªþôÆ