<p>Given a graph $G$ and a proper vertex coloring $C$ with the minimum
numbers of colors, how much faster can a maximum clique be found than
when just $G$ is given?</p>

<p>Additional information doesn't make the problem harder, and it is
still NP-hard since <a href="http://graphclasses.org/classes/AUTO_2153.html" rel="nofollow">there are graph classes where coloring
is in P and clique is NP-hard</a>.</p>

<p>There might be some relation to hypergraphs.</p>

<p>We have the trivial bound $\omega(G) \le \chi(G)$, so an algorithm
which finds a clique of size $\chi(G)$ will stop.</p>

CC BY-SA 3.0
2015-01-19T15:52:08.117Z
What is the question here? if we can speed CLIQUE even though it remains NPC?
R B
CC BY-SA 3.0
2015-01-19T16:35:38.057Z
@RB I edited giving a bound which might help. Actually I am asking if we can speed clique with additional information which gives upper bound.
joro
CC BY-SA 3.0
2015-01-19T17:36:57.023Z
Can you provide a sample of those graph classes which clique is NP-hard but coloring is P?
Saeed
CC BY-SA 3.0
2015-01-19T18:48:55.383Z
@Saeed according to graphclases.org example is (3K_1,co-K_{1,5})-free -- check details for reference, link: http://graphclasses.org/classes/AUTO_2153.html
joro
CC BY-SA 3.0
2015-01-20T00:01:02.760Z
Doesn't the "it is still NP-hard" part of your posting answer your own question?
David Eppstein
CC BY-SA 3.0
2015-01-20T08:18:04.437Z
@DavidEppstein I think the upper bound makes it at least slightly easier/faster.
joro
<graph-theory><graph-algorithms>
How much faster is solving Clique in properly colored graph?
joro
# How much faster is solving Clique in properly colored graph?

(Asked by: username_0 on 2015-01-19)

Given a graph $G$ and a proper vertex coloring $C$ with the minimum
numbers of colors, how much faster can a maximum clique be found than
when just $G$ is given?

Additional information doesn't make the problem harder, and it is
still NP-hard since [there are graph classes where coloring
is in P and clique is NP-hard](http://graphclasses.org/classes/AUTO_2153.html).

There might be some relation to hypergraphs.

We have the trivial bound $\omega(G) \le \chi(G)$, so an algorithm
which finds a clique of size $\chi(G)$ will stop.

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: What is the question here? if we can speed CLIQUE even though it remains NPC?  
> **username_0**: @RB I edited giving a bound which might help. Actually I am asking if we can speed clique with additional information which gives upper bound.  
> **username_2**: Can you provide a sample of those graph classes which clique is NP-hard but coloring is P?  
> **username_0**: @Saeed according to graphclases.org example is (3K_1,co-K_{1,5})-free -- check details for reference, link: http://graphclasses.org/classes/AUTO_2153.html  
> **username_3**: Doesn't the "it is still NP-hard" part of your posting answer your own question?  
> **username_0**: @DavidEppstein I think the upper bound makes it at least slightly easier/faster.  

---

## 0 answers

