边染色图中的单色子图研究.pdf

《边染色图中的单色子图研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、边染色图中的单色子图研究SomeStudyonMonochromaticSubgraphsinEdgeColoredGraphs作者指7导老师学位类别学科专业学位授予单位论文提交日期．2Q曼2年5月上日边染色图中的单色子图研究摘要边染色图中的单色子图问题是目前图论研究领域的热点问题．Bollob缸和Gy磊rfh猜想当n≥4k一3时，任意的2一边染色完全图％中都包含一个阶至少为n一2k+2的单色南．连通子图．当k=2，3时此猜想已经被证明是正确的，Liu等人证明了礼≥13k一15时任意的2．边染色完全图％都包含一个阶至少为n一2k+2的单色七一连通子图．Fujita等人证明了当礼≥

2、6．5(k一1)时结论成立．一些学者将这个问题推广到完全多部图中，并得到若干结果．本文中，我们主要考虑了边染色图中的单色七．连通子图阶的问题．首先，研究了完全图％中的七．连通单色子图问题，我们完整刻画了完全图‰(礼≥13k一15)的所有2一边染色，使得完全图‰中的单色七一连通子图的阶最多为佗一2k+2．然后，我们研究了2-边染色完全二部图和完全多部图中的2．连通单色子图的阶，给出了其精确值或者上下界，且其中上下界相差最多为1．最后，对于完全图我们还证明了当n≥13时，任意的2。边染色完全图％，如果％中有一个最大阶为n一2k+2的单色后．连通子图(七=2，3)，那么％中必有一个阶至

3、少为n一6的单色4一连通子图．关键词：单色子图；尼．连通子图；2一边染色；完全图SOMESTUDY0NMONOCHROMATlCSUBGRAPHSINEDGECOLOREDGRAPHSABSTRACTThestudyofmonochromaticsubgraphsinedge-coloredgraphsisalwaysahottopicgraphtheory．Bollob矗sandGy磊rf瓠conjecturedthatfor礼≥4k一3every2-edge-coloringof珞containsamonochromatick-connectedsubgraphwithatl

4、east礼一2k+2vertices．ItWasprovedthattheconjectureholdsfork=2．3．Liuetai．provedthatevery2-edge-coloringof％containsamonochromatic缸connectedsubgraphwithatleastn一2k+2verticeswhenn≥13k一15．Fujitaeta1．provedthatthesameresultholdsfor扎≥6．5(k一1)．Researchersconsideredtheanaloguequestionincompletemultiparti

5、tegraphsandgavesomeboundsforthequestion．Inthisthesis，wefocusontheorderofmonochromatick-connectedsubgraphsin2-edge-coloredgraphs．InChapter2，weconsiderthemonochromatick-connectedsubgraphsin2．edge—coloredcompletegraph‰．Wecharacterizeallthe2-edge-coloringsof％whereeachmonochromatick-connectedsubgr

6、aphhasatmost死一2k+2verticesfor扎≥13k一15．InChapter3，weconsidertheorderofmonochromatic2-connectedsubgraphsincompletemultipartitegraphs．Wegivesomeboundsfortheorder．Moreover，theupperandlowerboundsdifferbyatmostoneFinally,weconsidertheorderofmonochromatic4-connectedsubgraphsin2一edge-coloredK4．Weshow

7、thatifeachmonochromatick-connected(k=2，3)IIABSTRACTsubgraphhasatmostn一2k+2verticesin2-edge-colored虬(死≥13)，thenthereexistsamonochromatic4-connectedsubgraphwithatleast咒一6vertices．KEYWoRDS：monochromaticsubgraph，k-connectedsubgraph，2-edge-colorin