Stars and bunches in planar graphs. Part II: General planar graphs and colourings

O.V. Borodin, Haitze J. Broersma, A. Glebov, J. van den Heuvel

Research output: Book/ReportReportProfessional

76 Downloads (Pure)

Abstract

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 of the degrees of the vertices in the star is bounded, or there exists a large bunch.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages19
ISBN (Print)0169-2690
Publication statusPublished - 2002

Publication series

NameMemorandum Faculteit TW
PublisherDepartment of Applied Mathematics, University of Twente
No.1633
ISSN (Print)0169-2690

Keywords

  • METIS-208267
  • MSC-05C15
  • MSC-05C12
  • EWI-3453
  • IR-65820

Cite this

Borodin, O. V., Broersma, H. J., Glebov, A., & van den Heuvel, J. (2002). Stars and bunches in planar graphs. Part II: General planar graphs and colourings. (Memorandum Faculteit TW; No. 1633). Enschede: University of Twente, Department of Applied Mathematics.
Borodin, O.V. ; Broersma, Haitze J. ; Glebov, A. ; van den Heuvel, J. / Stars and bunches in planar graphs. Part II: General planar graphs and colourings. Enschede : University of Twente, Department of Applied Mathematics, 2002. 19 p. (Memorandum Faculteit TW; 1633).
@book{4d166c6b694c429db9442fa402b60e84,
title = "Stars and bunches in planar graphs. Part II: General planar graphs and colourings",
abstract = "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 of the degrees of the vertices in the star is bounded, or there exists a large bunch.",
keywords = "METIS-208267, MSC-05C15, MSC-05C12, EWI-3453, IR-65820",
author = "O.V. Borodin and Broersma, {Haitze J.} and A. Glebov and {van den Heuvel}, J.",
note = "Imported from MEMORANDA",
year = "2002",
language = "Undefined",
isbn = "0169-2690",
series = "Memorandum Faculteit TW",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1633",

}

Borodin, OV, Broersma, HJ, Glebov, A & van den Heuvel, J 2002, Stars and bunches in planar graphs. Part II: General planar graphs and colourings. Memorandum Faculteit TW, no. 1633, University of Twente, Department of Applied Mathematics, Enschede.

Stars and bunches in planar graphs. Part II: General planar graphs and colourings. / Borodin, O.V.; Broersma, Haitze J.; Glebov, A.; van den Heuvel, J.

Enschede : University of Twente, Department of Applied Mathematics, 2002. 19 p. (Memorandum Faculteit TW; No. 1633).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Stars and bunches in planar graphs. Part II: General planar graphs and colourings

AU - Borodin, O.V.

AU - Broersma, Haitze J.

AU - Glebov, A.

AU - van den Heuvel, J.

N1 - Imported from MEMORANDA

PY - 2002

Y1 - 2002

N2 - 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 of the degrees of the vertices in the star is bounded, or there exists a large bunch.

AB - 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 of the degrees of the vertices in the star is bounded, or there exists a large bunch.

KW - METIS-208267

KW - MSC-05C15

KW - MSC-05C12

KW - EWI-3453

KW - IR-65820

M3 - Report

SN - 0169-2690

T3 - Memorandum Faculteit TW

BT - Stars and bunches in planar graphs. Part II: General planar graphs and colourings

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Borodin OV, Broersma HJ, Glebov A, van den Heuvel J. Stars and bunches in planar graphs. Part II: General planar graphs and colourings. Enschede: University of Twente, Department of Applied Mathematics, 2002. 19 p. (Memorandum Faculteit TW; 1633).