The fractional chromatic number, the Hall ratio, and the lexicographic product

被引：4
|
作者：
Johnson, P. D., Jr. [1 ]
机构：
[1] Auburn Univ, Dept Math & Stat, Auburn, AL 36849 USA
来源：
DISCRETE MATHEMATICS | 2009年 / 309卷 / 14期
关键词：
Fractional chromatic number; Hall ratio; Lexicographic product; GRAPH;
D O I：
10.1016/j.disc.2008.05.049
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Let x(f) denote the fractional chromatic number and p the Hall ratio, and let the lexicographic product of G and H be denoted GlexH. Main results: (i) rho(GlexH) <= chi(f) (G)rho(H); (ii) if rho(G) = chi(f) (G) then rho(GlexH) = rho(G)rho(H) for all H; (iii) chi(f) - rho is unbounded. In addition, the question of how big chi(f)/rho can be is discussed. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码：4746 / 4749
页数：4
相关论文
共 50 条
  • [1] Game chromatic number of lexicographic product graphs
    Alagammai, R.
    Vijayalakshmi, V.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2015, 12 (2-3) : 216 - 220
  • [2] ON LOCAL ANTIMAGIC CHROMATIC NUMBER OF LEXICOGRAPHIC PRODUCT GRAPHS
    Lau, G. -C.
    Shiu, W. C.
    ACTA MATHEMATICA HUNGARICA, 2023, 169 (1) : 158 - 170
  • [3] On the local antimagic chromatic number of the lexicographic product of graphs
    Lau, Gee-Choon
    Shiu, Wai Chee
    Kanthavadivel, Premalatha
    Zhang, Ruixue
    Movirichettiar, Nalliah
    DISCRETE MATHEMATICS LETTERS, 2023, 11 : 76 - 83
  • [4] On local antimagic chromatic number of lexicographic product graphs
    G.-C. Lau
    W. C. Shiu
    Acta Mathematica Hungarica, 2023, 169 : 158 - 170
  • [5] Total Chromatic Number for Certain Classes of Lexicographic Product Graphs
    Sandhiya, T. P.
    Geetha, J.
    Somasundaram, K.
    COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2024, 9 (02) : 233 - 240
  • [6] On the ultimate lexicographic Hall-ratio
    Toth, Agnes
    DISCRETE MATHEMATICS, 2009, 309 (12) : 3992 - 3997
  • [7] On the fractional chromatic number, the chromatic number, and graph products
    Klavzar, S
    Yeh, HG
    DISCRETE MATHEMATICS, 2002, 247 (1-3) : 235 - 242
  • [8] The number of spanning trees in a new lexicographic product of graphs
    Liang Dong
    Li Feng
    Xu ZongBen
    SCIENCE CHINA-INFORMATION SCIENCES, 2014, 57 (11) : 1 - 9
  • [9] The number of spanning trees in a new lexicographic product of graphs
    Dong Liang
    Feng Li
    ZongBen Xu
    Science China Information Sciences, 2014, 57 : 1 - 9
  • [10] The number of spanning trees in a new lexicographic product of graphs
    LIANG Dong
    LI Feng
    XU ZongBen
    Science China(Information Sciences), 2014, 57 (11) : 57 - 65
12345