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

被引：5

作者：

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

共 9 条

[1] Hall ratio of the Mycielski graphs [J].

Cropper, Mathew ;

Gyarfas, Andras ;

Lehel, Jeno .

DISCRETE MATHEMATICS, 2006, 306 (16) :1988-1990

[2] Relations among the fractional chromatic, choice, Hall, and Hall-condition numbers of simple graphs [J].

Daneshgar, A ;

Hilton, AJW ;

Johnson, PD .

DISCRETE MATHEMATICS, 2001, 241 (1-3) :189-199

[3]

HILTON AJW, 1973, B LOND MATH SOC, V5, P302, DOI DOI 10.1112/BLMS/5.3.302

[4] Coloring the vertices of a graph with measurable sets in a probability space [J].

Johnson, PD ;

Rodger, CA .

EUROPEAN JOURNAL OF COMBINATORICS, 2005, 26 (02) :251-257

[5]

JOHNSON PD, 1994, ARS COMBINATORIA, V37, P183

[6]

Scheinerman ER., 2011, Fractional Graph Theory: A Rational Approach to the Theory of Graphs

[7]

SCOTT SH, 1975, THESIS U READING REA

[8] Asymptotic values of the Hall-ratio for graph powers [J].

Simonyi, Gabor .

DISCRETE MATHEMATICS, 2006, 306 (19-20) :2593-2601

[9]

West D. B., 2006, INTRO GRAPH THEORY

← 1 →