On graphs admitting two disjoint maximum independent sets

Authors

DOI:

https://doi.org/10.26493/2590-9770.1563.5f6

Keywords:

Maximum independent set, shedding vertex, König-Egerváry graph, unicyclic graph

Abstract

An independent set S is maximal if it is not a proper subset of an independent set, while S is maximum if it has a maximum size. The problem of whether a graph has a pair of disjoint maximal independent sets was introduced by Berge in the early 1970s. The class of graphs for which every induced subgraph admits two disjoint maximal independent sets was characterized by Schaudt in 2015.

Published

2022-09-26

Issue

Section

Articles