Sponsored by
 
Events
News
 
[ Events ]
 
 

Activity Search
Sort out
Field
 
Year
Seminars  
 
Taipei Postdoc Seminar
 
11:00 - 12:30, October 24, 2018 (Wednesday)
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.


 

back to list  
 (C) 2021 National Center for Theoretical Sciences