Hadwiger's conjecture for squares of 2-trees

被引:1
作者
Chandran, L. Sunil [1 ]
Issac, Davis [2 ]
Zhou, Sanming [3 ]
机构
[1] Indian Inst Sci, Bangalore 560012, Karnataka, India
[2] Max Planck Inst Informat, Saarland Informat Campus, Saarbrucken, Germany
[3] Univ Melbourne, Sch Math & Stat, Parkville, Vic 3010, Australia
关键词
EVERY PLANAR MAP; GRAPHS; NUMBER;
D O I
10.1016/j.ejc.2018.10.003
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Hadwiger's conjecture asserts that any graph contains a clique minor with order no less than the chromatic number of the graph. We prove that this well-known conjecture is true for all graphs if and only if it is true for squares of split graphs. This observation implies that Hadwiger's conjecture for squares of chordal graphs is as difficult as the general case, since chordal graphs are a superclass of split graphs. Then we consider 2-trees which are a subclass of each of planar graphs, 2-degenerate graphs and chordal graphs. We prove that Hadwiger's conjecture is true for squares of 2-trees. We achieve this by proving the following stronger result: for any 2-tree T, its square T-2 has a clique minor of order chi(T-2) for which each branch set induces a path, where chi(T-2) is the chromatic number of T-2. (C) 2018 Elsevier Ltd. All rights reserved.
引用
收藏
页码:159 / 174
页数:16
相关论文
共 22 条
[1]   EVERY PLANAR MAP IS 4 COLORABLE .1. DISCHARGING [J].
APPEL, K ;
HAKEN, W .
ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) :429-490
[2]   EVERY PLANAR MAP IS 4 COLORABLE .2. REDUCIBILITY [J].
APPEL, K ;
HAKEN, W ;
KOCH, J .
ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) :491-567
[3]  
Basavaraju M., COMMUNICATION
[4]   Hadwiger's conjecture for proper circular arc graphs [J].
Belkale, Naveen ;
Chandran, L. Sunil .
EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (04) :946-956
[5]  
Bollobas B., 1980, Europ. J. Comb. Theory, V1, P195
[6]   Hadwiger number and the Cartesian product of graphs [J].
Chandran, L. Sunil ;
Kostochka, Alexandr ;
Raju, J. Krishnam .
GRAPHS AND COMBINATORICS, 2008, 24 (04) :291-301
[7]   Hadwiger's conjecture for quasi-line graphs [J].
Chudnovsky, Maria ;
Fradkin, Alexandra Ovetsky .
JOURNAL OF GRAPH THEORY, 2008, 59 (01) :17-33
[8]   Claw-free graphs. VII. Quasi-line graphs [J].
Chudnovsky, Maria ;
Seymour, Paul .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2012, 102 (06) :1267-1294
[9]   HADWIGER NUMBER OF GRAPHS WITH SMALL CHORDALITY [J].
Golovach, Petr A. ;
Heggernes, Pinar ;
van't Hof, Pim ;
Paul, Christophe .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2015, 29 (03) :1427-1451
[10]  
Hadwiger Hugo., 1943, Naturforsch. Ges. Zurich, V88, P133