CAJ | 학술논문

如果一个图G的选择数等于它的色数,则称该图G是色可选择的.在2002年,Ohba给出如下猜想:每一个顶点个数小于等于2x(G)+1的图G是色可选择的.容易发现Ohba猜想成立的条件是当且仅当它对完全多部图成立,但是目前只是就某些特殊的完全多部图的图类证明了Ohba猜想的正确性.在本文我们证明图K6,3,2*(k-6),1*4(k≥6)是色可选择的,从而对图K6,3,2*(k-6),1*4(k≥6)和它们的所有完全k-部子图证明了Ohba猜想成立.
여과일개도G적선택수등우타적색수,칙칭해도G시색가선택적.재2002년,Ohba급출여하시상:매일개정점개수소우등우2x(G)+1적도G시색가선택적.용역발현Ohba시상성립적조건시당차부당타대완전다부도성립,단시목전지시취모사특수적완전다부도적도류증명료Ohba시상적정학성.재본문아문증명도K6,3,2*(k-6),1*4(k≥6)시색가선택적,종이대도K6,3,2*(k-6),1*4(k≥6)화타문적소유완전k-부자도증명료Ohba시상성립.
A graph G is called to be chromatic choosable if its choice number is equal to its chromatic number. In 2002, Ohba conjectured that every graph G with 2x(G) + 1 or fewer vertices is chromatic choosable. It is easy to see that Ohba's conjecture is true if and only if it is true for complete multipartite graphs. But at present only for some special cases of complete multipartite graphs, Ohba's conjecture have been verified. In this paper we show that graphs K6,3,2*(k-6),1*4 (k ≥ 6) is chromatic choosable and hence Ohba's conjecture is true for the graphs K6,3,2*(k-6),1*4 and all complete k-partite subgraphs of them.