THE FRACTIONAL CHROMATIC NUMBER OF K\bfDelta-FREE GRAPHS

被引：0

作者：

Hu, Xiaolan ^{[1
,2
]}

Peng, Xing ^{[3
]}

机构：

[1] Cent China Normal Univ, Sch Math & Stat, Wuhan 430079, Peoples R China

[2] Cent China Normal Univ, Hubei Key Lab Math Sci, Wuhan 430079, Peoples R China

[3] Anhui Univ, Ctr Pure Math, Sch Math Sci, Hefei 230601, Peoples R China

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2023年 / 37卷 / 04期

基金：

中国国家自然科学基金;

关键词：

coloring; fractional coloring; fractional chromatic number; TRIANGLE-FREE GRAPHS; INDEPENDENCE RATIO; MAXIMUM DEGREE; DELTA;

D O I：

10.1137/21M1440037

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

For a simple graph G, let \chif (G) be the fractional chromatic number of G. In this paper, we aim to establish upper bounds on \chif (G) for those graphs G with restrictions on the clique number. Namely, we prove that for \Delta \geq 4, if G has maximum degree at most \Delta and is K =-free, then \chif (G) \leq \Delta -81 unless G = C82 or G = C5 \boxtimes K2. This improves the result in [A. King, L. Lu, and X. Peng, SIAM J. Discrete Math., 26 (2012), pp. 452--471] for \Delta \geq 4 and the result in [K. Edwards and A. D. King, SIAM J. Discrete Math., 27 (2013), pp. 1184--1208] for \Delta \in {6, 7, 8}.

引用

页码：2486 / 2507

页数：22

共 21 条

[1]

[Anonymous], 1978, P 9 SE C COMBINATORI

[2] UPPER BOUND OF A GRAPHS CHROMATIC NUMBER, DEPENDING ON GRAPHS DEGREE AND DENSITY [J].

BORODIN, OV ;

KOSTOCHKA, AV .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1977, 23 (2-3) :247-250

[3] Subcubic triangle-free graphs have fractional chromatic number at most 14/5 [J].

Dvorak, Z. ;

Sereni, J. -S. ;

Volec, J. .

JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 2014, 89 :641-662

[4]

DVORv Z., 2022, arXiv

[5] BOUNDING THE FRACTIONAL CHROMATIC NUMBER OF KΔ-FREE GRAPHS [J].

Edwards, Katherine ;

King, Andrew D. .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (02) :1184-1208

[6] The fractional chromatic number of triangle-free subcubic graphs [J].

Ferguson, David G. ;

Kaiser, Tomas ;

Kral, Daniel .

EUROPEAN JOURNAL OF COMBINATORICS, 2014, 35 :184-220

[7]

Gallai T., 1963, Publ. Math. Inst. Hung. Acad. Sci., V8, P265

[8] Edge density and independence ratio in triangle-free graphs with maximum degree three [J].

Griggs, J ;

Murphy, O .

DISCRETE MATHEMATICS, 1996, 152 (1-3) :157-170

[9] THE FRACTIONAL CHROMATIC NUMBER OF GRAPHS OF MAXIMUM DEGREE AT MOST THREE [J].

Hatami, Hamed ;

Zhu, Xuding .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (04) :1762-1775

[10] A new proof of the independence ratio of triangle-free cubic graphs [J].

Heckman, CC ;

Thomas, R .

DISCRETE MATHEMATICS, 2001, 233 (1-3) :233-237

← 1 2 3 →