Krausz dimension and its generalizations in special graph classes

Details Krausz dimension and its generalizations in special graph classes Krausz dimension and its generalizations in special graph classes

2011-07-18

arxiv.org/abs/1107.3597v1

Mathematics

Combinatorics

Scientific paper

A {\it krausz $(k,m)$-partition} of a graph $G$ is the partition of $G$ into cliques, such that any vertex belongs to at most $k$ cliques and any two cliques have at most $m$ vertices in common. The {\it $m$-krausz} dimension $kdim_m(G)$ of the graph $G$ is the minimum number $k$ such that $G$ has a krausz $(k,m)$-partition. 1-krausz dimension is known and studied krausz dimension of graph $kdim(G)$. In this paper we prove, that the problem $"kdim(G)\leq 3"$ is polynomially solvable for chordal graphs, thus partially solving the problem of P. Hlineny and J. Kratochvil. We show, that the problem of finding $m$-krausz dimension is NP-hard for every $m\geq 1$, even if restricted to (1,2)-colorable graphs, but the problem $"kdim_m(G)\leq k"$ is polynomially solvable for $(\infty,1)$-polar graphs for every fixed $k,m\geq 1$.

Affiliated with

Also associated with

No associations

Rating

Krausz dimension and its generalizations in special graph classes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Krausz dimension and its generalizations in special graph classes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Krausz dimension and its generalizations in special graph classes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-513231