Chromatic-choosability of the power of graphs

Title
Chromatic-choosability of the power of graphs
Author(s)
권영수김석진[김석진]박보람[박보람]
Issue Date
201501
Publisher
ELSEVIER SCIENCE BV
Citation
DISCRETE APPLIED MATHEMATICS, v.180, pp.120 - 125
Abstract
The kth power G(k) of a graph G is the graph defined on V(G) such that two vertices u and v are adjacent in G(k) if the distance between u and v in G is at most k. Let chi(H) and chi e(H) be the chromatic number and the list chromatic number of H, respectively. A graph H is called chromatic-choosable if chi e(H) = chi(H). It is an interesting problem to find graphs that are chromatic-choosable. A natural question raised by Xuding Zhu (2013) is whether there exists a constant integer k such that G(k) is chromatic-choosable for every graph G. Motivated by the List Total Coloring Conjecture, Kostochka and Woodall (2001) asked whether G(2) is chromatic-choosable for every graph G. Kim and Park (2014) solved Kostochka and Woodall's conjecture in the negative by finding a family of graphs G whose squares are complete multipartite graphs with partite sets of unbounded size. In this paper, we answer Zhu's question by showing that for every integer k >= 2, there exists a graph G such that G(k) is not chromatic-choosable. Moreover, for any fixed k we show that the value chi e(G(k)) - chi(G(k)) can be arbitrarily large. (C) 2014 Elsevier B.V. All rights reserved.
URI
http://hdl.handle.net/YU.REPOSITORY/33656http://dx.doi.org/10.1016/j.dam.2014.08.004
ISSN
0166-218X
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