Noncrossing k-factors in geometric graphs II

Noncrossing k-factors in geometric graphs II

0.00 Avg rating—0 Votes
Article ID: iaor20051915
Country: Belarus
Volume: 4
Start Page Number: 111
End Page Number: 116
Publication Date: Dec 2004
Journal: Proceedings of the National Academy of Sciences of Belarus, Series of Physical-Mathematical Sciences
Authors:
Abstract:

It is proved that deciding the existence of a noncrossing 4-factor in 5-regular geometric graph G with r(G)=3 and the existence of a noncrossing 5-factor in 6-regular geometric graph G with r(G)=4, where r(G) is the index of intersection of geometric graph G, is NP-complete.

Reviews

Required fields are marked *. Your email address will not be published.