English  |  正體中文  |  简体中文  |  Items with full text/Total items : 52047/87178 (60%)
Visitors : 8694410      Online Users : 246
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    Please use this identifier to cite or link to this item: http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/56752

    Title: Multiple Coloring of Cone Graphs
    Authors: Pan, Zhishi;Zhu, Xuding
    Contributors: 淡江大學數學學系
    Keywords: Multiple coloring;Cone graphs;Mycielski graphs;Fractional chromatic number;Kneser graphs
    Date: 2010
    Issue Date: 2011-09-07 11:54:53 (UTC+8)
    Publisher: Philadelphia: Society for Industrial and Applied Mathematics
    Abstract: A k-fold coloring of a graph assigns to each vertex a set of k colors, and color sets assigned to adjacent vertices are disjoint. The kth chromatic number Xk(G) of a graph G is the minimum total number of colors needed in a k-fold coloring of G. Given a graph G = (V, E) and an integer m ≥ 0, the m-cone of G, denoted by µm(G), has vertex set (V x {0,1,… , m}) U {u} in which u is adjacent to every vertex of V x {m}, and (x, i)(y, j) is an edge if xy ∈ E and i = j = 0 or xy ∈ E and |i - j| = 1. This paper studies the kth chromatic number of the cone graphs. An upper bound for Xk(µm(G) in terms of Xk(G), k, and m are given. In particular, it is proved that for any graph G, if m ≥ 2k, then Xk(µm(G)) ≤ Xk(G) + 1. We also find a surprising connection between the kth chromatic number of the cone graph of G and the circular chromatic number of G. It is proved that if Xk(G)/k > Xc((G) and Xk(G) is even, then for sufficiently large m, Xk(µm(G)) = Xk(G). In particular, if X(G) > Xc(G) and X(G) is even, then for sufficiently large m, X(µm(G)) = X(G).
    Relation: SIAM Journal on Discrete Mathematics 24(4), pp.1515-1526
    DOI: 10.1137/070691486
    Appears in Collections:[數學學系暨研究所] 期刊論文

    Files in This Item:

    File Description SizeFormat
    0895-4801_24(4)p1515-1526.pdf241KbAdobe PDF133View/Open

    All items in 機構典藏 are protected by copyright, with all rights reserved.

    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - Feedback