13
$\begingroup$

This is a question inspired by the H-free cut problem. Given a graph, a partition of its vertex set $V$ into $r$ parts $V_1, V_2, \ldots, V_r$ is $H$-free if $G[V_i]$ does not induce a copy of $H$ for all $i$, $1 \leq i \leq r$.

I wish to consider the following question:

What is the least $r$ for which there exists a $H$-free partition into $r$ parts?

Notice that when $H$ is a single edge, then this amounts to finding the chromatic number, and is already NP-complete. I am wondering if it is easier to show NP-completeness for any fixed $H$ for this problem (easier, as compared to showing it for $H$-free cut). I even thought it might be obvious, but I didn't get anywhere. It is entirely possible I'm missing something quite straightforward, and if this is the case, I'd appreciate some pointers!

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ You mean: for all $i$ and for all $U \subseteq V_i$, the subgraph of $G$ induced by $U$ is not isomorphic to $H$? $\endgroup$
    – Jukka Suomela
    Sep 2, 2010 at 23:06
  • $\begingroup$ I think that RJK’s answer to the other problem linked from this applies to this problem (in fact better than to the other problem). $\endgroup$
    – Tsuyoshi Ito
    Sep 3, 2010 at 3:12
  • $\begingroup$ @Jukka: Quite so, I do. Thanks for the pointer, and forgive me for being too lazy (at least for now) to update the question accordingly! $\endgroup$
    – Neeldhara
    Sep 4, 2010 at 18:19
  • $\begingroup$ @Tsuyoshi: It does, and now I have a more elaborate version of the answer here as well! However, I should say that I posted this because I found myself in the "I-hit-a-roadblock-while-thinking-about-X and Y-seems-an-related-and-easier-start" situation. I just thought I should share the details of Y for the rest who were thinking about X, and it wasn't primarily intended to be a reference request :) $\endgroup$
    – Neeldhara
    Sep 4, 2010 at 18:22
  • $\begingroup$ Serge Gaspers referred to an old (1980) paper of Lewis and Yannakakis that seems very relevant here! $\endgroup$
    – RJK
    Sep 4, 2010 at 23:31

2 Answers 2

Reset to default
5
$\begingroup$

The earliest references I know to this type of problem are the following. These are also referred to in the Cowen, Goddard and Jesurum paper I mentioned in the other thread.

Andrews and Jacobson. (1985) On a generalization of chromatic number. In Proc. 16th Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton 1985), Congr. Numer. 47 33–48.

Cowen, Cowen and Woodall. (1986) Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency. J. Graph Theory 10 187–195.

Harary. (1985) Conditional colorability in graphs. In Graphs and Applications (Boulder 1982), Wiley–Interscience, pp. 127–136.

Harary, and Jones (nee Fraughnaugh). (1985) Conditional colorability II: Bipartite variations. In Proc. Sundance Conference on Combinatorics and Related Topics (Sundance 1985), Congr. Numer. 50 205–218.

AFAIK, there isn't yet a paper giving the explicit P/NP-c dichotomy for various choices of H. This has been done, though, by Hell and Nesetril, for another type of generalisation of the chromatic number, "H-colourings", to homomorphisms.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks much for your very detailed answer - greatly appreciated. That's a substantial addition to my reading list, it should keep me busy for a while! $\endgroup$
    – Neeldhara
    Sep 4, 2010 at 18:18
  • $\begingroup$ Well, not a problem, although, as I mentioned before, besides the JGT paper, it's pretty hard to track these down. (In fact, I must admit I haven't much succeeded yet, despite having had access to plenty of Canadian university libraries.) In any case, the Cowen, Goddard and Jesurum paper is probably most relevant and answers your/Moron's question for H being a fixed star, even restricted to planar graphs. Probably the nicest open (I think?) classes of H to sink your teeth into would be cycles or cliques. $\endgroup$
    – RJK
    Sep 4, 2010 at 20:31
5
$\begingroup$

In "Vertex partitioning into fixed additive hereditary properties is NP-hard", Alastair Farrugia proves that if $F_1$ and $F_2$ are two families of connected graphs, then the problem of partitioning a graph into two parts one of which is $F_1$-free and the other $F_2$-free is NP-hard, except when both $F_1$ and $F_2$ consist of the single edge.

(F-free = {for all H in F, H-free})

See www.combinatorics.org/Volume_11/PDF/v11i1r46.pdf

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.