The q-perfect graphs
<p><span style="font-style: normal;"><span>Let </span></span><em><span>q</span></em><span style="font-style: normal;"><span> be a positive integer. Many graphs admit a partial coloring with </span></span&g...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Università degli Studi di Catania
1992-11-01
|
| Series: | Le Matematiche |
| Online Access: | http://www.dmi.unict.it/ojs/index.php/lematematiche/article/view/585 |
| Summary: | <p><span style="font-style: normal;"><span>Let </span></span><em><span>q</span></em><span style="font-style: normal;"><span> be a positive integer. Many graphs admit a partial coloring with </span></span><em><span>q</span></em><span style="font-style: normal;"><span> colors and a clique partition such that each of the cliques is </span></span><em><span>strongly colored</span></em><span style="font-style: normal;"><span>, that is: contains the largest possible number of different colors. If a graph </span></span><em><span>G</span></em><span style="font-style: normal;"><span> and all its induced subgraphs have this property, we say that </span></span><em><span>G</span></em><span style="font-style: normal;"><span> is </span></span><em><span>q-perfect</span></em><span style="font-style: normal;"><span> (Lovasz). In a previous paper [4], the specific properties for the case </span></span><em><span>q=2</span></em><span style="font-style: normal;"><span> were investigated. Here, we study some graphs which are </span></span><em><span>q-</span></em><span style="font-style: normal;"><span>perfect for other values of </span></span><em><span>q</span></em><span style="font-style: normal;"><span>, and more specially the </span></span><em><span>balanced graphs</span></em><span style="font-style: normal;"><span>.</span></span></p> |
|---|---|
| ISSN: | 0373-3505 2037-5298 |