（基础数学专业论文）曲面嵌入图的子图结构及在染色问题中的应用.pdf

中文摘要 本文研究嵌入图以及平面图的子图结构以及在着色上的应用一些问题 在文章 8 8 中 z h a o 考虑了一类可嵌入在可定向曲面 欧拉特征值口s0 并且不包含 短圈的图 z h a o 证明了任意的可嵌人在可定向曲面 欧拉特征值口s0 并且 不包含从4 到1 l 一1 2 a 圈的图是可3 一着色的并且提出一个问题能够保证不包 含从4 到 圈的图是可3 一着色的最小的整数七 是多少 受到这个问题的 启发 我们考虑 1 1 3 a 并且得到一个l e b e s g u e 形式的定理 表示可 嵌入在可定向盐面 欧拉特征值口 o 并且不包含从4 到1 l 一3 口圈的图 我们 得到的以下主要结果t 定理2 1g 是一个嵌入在可定向雎面 欧拉特征值盯so 并且没有相邻的 三面 如果g 不包含从4 到1 1 3 口的面 要么g 包含一个2 一一度点或者包含一 个的艇 1 2 3 口 一面 作为子图的舭 1 2 3 x 一面的应用 我们证明 定理2 2 如果g 鲧 那么g i s3 一可着色的 自然地 我们考虑了平面图的3 一可着色 在1 9 7 6 s t e i n b e r g 给出一个猜想任 意不包含4 一圈和5 一圈的平面图是3 一可着色的 而这个条件就必要的 因为已 经找到不可3 一着色的平面图要么包含4 一圈或者包含5 一圈 见凰和 3 4 中 的例子 f i g 2 由于直接证明的困难性 许多人考虑了一些特殊的平面图 在这 里 我们考虑一类平面图不包含相邻三面并且不包含 5 6 9 一圈 我们得到 个 l e b c s g u e 形式的定理并验证这类平面图是可3 一着色的 定理3 1g 是一个2 连通的平面图不包含相邻三面并且不包含 5 6 9 一圈 那么必有以下结论成立 1 j g 3 2 g 包含一个4 一面 3 g 包含一个s p e c i a l1 0 一面关联于十个3 度点并且与五个3 一面相邻 作为定理3 1 的应用 我们得到下面的结论 定理3 2 任何平面图不包含相邻三面并且不包含 5 6 9 一圈是可3 一着色 的 关于平面图 有一个猜想 是否任意的3 一可着色的平面图的点荫度不超过 2 受到这个猜想和s t e i n b e r g 猜想的启发 我们考虑了不包含短圈的平面图的点 荫度同胚 我们证明了一个l e b e s g u e 形式的结构定理并把这个结论应用在不包含 4 一圈的平面图上 定理4 1g 是一个不包含4 一面并且不包含相邻三面的平面图 如果6 g 4 那么g 包含一个谨导出子图 应用定理4 1 结果 我们给出了文章 4 6 的简短证明作为引理4 2 并且得到不包含 4 一圈的平面图的点荫度不超过2 作为定理4 3 引理4 2 如果g 是一个不包含4 一圈的平面图 那么g 是4 一可选色性的 定理4 3 如果g 尼一个不包含4 一圈的平面图 那么b g 2 接着我们使用移权法和反证法完成了以下结论的证明 定理4 4 如果g 是 个不包含3 一圈的平面图 那么口 g 2 定理4 5 如果g 是一个不包含5 一圈的平面图 那么口 g 2 定理4 3 4 4 和4 5 可视为对上面猜想的是否正确的一个正面支持 关于平面图的平方图 在 7 6 w e g n e r 提出了以下猜想 猜想5 1 1 7 6 1 对于一个平面图g 舻 叱拿苫 1 讧 篡主7 1 受到w e g n e r 猜想的启发 我们考虑了不包含3 一圈的平面图的着色性 下面 是已知的关于平面图的平方图的着色性 t h o m a s s e n 7 1 l 证明了最大度为3 的平面图的平方图是7 一可着色的 h e u v e l 和m c g u i n n e s s1 3 q 证明了x g 2 2 a g 2 5 对于任意平面图g m o l l o y 和 s a l a v a t i p o u r 嘲把上界减到x g 2 sr 垒3 盟1 t 7 8 并有x g 2 r 业31 2 5 如 果t h a tz x g 2 4 1 l i h w a n g 和z h u1 5 2 证明了对于不包含甄一圉子式的平 面图g x g 2 sz x g 3 如果2 z x a 3 并且x g 2 学j 1 如果 6 3 4 我们用g 表示不包含三角形的平面图的集合 在这一部分 我们证明了一个 l e b e s g u e 形式的定理从而得到口的 个固定结构并且利用这个性质我们找到了这 类平面图的平方图的可选色性的一个上界 我们称一个4 一面 足特殊的如果 关联于两个2 一度点并且称一个点口是大点如果 是一个1 5 一度点 我们称一 个大点口是轻的如果西g 2 口 a a 1 3 我们记死 u 和乃 u 分别为与口相 邻的2 一度点和3 一度点的个数 定理5 1 如果g g 并且6 g 2 那么必有以下结论成立 n 1 a 一个1 4 一一度点与一个2 一度点相邻 b 如果u 是一个大点并且口至少关联于d v 一7 特殊的4 一面 那么r 2 口 d v 或有0 r 3 口 d v 一吨 s7 并有一个3 一度点属于n v 并且这个3 一 度点关联于两个4 一面 这两个4 一面均关联于2 一度点 c 有一个路忍 x y z 其中d y 3 并且d x d z 1 5 作为定理5 1 的应用 我们得到下面的定理 定理5 2 对于g g 要么g 包含一个轻的大点要么x g 2 a g t 6 在第六章中 我们着重进一步考虑了以下内容 i 平面图的非正则着色 i i 平面图和嵌入图的平方图的着色问题 i i i l p q 一着色问题 关键词 嵌入图 平面图 子图 点着色 列表着色 可选色性 l q 着色 点荫度 a b s t r a c t i nt h i sd i s s e r t a t i o n w ei n v e s t i g a t et h es t r u c t u r e so ft h es u b g r a p h so fp l a n e f 印h sa n dg r a p h se m b e d d e di no r i e n t a b l es u r f a c ew i t ha p p l i c a t i o n st og r a p hc o l o r i n g sp r o b l e m s i n 8 8 z h a nc o n s i d e r e dt h e3 c o l o r a b i f i t yo fg r a p h sw h i c ha r ee m o b e d d a b l ei nt h es u r f a c eo fn e g a t i v ec h a r a c t e r i s t i ca n dc o n t a i n i n gn os h o r tc i r c u i t s z h a op r o v e dt h a te v e r yg r a p he m b e d d e di ns u r f a c eo fn e g a t i v ec h a r a c t e r i s t i c 叮w i t h o u t c i r c u i t sf o r4 is1 1 1 2 ai s3 c o l o r a b l ea n dp r o p o s e g aq u e s t i o nt h a ta s k st h es m a l l e s ti n t e g e rk s t h a tg u a r a n t e e st h e3 c o l o r a b i l i t yo f g r a p h 8e m b e d d e di ns u r f a c eew i t h o u ti c i r c u i t sf o r4 i i n s p i r e db y t h eq u e s t i o n w ec o n s i d c rk s 1 1 3 aa n dg e tal e b e s g u et y p et h e o r e m l e t 鲧b et h es e to fg r a p h se m b e d d e di nt h eo r i e n t a b l es u r f a c eo fe u l e rc h a r a c t o r i s t i c 口 0w h i c hc o n t a i nn oc i r c u i t so fl e n g t hf r o m4t oi i 一3 盯 t h em a i n r e s u l t sa r e s u m m a r i z e da sf o l l o w s t h e o r e m2 1l e tgb eag r a p he m b e d d e di nao r i e n t a b l es u r f a c eo fe u l e r c h a r a c t e r i s t i c 叮 0a n dw i t h o u ta d j a c e n tt r i a n g l e s gc o n t a i n sn of a c e so fd e g r e e f r o m4t o1 1 3 a t h e ne i t h e rgc o n t a i n sa2 v e r t e xo ra 的h t 1 2 3 回 f a c e a sa na p p l i c a t i o no ft h es u b g r a p hl i g h t 1 2 3 x 口 f a c e w ep r o v et h a t t h e o r e m2 2i fg 鲧 t h e ngi s3 c h o o s a b l e n a t u r a l l y w ec o n s i d e rt h e3 c o l o r a b l ep l a n eg r a p h s i n1 9 7 6 s t e i n b e r gc o s j e c t u r e dt h a te v e r yp l a n eg r a p hw i t h o u t4 a n d5 c i r c u i t si s3 c o l o r a b l e w ek n o w t h ec o n d i t i o no ft h ec o n j e c t u r ei sn e c e s s a r ys i n c et h e r ee x i s tn o n 3 c o l o r a b l ep l a n e g r a p h sw h i c ha r ee i t h e rc 4 f r e eo r 岛一f r e e s e ek 4a n d 3 4 1 f i g 2 t h ec o n j e c t u r ei s h a r dt ob es o l v e dd i r e c t l ys ot h a tm a n ys p e c i a lc a s e 8o fp l a n eg r a p h sa r ec o n s i d e r e d w eo n l yc o n s i d e rt h ep l a n eg r a p h sc o n t a i n i n gn oa d j a c e n tt r i a n g l e sa n dc i r c u i t so f l e n g t hi 5 6 9 a n dg e tal e b e s g u et y p et h e o r e m a sac o n s e q u e n c e w ek n o w t h e s ep l a n eg r a p h sa r e3 c o l o r a b l c t h e o r e m3 1l e tgb ea2 c o n n e c t e dp l a n eg r a p ht h a tc o n t a i n sn oa d j a c o n t t r i a n g l e sa n dc i r c u i t so fl e n g t hi 5 6 9 t h e n o n eo ft h ef o l l o w i n gh o l d s 1 6 g 3 2 gc o n t a i n sa4 f a c e 3 gc o n t a i n sas p e c i a l1 0 f a c ei n c i d c n t w i t ht e n3 v e r t i c e sa n da d j a c e n tt of i v e 3 f a c e s a sad i r e c tc o n s e q u e n c eo ft h et h c o r c m3 1 w eh a v e t h e o r e m3 2e v e r yp l a n eg r a p hw i t h o u t 删a c e n tt r i a n g l e sa n dc i r c u i t so f l e n g t hi n 5 6 9 i s3 c o l o r a b l e o np l a n eg r a p h s t h e r ei sas t i l lo p e nc o n j e c t u r es a y st h a te v e r y3 c o l o r a b l e p l a n eg r a p hh a st h ev e r t e xa r b o r i e i t yw h i c hi sn om o r et h a n2 i n s p i r e db yt h i s c o n j e c t u r ea n ds t e i n b e r g sc o n j c c t u r e w ec o n s i d e rt h ev e r t e xa r b o r i c i t yo fp l a n e g r a p h sw i t h o u ts h o r tc i r c u i t s w ep r o v et h ef o l l o w i n gt h e o r e m s w ep r o v e8l c b e s g u et y p et h e o r e ma n da sc o n s c q u c n c et h a t4 c h o o s a b l i t yo f q f r e ep l a n eg r a p h 8 t h e o r e m4 1l e tgb eap l a n eg r a p hw i t h o u t4 f a c e sa n dw i t h o u ta d j a c e n t t r i a n g l e s i f6 g 4 t h e ng c o n t a i n sa n 碍i n d u c e ds u b g r a p h u s i n gt h er e s u l to ft h e o r e m4 1 w eh a v eas u b g r a p h 瑶o fap l a n eg r a p hg a st h ea b o v ea s s u m p t i o nc o n d i t i o n t h e r e f o r e w cg i v eas h o r tp r o o fo f 4 6 a sa c o r o l l a r y4 2a n dp r o v et h ev e r t e xa r b o r i c i t yo fgi sa tm o s t2i nt h c o r e m4 3 c o r o l l a r y4 2l e tg b eac 4 f r e ep l a n eg r a p h t h e ng i s4 c h o o s a b l e t h e o r e m4 3l e tgb eaq f l e ep l a n eg r a p h t h e na a 2 n e x t l y w eu s ead i s c h a r g em e t h o da n dac o n t r a d i c t i o nm e t h o dt oc o m p l e t et h e f o l l o w i n gr e s u l t s t h e o r e m4 4l e tgb ea 伤一f r e ep l a n eg r a p h t h e na g 2 t h e o r e m4 5l e tg b ea c 5 一f r e ep l a n eg r a p h t h e n 口 g s2 t h e o r e m s4 3 4 4a n d4 5m a yb ev i e w e da st h r e ep o s i t i v es u p p o r t st ot h e a b o v eo p e nc o n j e c t u r e o nt h es q u a r eo fp l a n eg r a p h s i n 7 6 w e g n e rp r o p o s e dt h ef o l l o w i n gc o n j e c t u r e c o n j e c t u r e5 1 1 7 6 f o rap l a n eg r a p hg 舻 拿 j 讧i 篡主7 i n s p i r e db yac o n j e c t u r eo fw e g n e r w ec o n s i d e rt h ec o l o r a b i l i t yo ft h es q u a r e o ft r i a n g l e f r e ep l a n eg r a p h s s o m ek n o w nr e s u l t so nc o l o r i n g so ft h es q u a r eo fp l a n e g r a p h s t h o m a s s e n 7 1 p r o v e dt h a tt h es q u a r eo fe v e r yc u b i cp l a n eg r a p h i s7 c o l o r a b l ew h i c hw a sc o n j e c t u r e db yw e g n e r h c u v e la n dm c g u i u n e s s 3 6 s h o w e d t h a tx g 2 2 a g 2 5f o ra n yp l a n eg r a p h m o l l o ya n ds a l a v a t i p o u r 5 9 i m p r o v e dt h eu p p c rb o u n dt ox g 2 5 6 3 l q 2 1 i 7 8 a n dt ox g 2 r 竽l 2 5 u n d e ra s s u m p t i o nt h a t g 2 4 1 l i h w a n ga n dz h uf 52 p r o v e dt h a t f o rak 4 m i n o rf r e eg r a p hg x g 1 2 g 3i f2 g 3 a n d x g 2 三号p j 1i f g 4 w er i s egt od e n o t et h es e to ft r i a m g l e f r c ep l a n eg r a p h s i nt h i sd i s s e r t a t i o n w g p r o v e a l e b e s g u e t y p e t h e o r e m o n t h e s t r u c t u r e o f g r a p h s i n 9 a n d a s a c o r o l l a r y g e t a l lu p p e rb o u n do nt h ec h o i c en u m b e ro f t h es q u a r eo f 口印h si n9 w es a ya4 f a c e i ss p e c i a l i ffi si n c i d e n tw i t ht w o2 v e r t i c e s a n ds a yav e r t e x i sm a j o r i f h a sd e g r e e a tl e a s t1 5 al i g h tm a j o rv e r t e xi sa m a j o rv e r t e x w i t hd c a v g 1 3 l e t t z v a n d 诒 b et h en u m b e ro f2 v e r t i c e sa n d3 v e r t i c e sa d j a c e n tt ou r e s p e c t i v e l y t h e o r e m5 1i fg 蛋a n d6 g 2 t h e no n eo ft h ef o l l o w i n gh o l d s a a1 4 一v e r t e xi sa d j a c e n tt oa v e r t e x b i f 口i sm a j o ra n d 口i si n c i d e n tw i t ha tl e a s td v 一7s p e d a j4 f a c e s t h e n e i t h e rr 2 v d v o r0 0 相对于图的点着色来说 还有图的边着色 边着色问题是在1 8 8 0 做为f c p 相 关的问题提出的 t a i t 6 8 给出了证明f c p 问题等价于证明任何3 正则3 连通 的平面图是否3 可着色的 1 9 1 6 年 k s n i g 4 4 1 证明了任意二部图是可 边着 色的 是图的最大度 接着 v i z i n g 7 2 1 证明了一个更强的结果 任何简单图 是可 1 一边着色的 h o l y e r 3 7 第一个证明图的边着色是n p 一困难的 当然 图的边着色相当于图的线图的点着色 许多问题可以归结为图的着色问题 而图的着色问题不仅包括点着色 边着色 还有面着色 另外还有许多关于图着色的模型 见 3 9 不过人们常考虑包括列表 着色 色和 均匀着色 分数着色 边着色 强边着色 路着色等 本文主要考虑是简单图的点着色以及列表着色 所使用的正是归约方法 先考 虑图的局部子图结构然后再扩展到整个图 下面我们列出一些已知的结论 定理l z h a o 8 8 如果一个不包含从4 到 1 l 一1 幻 一圈的图g 可嵌入在可定 向曲面 欧拉特征敷口小于等于0 那么g 是3 可着色的 对于平面图的3 可着色问题 我们已知主要的结论有 定理2 s a n d e r s 和z h a o 6 5 1 或b o r o d i n 9 1 如果g 不包含从4 到9 的圈 则x g 3 定理3 b o r o d i n 1 2 如果g 不包含从4 到7 的圈 则x c 3 定理4 x u 8 2 如果g 不包含5 或7 一圈 则x c 3 而对于平面图的平方图的色数 有以下著名的猜想 w e g n e r 猜想 7 6 d 对于一个平面图g 蜘2 翁 i f 篡主7 m 关于平面圈的平方圆的色数 我们有以下结论 定理5 7 6 w c g n e r 证明了最大度为3 的平面图的平方图是8 可着色的 定理6 7 1 t h o m a s s c n 证明了3 正则的平面图的平方图是7 可着色的 定理7 4 0 j o n a s 证明了平面图的平方图是 8 a 一2 2 一可着色的 定理8 5 9 m o l l o y 和s a l a v a t i p o u rx g 2 f 警1 j 7 s 并且x g 2 i 5 a 1 2 s 当 2 4 1 定理9 5 2 l i h w a n g 和z h u 证明了对于不包含她一图子式的平面图g x g 2 a 3 i f2 a 3 并且x c 产 等j 1 i f a 4 o 2 主要结论 本文的主要结果取自攻读博士学位期间所发表及已投稿的论文 其中第2 3 和4 章的主要结果是和导师许宝刚教授合作完成的 第5 章是与戴本球和导师许宝 刚教授合作完成 第6 幸的主要是我们可以进一步考虑的问题 一 我们考虑可嵌人可定向曲面的图 欧拉特征值口 0 的列表色数 在定 理1 中 z h a o 考虑了一类可嵌入在可定向曲面 欧拉特征值口 0 并且不包含 短圈的图 z l m o 证明了任意的可嵌人在可定向曲面 欧拉特征值盯 0 并且 不包含从4 到1 1 1 2 a 圈的图是可3 着色的并且提出一个问题能够保证不包 含从4 到 e 一圈的图是可3 二着色的最小的整数 是多少 受到这个问题的 启发 我们考虑 1 1 3 a 并且得到一个l c b c s g u e 形式的定理 鲧表示可 嵌入在可定向曲面 欧拉特征值d r 0 并且不包含从4 到l l 一3 盯圈的圜 我们 得到的以下主要结果 定理1 0 如果g 是一个可嵌入在可定向曲面 欧拉特征值盯 0 的图并且不 包含相邻的3 面和从4 到 1 1 3 口 一面 那么或者g 包含一个不超过2 度的点或 者包含一个l i g h t 1 2 3 口 面 由这个定理所给出图的子图结构 我们得到 定理1 l 如果一个不包含从4 到 1 1 3 口 一圈的图g 可嵌入在可定向曲面 欧 拉特征数口 0 郝么g 的列表着色数不超过3 意味着x l g 3 二 我们考虑了平面图不包含三角形的平方图的色数 受到w e g n e r 猜想的启发 并结合定理5 6 7 j8 9 我们考虑了不 包含3 一圈的平面图的着色性 我们用岔表示不包含三角形的平面图的集合 在这 一部分 我们证明了一个l e b c s g u e 形式的定理从而得到g 的一个固定结构并且利 用这个性质我们找到了这类平面图的平方图的可选色性的一个上界 我们称一个4 一面 是特殊的如果 关联于两个2 一度点 并称一个点 是大点如果口是一 个1 5 一度点 我们称一个大点 是轻的如果d g 2 u a g 1 3 我们记r 2 口 和乃 分别为与 相邻的2 一度点和3 一度点的个数 定理1 2 5 5 设g 是一个不包含三角形的平面图并且d g 22 那么就会有 以下情形必然存在 有一个1 4 一 度点与一个2 度点相邻 b 如果口是一个大点并且相邻于至少d v 一7 特殊的 面 那么就有要么 乃 u d o 或者0 r 3 d u 一死 u 7 并且存在一个3 度点 属于口邻 集 与两个均含有2 二度点的4 面相关联 c 有p 3 x y z 其中d y 3 并且d z d z 1 5 同样 我们利用定理1 2 所得到的图子式l i g h t 的大点或特殊的b 路也得到一 个g 2 的列表着色的上界 定理1 3 5 5 如果g 是不包孓圈的平面图 则有 要么g 含有一个的船的大点 要么x 产 s a a 1 6 三 关于平面图的3 可着色 我们考虑了一类特殊的平面图的3 可着色的 在1 9 7 6 s t e i n b e r g 给出一个猜想任意不包含4 一圈和5 一圈的平面图是3 一 可着色的 而这个条件就必要的 因为已经找到不可3 一着色的平面图要么包含4 一圈或者包含5 一圈 由于直接证明的困难性 许多人考虑了一些特殊的平面图 例如定理2 3 和4 在这里 我们考虑一类平面图不包含相邻三面并且不包含 5 6 9 一圈 我们得到一个l e b c s g u e 形式的定理并验证这类平面图是可3 一着 色的 定理1 4 5 3 设g 是一个2 一连通的平面图并且不合有相邻的三角形同时也不 v 包含 5 6 9 一圈 那么就会有以下情形必然存在 1 d g o t h eb e s tc u r r e n t l yk n o w np o l y n o m i a l t i m ea p p r o x i m a t i o na l g o r i t h mi sd u e t oh a l l d s r s s o n 3 3 a n dh a so n 1 0 9l o gn 2 l 0 9 3n p e r f o r m a n c eg u a r a n t e e o b v i o u s l y c o l o r i n gap o l i t i c a lm a p i se q u i v a l e n tt oc o l o r i n gt h ev e r t i c e so fi t s d u a lp l a n a rg r a p h b u tag r a p ha l s oh a se d g e sw h i c hc a nb ec o l o r e d t h ee d g e c o l o r i n gp r o b l e mw a sp o s e di n1 8 8 0i nr e l a t i o nt ot h ef c p t h ef i r s tp a p e rt h a t d e a l tw i t ht h i ss u b j c e tw a sw r i t t e nb yt a i t 6 8 i nh i sp a p e rt a i tp r o v e dt h a tt h e f c pi se q u i v a l e n tt ot h ep r o b l e mo fe d g e c o l o r i n ge v e r yp l a n a r3 c o n n e c t e dc u b i c g r a p hw i t h3c o l o r s i n1 9 1 6k 6 n i g 4 4 p r o v e dt h a te v e r yb i p a r t i t eg r a p hc a nb e a e d g e c o l o r e d w h e r e i st h em a x i m u mv e r t e xd e g r e e l a t e r v i z i n g 7 2 p r o v e da v e r ys t r o n gr e s u l t a s s e r t i n gt h a te v e r ys i m p l eg r a p hc a nb ee d g e c o l o r e dw i t h 1 c o l o r s i no t h e rw o r d s t h i sr e s u l ts a y st h a tt h ep r o b l e mi sa p p r o x i m a t ew i t ha l l a b s o l u t ee r r o rg u a r a n t e eo f1o ns i m p l e 舻印h s t h ef i r s tp r o o fo fn p h a r d n c s so f e d g e c o l o r i n gi sd u et oh o l y e r 37 o fc o n r s e e d g e c o l o r i n gc a nb cr e g a r d e da sa s p e c i a lc a s eo fv e r t e x c o l o r i n g n a m e l yt h ep r o b l e mo fc o l o r i n gt h ev e r t i c e so ft h e c o r r e s p o n d i n gl i n eg r a p h 1 4 m o d e l so fg r a p h c o l o r i n g f o rm a n yp r o b l e m sw h i c hc a n n o tb ee a s i l yr e d u c e dt oc l a s s i c a lc o l o r i n go ft h e v e r t i c e so re d g e so fa na s s o c i a t e dg r a p hw ei n t r o d u c em o r eg e n e r a l n o n c l a s s i c a l m o d e l so fc o l o r i n g i ng e n e r a l t h ec o l o r i n go fa g r a p hc a nc o n s i s to fa s s i g n i n gc o l o r s t ov e r t i c e s e d g e s a n df a c e so fap l a n eg r a p ho ra n yc o m b i n a t i o no ft h ea b o v es e t ss i m u l t a n e o u s l y m o r e o v e r f o re a c hm o d e lo fc o l o r i n gw eh a v ev a r i o u sr u l e so nl e g a l i t y o ro p t i m a l i t yo fs o l u t i o n s n o n c l a s s i c a lm o d e l sc a ni n t r o d u c ea d d i t i o n a lc o n d i t i o n s o ft h eu s a g eo fc o l o r sb ym a k i n gi tp o s s i b l et ou m o r et h a no n ec o l o rp e re l e m e n t p e r m i t t i n gt h es p l i t t i n go fc o l o r si n t of r a c t i o n so ra d m i t t i n gt h es w a t h i n go fc o l o r s i ng e n e r a l t h e r ea r es e v e r a ld o z e ng r a p hc o l o r i n gm o d e l sd e s c r i b e di nt h el i t e r a t u r e 3 9 h o w c v e r o n l yad o z e no rs oa r er e l e v a n t f r o map r a c t i c a lp o i n to fv i e w t h e s ei n c l u d el i s tc o l o r i n g c h r o m a t i cs u mc o l o r i n g e q u i t a b l ec o l o r i n g f r a c t i o n a l c o l o r i n g r a n kc o l o r i n g h a r m o n i o u sc o l o r i n g r a d i oc o l o r i n g i n t e r v a lc o l o r i n ga n d e d g e c o l o r i n g s t r o n gc o l o r i n ga n dp a t hc o l o r i n g m o s to ft h e md c a lw i t hv e r t e x c o l o r i n ga n de d g e c o l o r i n g b u t8 0 m eo ft h e ma r ed e f i n e do n l yf o rv e r t e x c o l o r i n g o g h a r m o n i o u s o re d g e c o l o r i n g e g i n t e r v a l i nt h i sp a p e r w ec o n s i d e ri n d e t a i lt h em o d e i so fc o l o r i n g w h i c ha r em o s tu s e f u lf r o map r a c t i c a lp o i n to fv i e w t h o s ei n c l u d e v c r t cc o l o r i n g l i s tc o l o r i n g l p q 一c o l o r i n g 1 5a p p l i c a t i o n so fg r a p hc o l o r i n g 1 1 1 t i m et a b l i n ga n d s c h e d u l i n gm a n ys c h e d u l i n gp r o b l e m si n v o l v ea l l o w i n g f o ran u m b c ro fp a l r w i s er e s t r i c t i o n so nw h i c hj o b sc a nb ed o n es i m u l t a n e o u s l y f o r i n s t a n c e i na t t e m p t i n gt os c h e d u l ec l a s s e sa tau n i v e r s i t y t w oc o u r s e 8t a u g h tb y t h es a m ef a c u l t ym e m b e rc a n n o tb es c h e d u l e df o rt h es a m et i m es l o t s i m i l a r l y t w o c o u r s et h a ta r er e q u i r e db yt h es a m eg r o u po fs t u d e n t sa l s os h o u l dn o tc o n f l i c t t h e p r o b l e mo fd e t e r m i n i n gt h em i n i m u mn u m b e ro ft i m es l o t sn e e d e ds u b j e c tt ot h e s e r e s t r i c t i o n si sag r a p hc o l o d n gp r o b l e m t h i sp r o b l e mh a sb e e ns t u d i e db ym a n y r e s e a r c h e r s i n c l u d i n gl e i g h t o n 5 0 o p s u ta n dr o b e r t s 6 2 a n dd ew e r r a 2 3 2 f r e q u e n c ya s s i g n m e n tg a m s t 2 6 e x a m i n e sap r o b l e mi na s s i g n i n gf r e q u e n c i e st om o b i l er a d i o sa n do t h e rl l s c r so ft h ee l e c t r o m a g n e t i cs p e c t r u m i nt h e s i m p l e s tc a s e t w oc u s t o m e r st h a ta r es u f f i c i e n t l yc l o s em u s tb ea s s i g n e dd i f f e r e n t f r e q u e n c i e s w h i l et h o s en l a ta r ed i s t a n tc a ns h a r ef r e q u e n c i e s t h ep r o b l e mo f m i n i m i z i n gt h en u m b e ro ff r e q u e n c i e si st h e nag r a p hc o l o r i n gp r o b l e m 3 r e g i s t e ra l l o c a t i o no n ev e r ya c t i v ea p p l i c a t i o nf o rg r a p hc o l o r i n gi s r e g i s t e ra l l o c a t i o n t h er e g i s t e ra l l o c a t i o np r o b l e mi st oa s s i g nv a r i a b l e st oal i m i t e d n u m b e ro fh a r d w a r er e g i s t e r sd u r i n gp r o g r a me x e c u t i o n v a r i a b l e si nr e s t e mc a n b ea c c e s s e dm u c hq u i c k e rt h a nt h o s en o ti nr e s t e m t y p i c a l l y h o w e v e r t h e