β-Perfect Graphs

✍ Scribed by S.E. Markossian; G.S. Gasparian; B.A. Reed

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 291 KB
• Volume: 67
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1996.0030

✦ Synopsis

The class of ;-perfect graphs is introduced. We draw a number of parallels between these graphs and perfect graphs. We also introduce some special classes of ;-perfect graphs. Finally, we show that the greedy algorithm can be used to colour a graph G with no even chordless cycles using at most 2(/(G)&1) colours. 1996 Academic Press, Inc.

1. ;-Perfect Graphs

Contrary to our usual practice, we feel obliged to begin this paper with a few definitions. So, let G=(V(G), E(G )) be a graph without loops or multiple edges (for this and other definitions see Berge [1]). We denote the chromatic number of G by /(G ). We let |(G ) be the size of the largest clique in G. Clearly, /(G ) |(G). For a vertex x of G we let d(x) be the degree of x in G. We let $ G be the minimum degree of a vertex in G and we let 2 G be the maximum degree in G. We let

. Now, we can order the vertices of G arbitrarily and then colour them greedily. Thus /(G ) 2 G +1. Actually, we can do better. We order the vertices by repeatedly removing a vertex of minimum degree in the subgraph of vertices not yet chosen and placing it after all the remaining vertices but before all the vertices already removed. (See [9] for results on this order; in [4] this order is discussed in relation to perfect graphs). Colouring greedily on this order shows that /(G) ;(G) (as was proven in [9] and [14]).