✦ LIBER ✦

A note on superbrittle graphs

✍ Scribed by M Preissmann; D de Werra; N.V.R Mahadev

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 453 KB
Volume: 61
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(86)90097-x

No coin nor oath required. For personal study only.

✦ Synopsis

Perfectly orderable graphs are such that an ordering xl > x 2 >. " " > X n of the nodes can be found for which the sequential node coloring algorithm based on this order ("always use the smallest possible color") gives an optimum coloring for any subgraph.

We characterize in terms of forbidden subgraphs two subclasses of perfectly orderable graphs: the superbrittle graphs are such that in any subgraph a node x can never be a midpoint of an induced P4 (path on 4 nodes) and an endpoint of an induced P,,. Maxibrittle graphs are such that in any subgraph there is no induced P4 having a node of maximum degree as an endpoint and there is no induced P4 having a node of minimum degree as a midpoint.

📜 SIMILAR VOLUMES

A note on conservative graphs

✍ Arthur T. White 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract An application of conservative graphs to topological graph theory is indicated.

A note on coset graphs

✍ Ulrike Baumann 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

## Abstract Coset graphs are a generalization of Cayley graphs. They arise in the construction of graphs and digraphs with transitive automorphism groups. Moreover, the consideration of coset graphs makes it possible to give an algebraic description of regular connected graphs of even degree. In th

A note on planar graphs

✍ David P. Brown; Alan Budner 📂 Article 📅 1965 🏛 Elsevier Science 🌐 English ⚖ 612 KB

Some new properties of the distribution of elements and vertices with respect to the windows of a connected planar graph G are established. It is also shown that a window matrix of G has properties similar to the properties of an incidence matrix of a graph which is not necessarily planar. A method

A note on visibility graphs

✍ F Luccio; S Mazzone; C.K Wong 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 602 KB

Given a set S = {s 1, s 2, ..., s,,) of vertical line segments, si, sj see each other ff there is a horizontal line segment which intersects them, but does not intersect any other line segment between them. A ws" ibility graph G of vertices {vl, v2, • .., v,,} is put into a one-to-one correspondenc

A note on stable graphs

✍ Linda Lesniak-Foster 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 551 KB

A note on ‘on antipodal graphs’

✍ R Aravamudhan; B Rajendran 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 136 KB