The restricted arc-width of a graph

Publication date 5 February 2004

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/123238, http://www.emis.de/journals/EJC/Volume_10/Abstracts/v10i1r41.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph minors (05C83)

Review text

Summary: An arc-representation of a graph is a function mapping each vertex in the graph to an arc on the unit circle in such a way that adjacent vertices are mapped to intersecting arcs. The width of such a representation is the maximum number of arcs passing through a single point. The arc-width of a graph is defined to be the minimum width over all of its arc-representations. We extend the work of \textit{J. Barát} and \textit{P. Hajnal} [Electron. J. Comb. 8, Research paper R34 (2001; Zbl 0996.05107)] on this subject and develop a generalization we call restricted arc-width. Our main results revolve around using this to bound arc-width from below and to examine the effect of several graph operations on arc-width. In particular, we completely describe the effect of disjoint unions and wedge sums while providing tight bounds on the effect of cones.

Recommendations

Cited in

(2)

This page was built for publication: The restricted arc-width of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1422127)