Stars and bunches in planar graphs. Part II: General planar graphs and colourings
2002•research.utwente.nl
Given a plane graph, a $ k $-star at $ u $ is a set of $ k $ vertices with a common neighbour
$ u $; and a bunch is a maximal collection of paths of length at most two in the graph, such
that all paths have the same end vertices and the edges of the paths form consecutive edges
(\, in the natural order in the plane graph\,) around the two end vertices. We first prove a
theorem on the structure of plane graphs in terms of stars and bunches. The result states that
a plane graph contains a $(d-1) $-star centred at a vertex of degree $ d\leq5 $ and the sum …
$ u $; and a bunch is a maximal collection of paths of length at most two in the graph, such
that all paths have the same end vertices and the edges of the paths form consecutive edges
(\, in the natural order in the plane graph\,) around the two end vertices. We first prove a
theorem on the structure of plane graphs in terms of stars and bunches. The result states that
a plane graph contains a $(d-1) $-star centred at a vertex of degree $ d\leq5 $ and the sum …
Abstract
Given a plane graph, a -star at is a set of vertices with a common neighbour ; and a bunch is a maximal collection of paths of length at most two in the graph, such that all paths have the same end vertices and the edges of the paths form consecutive edges (\, in the natural order in the plane graph\,) around the two end vertices. We first prove a theorem on the structure of plane graphs in terms of stars and bunches. The result states that a plane graph contains a -star centred at a vertex of degree and the sum of the degrees of the vertices in the star is bounded, or there exists a large bunch.
research.utwente.nl
以上显示的是最相近的搜索结果。 查看全部搜索结果