𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the perfect orderability of unions of two graphs

✍ Scribed by Ho�ng, Ch�nh T.; Tu, Xiaodan

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
264 KB
Volume
33
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is perfectly orderable, if it admits an order < on its vertices such that the sequential coloring algorithm delivers an optimum coloring on each induced subgraph (H, <) of (G, <). A graph is a threshold graph, if it contains no P 4 , 2K 2 , and C 4 as induced subgraph. A theorem of Chvátal, Hoàng, Mahadev, and de Werra states that a graph is perfectly orderable, if it is the union of two threshold graphs. In this article, we investigate possible generalizations of the above theorem. Hoàng has conjectured that, if G is the union of two graphs G 1 and G 2 , then G is perfectly orderable whenever G 1 and G 2 are both P 4 -free and 2K 2 -free. We show that the complement of the chordless cycle with at least five vertices cannot be a counter-example to this conjecture, and we prove a special case of it: if G 1 and G 2 are two edge-disjoint graphs that are P 4 -free and 2K 2 -free, then the union of G 1 and G 2 is perfectly orderable.

📜 SIMILAR VOLUMES

A graph-theoretic version of the union-c
A graph-theoretic version of the union-closed sets conjecture
✍ El-Zahar, Mohamed H. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB 👁 2 views

An induced subgraph S of a graph G is called a derived subgraph of G if S contains no isolated vertices. An edge e of G is said to be residual if e occurs in more than half of the derived subgraphs of G. We introduce the conjecture: Every non-empty graph contains a non-residual edge. This conjecture

On the design of two channel perfect con
On the design of two channel perfect construction QMF filters
✍ Saleh, A. I.; Fahmy, M. F.; Raheem, G. A.; Fahmy, G. F. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB 👁 2 views

This paper presents two rapidly convergent methods for the design of two-channel odd degree linear phase FIR banks as well as IIR "lter banks. In both cases, zeros of arbitrary multiplicity are assumed at z"!1, to ensure regularity of the generated wavelet basis. It is shown that in the FIR case, th

Comparison of two indices for the invest
Comparison of two indices for the investigation of cooperation graphs
✍ Geldenhuys, Gerhard ;Human, Lez�nne 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 495 KB

An index of cohesion for the investigation of communication between authors or academic units is described and compared with the Brillouin-Shaw index. The Brillouin-Shaw index has the advantage of relatively easy computation, but it cannot bring out the same nuances as the index of cohesion.

On the linear arboricity of planar graph
On the linear arboricity of planar graphs
✍ Wu, Jian-Liang 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB 👁 2 views

The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. Akiyama, Exoo, and Harary conjectured for any simple graph G with maximum degree ∆. The conjecture has been proved to be true for graphs having ∆ =

Various results on the toughness of grap
Various results on the toughness of graphs
✍ Broersma, Hajo; Engbers, Erik; Trommel, Huib 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB 👁 2 views

Let G be a graph and let t Ն 0 be a real number. Then, We discuss how the toughness of (spanning) subgraphs of G and related graphs depends on (G), we give some sufficient degree conditions implying that (G) Ն t, and we study which subdivisions of 2-connected graphs have minimally 2-tough squares.