Krausz dimension and its generalizations in special graph classes

MaRDI QIDQ5747376zbMATH OpenFDO

Authors Olga Glebova, Yury Metelsky, Pavel Skums

Publication date 14 February 2014

Full work available at URL https://arxiv.org/abs/1107.3597, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1837/0.html

zbMATH Keywords

chordal graphintersection graphKrausz dimensionlinear \(k\)-uniform hypergraphpolar graphsplit graph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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 $kdi{m}_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 $$ 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 $mgeq1$, even if restricted to (1,2)-colorable graphs, but the problem $$ is polynomially solvable for $(infty,1)$-polar graphs for every fixed $k,mgeq1$.

Recommendations

• scientific article; zbMATH DE number 1107734
• Generalized partitions of graphs
• scientific article; zbMATH DE number 5054160
• The Krausz decomposition in special classes of split graphs
• On the characterization of graphs with an equivalence partition number at most three in the class of chordal graphs

Cited in

(6)

• scientific article; zbMATH DE number 1107734 (Why is no real title available?)
• scientific article; zbMATH DE number 811560 (Why is no real title available?)
• A finite characterization and recognition of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 in the class of threshold graphs
• The Krausz decomposition in special classes of split graphs
• scientific article; zbMATH DE number 5054160 (Why is no real title available?)
• The (generalized) orthogonality dimension of (generalized) kneser graphs: bounds and applications

This page was built for publication: Krausz dimension and its generalizations in special graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5747376)