About this Computer Science article

β-Perfect Graphs by S.E. Markossian; G.S. Gasparian; B.A. Reed is a Computer Science article available to read on EtoBox.

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 resu

Author

S.E. Markossian; G.S. Gasparian; B.A. Reed

Publisher

Elsevier Science; Elsevier ; Elsevier Inc.; Elsevier BV (ISSN 0095-8956)

Published

1996

Language

EN

Field

Computer Science (Physical Sciences)