𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Two-colourings that decompose perfect graphs

✍ Scribed by Vašek Chvátal; William J Lenhart; Najiba Sbihi

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
435 KB
Volume
49
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the two-edge-colorings of perfect gra
On the two-edge-colorings of perfect graphs
✍ Chính T. Hoàng 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 409 KB 👁 1 views

## Abstract We investigate the conjecture that a graph is perfect if it admits a two‐edge‐coloring such that two edges receive different colors if they are the nonincident edges of a __P__~4~ (chordless path with four vertices). Partial results on this conjecture are given in this paper. © 1995 Joh

On the perfect orderability of unions of
On the perfect orderability of unions of two graphs
✍ Ho�ng, Ch�nh T.; Tu, Xiaodan 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 264 KB 👁 3 views

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

Degree sums and graphs that are not cove
Degree sums and graphs that are not covered by two cycles
✍ Saito, Akira 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 2 views

For a graph G, let σ 3 (G) = min{deg G x + deg G y + deg G z: {x, y, z} is an independent set in G}. Enomoto et al. [Enowoto et al., J Graph Theory 20 (1995), 419-422] have proved that the vertex set of a 2-connected graph G of order n with σ 3 (G) ≥ n is covered by two cycles, edges or vertices. Ex

Graphs such that every two edges are con
Graphs such that every two edges are contained in a shortest cycle
✍ Nathalie Homobono; Claudine Peyrat 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 665 KB

A graph G is said to have depth 6 if every path of length d + 1 is contained in a shortest cycle. First we answer by the negative a problem of Neumaier [2], by constructing for every 6, a graph of depth 6 which is neither a cyck nor a uniform subdivision of another graph. Then we characterize the gr