Coloring edges and vertices of graphs without short or long cycles
Vadim Lozin, Marcin Kamiński · Libraries and Cultural Resources (University of Calgary) · 2006
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.