tailieunhanh - Báo cáo toán học: "The arc-width of a graph"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: The arc-width of a graph. | The arc-width of a graph Jangs Barat jbarat@ and Peter Hajnal hajnal@ Bolyai Institute University of Szeged Aradi vertanuk tere 1. Szeged 6720 Hungary Submitted January 23 2001 Accepted June 13 2001. MR Subject Classifications 05C62 05C83 Abstract The arc-representation of a graph is a mapping from the set of vertices to the arcs of a circle such that adjacent vertices are mapped to intersecting arcs. The width of such a representation is the maximum number of arcs having a point in common. The arc-width aw of a graph is the minimum width of its arc-representations. We show how arc-width is related to path-width and vortex-width. We prove that aw Ks S s. 1 Introduction The notation and terminology of the paper follows 2 . In the Graph Minors project Robertson and Seymour often with other coauthors introduced several minor-monotone graph parameters. We recall their first such parameter. Our definition is a dual to the original one appearing in 3 . About the equivalence see . Exercises 24 25 in Chapter 12 of 2 . Definition 1 The interval-representation of a graph G is a mapping Ộ from its vertex set to the intervals of a base line such that adjacent vertices are mapped to intersecting intervals. The width in a representation of a point P of the base line is the number of intervals containing P. The width of Ộ is the maximum width Research supported by OTKA Grant . and the Hungarian State Eotvos Scholarship Research supported by OTKA Grants . and . the electronic journal gf combinatorics 8 2001 R34 1 of the points of the base line. This is equal to the maximum number of pairwise intersecting intervals. The interval-width of a graph G is the minimal possible width of such interval-representations pw G in notation. Actually Robertson and Seymour defined path-width pw which is one less than the above defined interval-width. They extended the notion of path-width by changing the base line to a tree and substituting .