重庆理工大学学报（自然科学版）
重慶理工大學學報（自然科學版）
중경리공대학학보（자연과학판）
JOURNAL OF CHONGQING INSTITUTE OF TECHNOLOGY
2011年
3期
108-110,117
,共4页
无圈着色%无圈色数%最大度
無圈著色%無圈色數%最大度
무권착색%무권색수%최대도
图G的无圈着色是指正常的顶点着色,同时图中任意的圈均不着双色.换句话说,图G的无圈着色是指G的正常顶点着色并且由任意两类颜色导出的子图G'为森林.图G的无圈色数是指在G的所有无圈着色中使用色数的最小者,这里用a(G)表示.证明了最大度为5的非正则图的无圈色数最多为8,并由此推出含有割边或割点的五正则图均可以用8种颜色进行无圈着色.
圖G的無圈著色是指正常的頂點著色,同時圖中任意的圈均不著雙色.換句話說,圖G的無圈著色是指G的正常頂點著色併且由任意兩類顏色導齣的子圖G'為森林.圖G的無圈色數是指在G的所有無圈著色中使用色數的最小者,這裏用a(G)錶示.證明瞭最大度為5的非正則圖的無圈色數最多為8,併由此推齣含有割邊或割點的五正則圖均可以用8種顏色進行無圈著色.
도G적무권착색시지정상적정점착색,동시도중임의적권균불착쌍색.환구화설,도G적무권착색시지G적정상정점착색병차유임의량류안색도출적자도G'위삼림.도G적무권색수시지재G적소유무권착색중사용색수적최소자,저리용a(G)표시.증명료최대도위5적비정칙도적무권색수최다위8,병유차추출함유할변혹할점적오정칙도균가이용8충안색진행무권착색.
