Discrete Mathematics & Theoretical Computer Science 
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 mKrausz dimension kdimm(G) of the graph G is the minimum number k such that G has a Krausz (k,m)partition. In particular, 1Krausz dimension or simply Krausz dimension kdim(G) is a wellknown graphtheoretical 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 NPhard for split graphs and complements of bipartite graphs. We show that the problem of finding mKrausz dimension is NPhard for every m≥1, but the problem "kdimm(G)≤k" is is fixedparameter 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.
Source : ScholeXplorer
IsRelatedTo DOI 10.1016/j.disc.2007.12.082 Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.endm.2005.06.007
