Krausz dimension and its generalizations in special graph classes
Pavel Skums, Yury Metelsky, Olga Glebova
Abstract
A Krausz (k,m)-partition of a graph
G is a decomposition 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. In particular, 1-Krausz dimension or
simply Krausz dimension kdim(G) is a well-known
graph-theoretical parameter. In this paper we prove that the problem
"kdim(G)≤3" is polynomially solvable for chordal
graphs, thus partially solving the open problem of P. Hlineny and
J. Kratochvil. We solve another open problem of P. Hlineny and J.
Kratochvil by proving that the problem of finding Krausz dimension is
NP-hard for split graphs and complements of bipartite graphs. We show
that the problem of finding m-Krausz dimension is NP-hard
for every m≥1, but the problem
"kdimm(G)≤k" is is fixed-parameter
tractable when parameterized by k and m for
(∞,1)-polar graphs. Moreover, the class of
(∞,1)-polar graphs with
kdimm(G)≤k is characterized by a finite
list of forbidden induced subgraphs for every
k,m≥1.
Full Text: PDF PostScript