Glebova, Olga and Metelsky, Yury and Skums, Pavel - Krausz dimension and its generalizations in special graph classes

dmtcs:623 - Discrete Mathematics & Theoretical Computer Science, March 16, 2013, Vol. 15 no. 1
Krausz dimension and its generalizations in special graph classes

Authors: Glebova, Olga and Metelsky, Yury and Skums, Pavel

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.


Source : oai:HAL:hal-00990610v1
Volume: Vol. 15 no. 1
Section: Graph Theory
Published on: March 16, 2013
Submitted on: April 12, 2011
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 40 times.
This article's PDF has been downloaded 43 times.