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 条
  • [21] On the Equitable Edge-Coloring of 1-Planar Graphs and Planar Graphs
    Dai-Qiang Hu
    Jian-Liang Wu
    Donglei Yang
    Xin Zhang
    Graphs and Combinatorics, 2017, 33 : 945 - 953
  • [22] Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies
    Dvorak, Zdenek
    Kral, Daniel
    Thomas, Robin
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2021, 150 : 244 - 269
  • [23] Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
    de Werra, D.
    Demange, M.
    Escoffier, B.
    Monnot, J.
    Paschos, V. Th.
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) : 819 - 832
  • [24] SQUARE COLORING PLANAR GRAPHS WITH AUTOMATIC DISCHARGING
    Bousquet, Nicolas
    Deschamps, Quentin
    DE Meyer, Lucas
    Pierron, Theo
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2024, 38 (01) : 504 - 528
  • [25] ACYCLIC LIST EDGE COLORING OF PLANAR GRAPHS
    Lai, Hsin-Hao
    Lih, Ko-Wei
    BULLETIN OF THE INSTITUTE OF MATHEMATICS ACADEMIA SINICA NEW SERIES, 2010, 5 (04): : 413 - 436
  • [26] Equitable coloring planar graphs with large girth
    Wu, Jianliang
    Wang, Ping
    DISCRETE MATHEMATICS, 2008, 308 (5-6) : 985 - 990
  • [27] ACYCLIC EDGE-COLORING OF PLANAR GRAPHS
    Basavaraju, Manu
    Chandran, L. Sunil
    Cohen, Nathann
    Havet, Frederic
    Mueller, Tobias
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2011, 25 (02) : 463 - 478
  • [28] Randomly Coloring Planar Graphs with Fewer Colors than the Maximum Degree
    Hayes, Thomas R.
    Vera, Juan C.
    Vigoda, Eric
    STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, 2007, : 450 - 458
  • [29] 5-Coloring reconfiguration of planar graphs with no short odd cycles
    Cranston, Daniel W.
    Mahmoud, Reem
    JOURNAL OF GRAPH THEORY, 2024, 105 (04) : 670 - 679
  • [30] 5-list-coloring planar graphs with distant precolored vertices
    Dvorak, Zdenek
    Lidicky, Bernard
    Mohar, Bojan
    Postle, Luke
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 122 : 311 - 352