首页 | 本学科首页   官方微博 | 高级检索  
     


Exponentially many 4‐list‐colorings of triangle‐free graphs on surfaces
Abstract:Thomassen proved that every planar graph G on n vertices has at least urn:x-wiley:03649024:media:jgt22153:jgt22153-math-0001 distinct L‐colorings if L is a 5‐list‐assignment for G and at least urn:x-wiley:03649024:media:jgt22153:jgt22153-math-0002 distinct L‐colorings if L is a 3‐list‐assignment for G and G has girth at least five. Postle and Thomas proved that if G is a graph on n vertices embedded on a surface Σ of genus g, then there exist constants urn:x-wiley:03649024:media:jgt22153:jgt22153-math-0003 such that if G has an L‐coloring, then G has at least urn:x-wiley:03649024:media:jgt22153:jgt22153-math-0004 distinct L‐colorings if L is a 5‐list‐assignment for G or if L is a 3‐list‐assignment for G and G has girth at least five. More generally, they proved that there exist constants urn:x-wiley:03649024:media:jgt22153:jgt22153-math-0005 such that if G is a graph on n vertices embedded in a surface Σ of fixed genus g, H is a proper subgraph of G, and ϕ is an L‐coloring of H that extends to an L‐coloring of G, then ϕ extends to at least urn:x-wiley:03649024:media:jgt22153:jgt22153-math-0006 distinct L‐colorings of G if L is a 5‐list‐assignment or if L is a 3‐list‐assignment and G has girth at least five. We prove the same result if G is triangle‐free and L is a 4‐list‐assignment of G, where urn:x-wiley:03649024:media:jgt22153:jgt22153-math-0007, and urn:x-wiley:03649024:media:jgt22153:jgt22153-math-0008.
Keywords:coloring  exponentially many  graph theory  graphs on surfaces  list‐coloring
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号