Colorability of P5-free Graphs: 4-colorability belongs P for P5-free graphs with a dominating K4 - Brossura

Wang, Zebin

Brossura

ISBN 10: 3838373677 ISBN 13: 9783838373676

Casa editrice: LAP LAMBERT Academic Publishing, 2010

Riassunto

This paper considers the question of whether or not a P5-free graph can be 4-colored in polynomial time. It is known that a connected P5-free graph G must have either a dominating clique or a dominating P3. Thus, when considering the 4-coloring question, we have three cases of interest: either G has a dominating K4, a dominating K3, or a dominating P3. In this paper, we demonstrate a polynomial time approach for determining whether or not a P5-free graph G with a dominating K4 can be 4-colored.

Su questo libro

L'autore

Currently, work for a financial institution as senior developer in Toronto, ON. Canada. From Jan.2003 to Jun.2005, major in Computing & Information Science at University of Guelph in Canada, received Master Degree. From Sept.1990 to Jul.1994, major in Computer Science at Civil Aviation Institute of China, received Bachelor Degree.

Dettagli dell'edizione

• Editore: LAP LAMBERT Academic Publishing
• Data di pubblicazione: 2010
• Lingua: Inglese
• ISBN 10: 3838373677
• ISBN 13: 9783838373676
• Rilegatura: Copertina flessibile
• Numero di pagine: 112
• Contatto del produttore: non disponibile
• Persona responsabile: KreGa Onlinehandel GmbH; 4950000000000; info@krega-onlinehandel.de; ; Birkenweg 31; Brakel; 33034; Germania