Coloring count cones of planar graphs

被引:0
|
作者
Dvorak, Zdenek [1 ]
Lidicky, Bernard [2 ]
机构
[1] Charles Univ Prague, Comp Sci Inst CSI, Prague, Czech Republic
[2] Iowa State Univ, Dept Math, 396 Carver Hall,411 Morrill Rd, Ames, IA 50011 USA
关键词
coloring count cone; four color theorem; graph coloring; planar graphs; MAP;
D O I
10.1002/jgt.22767
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For a plane near-triangulation G with the outer face bounded by a cycle C, let n(G)* denote the function that to each 4-coloring psi of C assigns the number of ways psi extends to a 4-coloring ofG. The Block-count reducibility argument (which has been developed in connection with attempted proofs of the Four Color Theorem) is equivalent to the statement that the function n(G)* belongs to a certain cone in the space of all functions from 4-colorings of C to real numbers. We investigate the properties of this cone for vertical bar C vertical bar = 5, formulate a conjecture strengthening the Four Color Theorem, and present evidence supporting this conjecture.
引用
收藏
页码:84 / 100
页数:17
相关论文
共 50 条
  • [1] A Heuristic for the Coloring of Planar Graphs
    De Ita Luna, Guillermo
    Lopez-Ramirez, Cristina
    De Ita-Varela, Ana E.
    Gutierrez-Gomez, Jorge E.
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2020, 354 : 91 - 105
  • [2] Dynamic coloring and list dynamic coloring of planar graphs
    Kim, Seog-Jin
    Lee, Sang June
    Park, Won-Jin
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (13-14) : 2207 - 2212
  • [3] COLORING PLANAR GRAPHS VIA COLORED PATHS IN THE ASSOCIAHEDRA
    Bowlin, Garry
    Brin, Matthew G.
    INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2013, 23 (06) : 1337 - 1418
  • [4] Improved square coloring of planar graphs
    Bousquet, Nicolas
    Deschamps, Quentin
    de Meyer, Lucas
    Pierron, Theo
    DISCRETE MATHEMATICS, 2023, 346 (04)
  • [5] CHARACTERIZATION OF CYCLE OBSTRUCTION SETS FOR IMPROPER COLORING PLANAR GRAPHS
    Choi, Ilkyoo
    Liu, Chun-Hung
    Oum, Sang-Il
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (02) : 1209 - 1228
  • [6] Circular coloring and fractional coloring in planar graphs
    Hu, Xiaolan
    Li, Jiaao
    JOURNAL OF GRAPH THEORY, 2022, 99 (02) : 312 - 343
  • [7] Additive Coloring of Planar Graphs
    Tomasz Bartnicki
    Bartłomiej Bosek
    Sebastian Czerwiński
    Jarosław Grytczuk
    Grzegorz Matecki
    Wiktor Żelazny
    Graphs and Combinatorics, 2014, 30 : 1087 - 1098
  • [8] Additive Coloring of Planar Graphs
    Bartnicki, Tomasz
    Bosek, Bartlomiej
    Czerwinski, Sebastian
    Grytczuk, Jaroslaw
    Matecki, Grzegorz
    Zelazny, Wiktor
    GRAPHS AND COMBINATORICS, 2014, 30 (05) : 1087 - 1098
  • [9] Odd coloring of sparse graphs and planar graphs
    Cho, Eun-Kyung
    Choi, Ilkyoo
    Kwon, Hyemin
    Park, Boram
    DISCRETE MATHEMATICS, 2023, 346 (05)
  • [10] Coloring Squares of Planar Graphs with Small Maximum Degree
    Krzyzinski, Mateusz
    Rzazewski, Pawel
    Tur, Szymon
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2024, 44 (03) : 817 - 835