Re: maximal 3-colorable subset

johank <j.kwisthout@xxxxxxxxx> wrote:
# Hi all,
#
# I am looking for references on the following problem:
#
# given a graph G=(V,E), 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.
#
# Although this seems a rather 'natural' problem to me I have
# difficulties finding references that address such problems. Any
# pointers would me most appreciated.


Here is a reference.

M. Yannakakis, F. Gavril
The maximum k-colorable subgraph problem for chordal graphs.
Information Processing Letters 24 (1987), 133-137.

--Gerhard

___________________________________________________________
Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/

.

Relevant Pages

  • Re: Calling destructor
    ... >> Something you can do, that will help, is to set references to null for ... As long as you hold references to an object, ... OP described how he had a large graph of objects and needed the ability to ... In such a scenario, setting a reference to the object to null ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: White House spins "The Commander Guy"
    ... References you ... That's the true test of science -- ... The graph shows a scatter anywhere between 110 and 130. ... science is to consider all data, and that scatter graph has more data ...
    (rec.sport.golf)
  • Re: Complexity of Finding the longest simple path in a graph
    ... salesman problem / you can look for Kruskal and Prim's algo... ... > formulated into a reachability graph: ... Note I do not know any "target" vertice. ... > references about the corresponding results. ...
    (comp.theory)
  • maximal 3-colorable subset
    ... a optimisation variant of graph coloring that fixes the number ... difficulties finding references that address such problems. ... Kind regards, ...
    (comp.theory)
  • Re: Variable removed due to Optimization!!!
    ... "Anton Feiertag" wrote in message ... when stepping within the range of code that references it.. ... Turning optimisation off doesn't necessarily mean the exe will be linked ... The code may not be rebuilt, you may have otherwise fixed the units options. ...
    (comp.lang.pascal.delphi.misc)
Loading