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 条

[31] A smaller upper bound for the list injective chromatic number of planar graphs [J].

Chen, Hongyu ;

Zhang, Li .

AIMS MATHEMATICS, 2025, 10 (01) :289-310

[32] Injective Chromatic Number of Outerplanar Graphs [J].

Mozafari-Nia, Mahsa ;

Omoomi, Behnaz .

TAIWANESE JOURNAL OF MATHEMATICS, 2018, 22 (06) :1309-1320

[33] Injective choosability of planar graphs of girth five and six [J].

Li, Rui ;

Xu, Baogang .

DISCRETE MATHEMATICS, 2012, 312 (06) :1260-1265

[34] On the fractional chromatic number, the chromatic number, and graph products [J].

Klavzar, S ;

Yeh, HG .

DISCRETE MATHEMATICS, 2002, 247 (1-3) :235-242

[35] A note on generalized chromatic number and generalized girth [J].

Bollobás, B ;

West, DB .

DISCRETE MATHEMATICS, 2000, 213 (1-3) :29-34

[36] On a construction of graphs with high chromatic capacity and large girth [J].

Zhou, Bing .

DISCRETE MATHEMATICS, 2010, 310 (17-18) :2452-2454

[37] On the packing number of antibalanced signed simple planar graphs of negative girth at least 5 [J].

Naserasr, Reza ;

Yu, Weiqiang .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2024, 47 (02)

[38] On the packing number of antibalanced signed simple planar graphs of negative girth at least 5 [J].

Reza Naserasr ;

Weiqiang Yu .

Journal of Combinatorial Optimization, 2024, 47

[39] PRECISE UPPER BOUND FOR THE STRONG EDGE CHROMATIC NUMBER OF SPARSE PLANAR GRAPHS [J].

Borodin, Oleg V. ;

Ivanova, Anna O. .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2013, 33 (04) :759-770

[40] The hub number, girth and Mycielski graphs [J].

Liu, Xiaoping ;

Dang, Zhilan ;

Wu, Baoyindureng .

INFORMATION PROCESSING LETTERS, 2014, 114 (10) :561-563

← 1 2 3 4 5 →