Coloring edges and vertices of graphs without short or long cycles

Authors

  • Vadim V. Lozin
  • Marcin Kaminski

DOI:

https://doi.org/10.11575/cdm.v2i1.61890

Abstract

Vertex and edge colorability are two graph problems that are NP-hard in general. We show that both problems remain difficult even for graphs without short cycles, i.e., without cycles of length at most g for any particular value of g. On the contrary, for graphs without long cycles, both problems are shown to be solvable in poynomial time.

Downloads

Download data is not yet available.

Downloads

Published

2007-03-08

Issue

Section

Articles