On-line list colouring of complete multipartite graphs

Title
On-line list colouring of complete multipartite graphs
Author(s)
권영수김석진[김석진]Daphne Der-Fen Liu[Daphne Der-Fen Liu]Xuding Zhu[Xuding Zhu]
Keywords
INDEPENDENCE NUMBER; OHBAS CONJECTURE
Issue Date
201202
Publisher
ELECTRONIC JOURNAL OF COMBINATORICS
Citation
ELECTRONIC JOURNAL OF COMBINATORICS, v.19, no.1
Abstract
The Ohba Conjecture says that every graph G with vertical bar V(G)vertical bar <= 2 chi(G) + 1 is chromatic choosable. This paper studies an on-line version of Ohba Conjecture. We prove that unlike the off-line case, for k >= 3, the complete multipartite graph K-2 star(k-1),K-3 is not on-line chromatic-choosable. Based on this result, the on-line version of Ohba Conjecture is modified as follows: Every graph G with vertical bar V(G)vertical bar <= 2 chi(G) is on-line chromatic choosable. We present an explicit strategy to show that for any positive integer k,the graph K-2 star k is on-line chromatic-choosable. We then present a minimal function g for which the graph K-2 star(k-1),K-3 is on-line g-choosable.
URI
http://hdl.handle.net/YU.REPOSITORY/29953
ISSN
1077-8926
Appears in Collections:
이과대학 > 수학과 > Articles
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE