Previous |  Up |  Next


chromatic number; clique number; weakly perfect graph
A graph is called weakly perfect if its chromatic number equals its clique number. In this note a new class of weakly perfect graphs is presented and an explicit formula for the chromatic number of such graphs is given.
[1] Garey, M. R., Johnson, D. S.: Computers and Intractabilitiy: A Guide to the Theory of NP-Completeness. W. H. Freman and Company, New York (1979). MR 0519066
[2] Kubale, M.: Graph Colorings. American Mathematical Society (2004). MR 2074481 | Zbl 1064.05061
[3] McDiarmid, C., Reed, B.: Channel assignment and weighted colouring. Networks 36 (2000), 114-117. DOI 10.1002/1097-0037(200009)36:2<114::AID-NET6>3.0.CO;2-G | MR 1793319
[4] West, D. B.: Introduction to Graph Theory. Prentice Hall, Inc., Upper Saddle River, NJ (1996). MR 1367739 | Zbl 0845.05001
Partner of
EuDML logo