Abstract

A graph $G$ is said to be $\mathcal{R}$-perfect if, for all induced subgraphs $H$ of $G$, the induced regular independence number of each induced subgraph $H$ is equal to its corresponding induced regular cover. Here, the induced regular independence number is the maximum number of vertices in $H$ such that no two belong to the same induced regular subgraph in $H$, and the induced regular cover of $H$ is the minimum number of induced regular subgraphs in $H$ required to cover the vertex set of $H$. This article introduces the notion of induced regular perfect graphs or $\mathcal{R}$-perfect graphs through which we study the structural properties of $\mathcal{R}$-perfect graphs and identify a forbidden class of graphs for the same. This further leads to the characterization of $\mathcal{R}$-perfect biconnected graphs. With these results, we derive and prove a general characterization for $\mathcal{R}$-perfect graphs.

Keywords and Phrases

Perfect graphs, $\mathcal{F}$-perfect graphs, Regular graphs, $\mathcal{R}$-perfect graphs, Graph minors.

A.M.S. subject classification

05C17, 05C10, 05C60, 05C83.

.....