R638, Astronomy-Mathematics Building, NTU
(台灣大學天文數學館 638室)
Maximum $d$-degenerate Subgraph of a Planar Graph
Hao Qi (Academia Sinica)
Abstract:
A graph
is
if every subgraph of
has a vertex of degree at most
. The study of induced
-degenerate subgraphs of planar graphs is related to many other problems, and has been studied by many authors. We are interested in the maximum induced
-degenerate subgraph of a planar graph. For a non-negative integer
and a graph
, denote by
the maximum number of vertices of an induced
-degenerate subgraph of
. For
, let
It follows from the four colour theorem that
. However, proving
without using the four colour theorem remains an open problem. Albertson-Berman and Akiyama independently conjectured that
. Borodin and Glebov proved that this conjecture is true for planar graphs of girth at least
. Otherwise, this conjecture is largely open. The best known upper and lower bound for
is
, the last result was proved by Luko\u{t}ka, Maz\'{a}k and Zhu. In this talk, we give a new result
; and conjecture that
.
This is a joint work with H. A. Kierstead, Sang-il Oum and Xuding Zhu.