𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Berge's strong path partition conjecture

✍ Scribed by S. Sridharan

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
312 KB
Volume
112
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Sridharan, S., On the Berge's strong path partition conjecture, Discrete Mathematics 112 (1993) 289-293.

It is proved that for every k-optimal path partition of a digraph in which each component contains at most one cycle, there exists a partial k-coloring which colors strongly every path of the partition.

Definition. Consider a partial k-coloring and a path P of G. We say that P is strongly co/ored or the partial k-coloring is strong for P if the number of different colors represented in P is equal to min { k, 1 P I}.

πŸ“œ SIMILAR VOLUMES

On the bergeβ€”sauer conjecture
On the bergeβ€”sauer conjecture
✍ K. R. Parthasarathy; S. Sridharan πŸ“‚ Article πŸ“… 1982 πŸ› John Wiley and Sons 🌐 English βš– 115 KB

## Abstract It is proved that a simple 4‐regular graph without __K__~1,3~ as an induced subgraph has a 3‐regular subgraph.

On the strong perfect graph conjecture
On the strong perfect graph conjecture
✍ Stephan Olariu πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 384 KB

A graph G is perfect if for every induced subgraph H of G the chromatic number x(H) equals the largest number w ( H ) of pairwise adjacent vertices in H. Berge's famous Strong Perfect Graph Conjecture asserts that a graph G is perfect if and only if neither G nor its complement C contains an odd cho