Krausz dimension and its generalizations in special graph classes

Abstract

A 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 m-krausz dimension kdimm(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) ≤ 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 even if restricted to (1, 2)-colorable graphs, but the problem “kdimm(G) ≤ k” is polynomially solvable for (∞, 1)-polar graphs for every fixed k, m ≥ 1.