Orthogonality of packings of paths and independent sets partitions on bipartite gr...
A study of infinite graphs through the problem of describing Unfriendly Partitions
Algorithmic and structural aspects of covering and packing problems on graphs
| Full text | |
| Author(s): |
Silva, Caroline Aparecida de Paula
;
da Silva, Candida Nunes
;
Lee, Orlando
Total Authors: 3
|
| Document type: | Journal article |
| Source: | DISCRETE MATHEMATICS; v. 346, n. 8, p. 6-pg., 2023-04-19. |
| Abstract | |
Let D be a digraph. A stable set S of D and a path partition P of D are orthogonal if every path P is an element of P contains exactly one vertex of S. In 1982, Berge defined the class of alpha-diperfect digraphs. A digraph D is alpha-diperfect if for every maximum stable set S of D there is a path partition P of D orthogonal to S and this property holds for every induced subdigraph of D. An anti-directed odd cycle is an orientation of an odd cycle (x0, . . . , x2k, x0) with k >= 2 in which each vertex x0, x1, x2, x3, x5, x7, ... , x2k-1 is either a source or a sink. Berge conjectured that a digraph D is alpha-diperfect if and only if D does not contain an anti -directed odd cycle as an induced subdigraph. In this paper, we show that this conjecture is false by exhibiting an infinite family of orientations of complements of odd cycles with at least seven vertices that are not alpha-diperfect. (c) 2023 Elsevier B.V. All rights reserved. (AU) | |
| FAPESP's process: | 20/06116-4 - chi-Diperfect Digraphs |
| Grantee: | Caroline Aparecida de Paula Silva |
| Support Opportunities: | Scholarships in Brazil - Master |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |