Choosability in signed planar graphs

被引：14
|
作者：
Jin, Ligang [1 ]
Kang, Yingli [1 ,2 ]
Steffen, Eckhard [1 ]
机构：
[1] Univ Paderborn, Paderborn Inst Adv Studies Comp Sci & Engn, D-33098 Paderborn, Germany
[2] Int Grad Sch Dynam Intelligent Syst, Paderborn, Germany
来源：
EUROPEAN JOURNAL OF COMBINATORICS | 2016年 / 52卷
关键词：
CYCLES;
D O I：
10.1016/j.ejc.2015.10.001
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
This paper studies the choosability of signed planar graphs. We prove that every signed planar graph is 5-choosable and that there is a signed planar graph which is not 4-choosable while the unsigned graph is 4-choosable. For each k is an element of {3, 4, 5, 6}, every signed planar graph without circuits of length k is 4-choosable. Furthermore, every signed planar graph without circuits of length 3 and of length 4 is 3-choosable. We construct a signed planar graph with girth 4 which is not 3-choosable but the unsigned graph is 3-choosable. (C) 2015 Elsevier Ltd. All rights reserved.
引用
收藏
页码：234 / 243
页数：10
相关论文
共 50 条
  • [41] On Choosability with Separation of Planar Graphs Without Adjacent Short Cycles
    Min Chen
    Ko-Wei Lih
    Weifan Wang
    Bulletin of the Malaysian Mathematical Sciences Society, 2018, 41 : 1507 - 1518
  • [42] NSD Total Choosability of Planar Graphs with Girth at Least Four
    Han, Xue
    Wang, Jihui
    Qiu, Baojian
    PROCEEDINGS OF 2016 INTERNATIONAL CONFERENCE ON MODELING, SIMULATION AND OPTIMIZATION TECHNOLOGIES AND APPLICATIONS (MSOTA2016), 2016, 58 : 78 - 80
  • [43] A note on the acyclic 3-choosability of some planar graphs
    Hocquard, Herve
    Montassier, Mickael
    Raspaud, Andre
    DISCRETE APPLIED MATHEMATICS, 2010, 158 (10) : 1104 - 1110
  • [44] On 3-choosability of planar graphs without certain cycles
    Zhang, Haihui
    Sun, Zhiren
    INFORMATION PROCESSING LETTERS, 2008, 107 (3-4) : 102 - 106
  • [45] IMPROPER CHOOSABILITY OF PLANAR GRAPHS WITHOUT 4-CYCLES
    Wang, Yingqian
    Xu, Lingji
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (04) : 2029 - 2037
  • [46] A note on the not 3-choosability of some families of planar graphs
    Montassier, M
    INFORMATION PROCESSING LETTERS, 2006, 99 (02) : 68 - 71
  • [47] Choosability with union separation of triangle-free planar graphs
    Hou, Jianfeng
    Zhu, Hongguo
    DISCRETE MATHEMATICS, 2020, 343 (12)
  • [48] On (2, r)-choosability of planar graphs without short cycles
    Hou, Jianfeng
    Zhu, Hongguo
    APPLIED MATHEMATICS AND COMPUTATION, 2023, 444
  • [49] (4,2)-Choosability of Planar Graphs with Forbidden Structures
    Berikkyzy, Zhanar
    Cox, Christopher
    Dairyko, Michael
    Hogenson, Kirsten
    Kumbhat, Mohit
    Lidicky, Bernard
    Messerschmidt, Kacy
    Moss, Kevin
    Nowak, Kathleen
    Palmowski, Kevin F.
    Stolee, Derrick
    GRAPHS AND COMBINATORICS, 2017, 33 (04) : 751 - 787
  • [50] On Choosability with Separation of Planar Graphs Without Adjacent Short Cycles
    Chen, Min
    Lih, Ko-Wei
    Wang, Weifan
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2018, 41 (03) : 1507 - 1518
12345