Re: maximal 3-colorable subset
- From: "Proginoskes" <CCHeckman@xxxxxxxxx>
- Date: 7 Dec 2006 22:21:14 -0800
johank wrote:
Hi all,
I am looking for references on the following problem:
given a graph G=(V,E),
and an integer k,
is there a subset V' of V of size k that is 3-colorable?
That is, a optimisation variant of graph coloring that fixes the number
of colors, and optimises the number of vertices that can be colored,
rather than optimising the number of colors used to color everything.
What you have given is not an optimization problem; an optimization
problem would return a "partial" coloring
c:A -> {1,2,...,k} with A (a subset of the vertices) of maximum size.
Although this seems a rather 'natural' problem to me I have
difficulties finding references that address such problems. Any
pointers would me most appreciated.
If you could solve this problem in polynomial time, then you can solve
3-colorability in polynomial time by sending n with a graph G to it.
However, there are some results in the literature involving "defective
colorings"; a k-coloring is d-defective if you can color the vertices
of a graph G such that the subgraphs induced by every color have degree
<= k; that is, every vertex is adjacent to at most k vertices of the
same color. You might be interested in (k,1) colorings. (I don't have
access to MathSciNet at the moment, so I can't make any suggestions.)
--- Christopher Heckman
.
- Prev by Date: Re: Regular Tree Grammar vs. Context-Free Grammar
- Next by Date: Re: Question on computational complexity
- Previous by thread: Regular Tree Grammar vs. Context-Free Grammar
- Next by thread: Re: Question on computational complexity
- Index(es):
Relevant Pages
|
