Vertex 3-colorability of claw-free graphs

Authors

  • Marcin Kamiński RUTCOR - Rutgers University Center for Operations Research, 640 Bartholomew Road, Piscataway, NJ 08854, USA
  • Vadim Lozin RUTCOR - Rutgers University Center for Operations Research, 640 Bartholomew Road, Piscataway, NJ 08854, USA

Keywords:

Vertex 3-colorability, Claw-free graphs, Polynomial-time algorithm

Abstract

The 3-COLORABILITY problem is NP-complete in the class of claw-free graphs. In this paper we study the computational complexity of the problem in subclasses of claw-free graphs defined by forbidding finitely many additional subgraphs (line graphs and claw-free graphs of bounded vertex degree being examples of such classes). We prove a necessary condition for the polynomial-time solvability of the problem in such classes and propose a linear-time solution for an infinitely increasing hierarchy of classes that meet the condition. To develop such a solution for the basis of this hierarchy, we generalize the notion of locally connected graphs that has been recently studied in the context of the 3-COLORABILITY problem. Key words: Vertex 3-colorability; Claw-free graphs; Polynomial-time algorithm

Downloads

Published

2007-02-07

How to Cite

Kamiński, M., & Lozin, V. (2007). Vertex 3-colorability of claw-free graphs. Algorithmic Operations Research, 2(1). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/2730

Issue

Vol. 2 No. 1 (2007)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.