A New Upper Bound on the Chromatic Number of Graphs with No Odd Kt Minor

被引:4
作者
Norin, Sergey [1 ]
Song, Zi-Xia [2 ]
机构
[1] McGill Univ, Dept Math & Stat, Montreal, PQ, Canada
[2] Univ Cent Florida, Dept Math, Orlando, FL 32816 USA
基金
美国国家科学基金会; 加拿大自然科学与工程研究理事会;
关键词
EXTREMAL FUNCTION;
D O I
10.1007/s00493-021-4390-3
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Gerards and Seymour conjectured that every graph with no odd K-t minor is (t - 1)-colorable. This is a strengthening of the famous Hadwiger's Conjecture. Geelen et al. proved that every graph with no odd K-t minor is O(t root logt)-colorable. Using the methods the present authors and Postle recently developed for coloring graphs with no K-t minor, we make the first improvement on this bound by showing that every graph with no odd K-t minor is O(t(logt)(beta))-colorable for every beta > 1/4.
引用
收藏
页码:137 / 149
页数:13
相关论文
共 19 条
  • [1] Highly linked graphs
    Bollobas, B
    Thomason, A
    [J]. COMBINATORICA, 1996, 16 (03) : 313 - 320
  • [2] CATLIN PA, 1978, DISCRETE MATH, V22, P81, DOI 10.1016/0012-365X(78)90049-3
  • [3] Packing non-zero A-paths in group-labelled graphs
    Chudnovsky, Maria
    Geelen, Jim
    Gerards, Bert
    Goddyn, Luis
    Lohman, Michael
    Seymour, Paul
    [J]. COMBINATORICA, 2006, 26 (05) : 521 - 532
  • [4] ON SOME EXTREMAL PROBLEMS IN GRAPH THEORY
    ERDOS, P
    [J]. ISRAEL JOURNAL OF MATHEMATICS, 1965, 3 (02) : 113 - &
  • [5] On the odd-minor variant of Hadwiger's conjecture
    Geelen, Jim
    Gerards, Bert
    Reed, Bruce
    Seymour, Paul
    Vetta, Adrian
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2009, 99 (01) : 20 - 29
  • [6] Hadwiger H., 1943, VIERTELJAHRSSCHR NAT, V88, P133
  • [7] Jensen TR., 1995, GRAPH COLORING PROBL
  • [8] Some remarks on the odd Hadwiger's conjecture
    Kawarabayashi, Ken-Ichi
    Song, Zi-Xia
    [J]. COMBINATORICA, 2007, 27 (04) : 429 - 438
  • [9] Highly parity linked graphs
    Kawarabayashi, Ken-Ichi
    Reed, Bruce
    [J]. COMBINATORICA, 2009, 29 (02) : 215 - 225
  • [10] Note on coloring graphs without odd-Kk-minors
    Kawarabayashi, Ken-ichi
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2009, 99 (04) : 728 - 731