Girth and fractional chromatic number of planar graphs

被引：0

作者：

Pirnazar, A ^{[1
]}

Ullman, DH ^{[1
]}

机构：

[1] George Washington Univ, Dept Math, Washington, DC 20052 USA

来源：

JOURNAL OF GRAPH THEORY | 2002年 / 39卷 / 03期

关键词：

fractional chromatic number; girth; planar graphs; four-color theorem;

D O I：

10.1002/jgt.10024

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In 1959, even before the Four-Color Theorem was proved, Grotzsch showed that planar graphs with girth at least 4 have chromatic number at the most 3. We examine the fractional analogue of this theorem and its generalizations. For any fixed girth, we ask for the largest possible fractional chromatic number of a planar graph with that girth, and we provide upper and lower bounds for this quantity. (C) 2002 Wiley Periodicals, Inc.

引用

页码：201 / 217

页数：17

共 50 条

[21] Fractional arboricity, strength and eigenvalues of graphs with fixed girth or clique number [J].

Hong, Zhen-Mu ;

Xia, Zheng-Jiang ;

Lai, Hong-Jian ;

Liu, Ruifang .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2021, 611 :135-147

[22] More results on r-inflated graphs: Arboricity, thickness, chromatic number and fractional chromatic number [J].

Albertson, Michael O. ;

Boutin, Debra L. ;

Gethner, Ellen .

ARS MATHEMATICA CONTEMPORANEA, 2011, 4 (01) :5-24

[23] 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

[24] The performance of an upper bound on the fractional chromatic number of weighted graphs [J].

Ganesan, Ashwin .

APPLIED MATHEMATICS LETTERS, 2010, 23 (05) :597-599

[25] The fractional chromatic number of triangle-free graphs with Δ ≤ 3 [J].

Lu, Linyuan ;

Peng, Xing .

DISCRETE MATHEMATICS, 2012, 312 (24) :3502-3516

[26] THE FRACTIONAL CHROMATIC NUMBER OF K\bfDelta-FREE GRAPHS [J].

Hu, Xiaolan ;

Peng, Xing .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (04) :2486-2507

[27] Equitable coloring planar graphs with large girth [J].

Wu, Jianliang ;

Wang, Ping .

DISCRETE MATHEMATICS, 2008, 308 (5-6) :985-990

[28] Tight relation between the circular chromatic number and the girth of series-parallel graphs [J].

Pan, ZS ;

Zhu, XD .

DISCRETE MATHEMATICS, 2002, 254 (1-3) :393-404

[29] The circular chromatic index of graphs of high girth [J].

Kaiser, Tomas ;

Kral, Daniel ;

Skrekovski, Riste ;

Zhu, Xuding .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (01) :1-13

[30] LIGHT GRAPHS IN PLANAR GRAPHS OF LARGE GIRTH [J].

Hudak, Peter ;

Macekova, Maria ;

Madaras, Tomas ;

Siroczki, Pavol .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2016, 36 (01) :227-238

← 1 2 3 4 5 →