Choosability of the square of planar subcubic graphs with large girth

被引：19
|
作者：
Havet, F. [1 ]
机构：
[1] INRIA Sophia Antipolis, UNSA, CNRS, Projet Mascotte, F-06902 Sophia Antipolis, France
来源：
DISCRETE MATHEMATICS | 2009年 / 309卷 / 11期
关键词：
List colouring; Square of a graph; Bounded density; Planar graph;
D O I：
10.1016/j.disc.2007.12.100
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We show that the choice number of the square of a subcubic graph with maximum average degree less than 18/7 is at most 6. As a corollary, we get that the choice number of the square of a subcubic planar graph with girth at least 9 is at most 6. We then show that the choice number of the square of a subcubic planar graph with girth at least 13 is at most 5. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码：3553 / 3563
页数：11
相关论文
共 50 条
  • [31] Odd Induced Subgraphs in Planar Graphs with Large Girth
    Rao, Mengjiao
    Hou, Jianfeng
    Zeng, Qinghou
    GRAPHS AND COMBINATORICS, 2022, 38 (04)
  • [32] Infinite highly connected planar graphs of large girth
    Georgakopoulos, A.
    ABHANDLUNGEN AUS DEM MATHEMATISCHEN SEMINAR DER UNIVERSITAT HAMBURG, 2006, 76 (1): : 235 - 245
  • [33] Large induced forests in planar graphs with girth 4
    Dross, Francois
    Montassier, Mickael
    Pinlou, Alexandre
    DISCRETE APPLIED MATHEMATICS, 2019, 254 : 96 - 106
  • [34] Acyclic chromatic indices of planar graphs with large girth
    Wang, Weifan
    Shu, Qiaojun
    Wang, Kan
    Wang, Ping
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (12) : 1239 - 1253
  • [35] Odd Induced Subgraphs in Planar Graphs with Large Girth
    Mengjiao Rao
    Jianfeng Hou
    Qinghou Zeng
    Graphs and Combinatorics, 2022, 38
  • [36] The 3-choosability of plane graphs of girth 4
    Lam, PCB
    Shiu, WC
    Song, ZM
    DISCRETE MATHEMATICS, 2005, 294 (03) : 297 - 301
  • [37] A Note on Group Choosability of Graphs with Girth at least 4
    G. R. Omidi
    Graphs and Combinatorics, 2011, 27 : 269 - 273
  • [38] STRONG CHROMATIC INDEX OF PLANAR GRAPHS WITH LARGE GIRTH
    Chang, Gerard Jennhwa
    Montassier, Mickael
    Pecher, Arnaud
    Raspaud, Andre
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2014, 34 (04) : 723 - 733
  • [39] Induced Matchings in Subcubic Planar Graphs
    Kang, Ross J.
    Mnich, Matthias
    Mueller, Tobias
    ALGORITHMS-ESA 2010, PT II, 2010, 6347 : 112 - +
  • [40] On the total choosability of planar graphs and of sparse graphs
    Chang, Gerard Jennhwa
    Hou, Jianfeng
    Roussel, Nicolas
    INFORMATION PROCESSING LETTERS, 2010, 110 (20) : 849 - 853
12345