R638, Astronomy-Mathematics Building, NTU
(台灣大學天文數學館 638室)
Maximum $d$-degenerate Subgraph of a Planar Graph
Hao Qi (Academia Sinica)
Abstract:
A graph
![](https://chart.googleapis.com/chart?cht=tx&chl=%24G%24&chf=bg,s,333333&chco=ffffff)
is
![](https://chart.googleapis.com/chart?cht=tx&chl=%24k-degenerate%24&chf=bg,s,333333&chco=ffffff)
if every subgraph of
![](https://chart.googleapis.com/chart?cht=tx&chl=%24G%24&chf=bg,s,333333&chco=ffffff)
has a vertex of degree at most
![](https://chart.googleapis.com/chart?cht=tx&chl=%24k%24&chf=bg,s,333333&chco=ffffff)
. The study of induced
![](https://chart.googleapis.com/chart?cht=tx&chl=%24k%24&chf=bg,s,333333&chco=ffffff)
-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
![](https://chart.googleapis.com/chart?cht=tx&chl=%24d%24&chf=bg,s,333333&chco=ffffff)
-degenerate subgraph of a planar graph. For a non-negative integer
![](https://chart.googleapis.com/chart?cht=tx&chl=%24d%24&chf=bg,s,333333&chco=ffffff)
and a graph
![](https://chart.googleapis.com/chart?cht=tx&chl=%24G%24&chf=bg,s,333333&chco=ffffff)
, denote by
![](https://chart.googleapis.com/chart?cht=tx&chl=%24%5Calpha_d(G)%24&chf=bg,s,333333&chco=ffffff)
the maximum number of vertices of an induced
![](https://chart.googleapis.com/chart?cht=tx&chl=%24d%24&chf=bg,s,333333&chco=ffffff)
-degenerate subgraph of
![](https://chart.googleapis.com/chart?cht=tx&chl=%24G%24&chf=bg,s,333333&chco=ffffff)
. For
![](https://chart.googleapis.com/chart?cht=tx&chl=%240%20%5Cle%20d%20%5Cle%204%24&chf=bg,s,333333&chco=ffffff)
, let
It follows from the four colour theorem that
![](https://chart.googleapis.com/chart?cht=tx&chl=%24%5Ctau_0%3D1%2F4%24&chf=bg,s,333333&chco=ffffff)
. However, proving
![](https://chart.googleapis.com/chart?cht=tx&chl=%24%5Ctau_0%3D1%2F4%24&chf=bg,s,333333&chco=ffffff)
without using the four colour theorem remains an open problem. Albertson-Berman and Akiyama independently conjectured that
![](https://chart.googleapis.com/chart?cht=tx&chl=%24%5Ctau_1%20%3D%201%2F2%24&chf=bg,s,333333&chco=ffffff)
. Borodin and Glebov proved that this conjecture is true for planar graphs of girth at least
![](https://chart.googleapis.com/chart?cht=tx&chl=%245%24&chf=bg,s,333333&chco=ffffff)
. Otherwise, this conjecture is largely open. The best known upper and lower bound for
![](https://chart.googleapis.com/chart?cht=tx&chl=%24%5Ctau_4%24&chf=bg,s,333333&chco=ffffff)
is
![](https://chart.googleapis.com/chart?cht=tx&chl=%248%2F9%20%5Cle%20%5Ctau_4%20%5Cle%2011%2F21%24&chf=bg,s,333333&chco=ffffff)
, the last result was proved by Luko\u{t}ka, Maz\'{a}k and Zhu. In this talk, we give a new result
![](https://chart.googleapis.com/chart?cht=tx&chl=%245%2F7%20%5Cle%20%5Ctau_3%20%5Cle%205%2F6%24&chf=bg,s,333333&chco=ffffff)
; and conjecture that
![](https://chart.googleapis.com/chart?cht=tx&chl=%24%20%5Ctau_2%3D2%2F3%2C%20%5Ctau_3%3D5%2F6%2C%20%5Ctau_4%3D11%2F12%24&chf=bg,s,333333&chco=ffffff)
.
This is a joint work with H. A. Kierstead, Sang-il Oum and Xuding Zhu.