Perfection thickness of graphs

DOI10.1016/S0012-365X(99)00322-2MaRDI QIDQ1974539zbMATH OpenOpenAlexFDO

Authors Hirotsugu Asari, Tao Jiang, André Kündgen, Douglas B. West

Publication date 7 May 2000

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)00322-2

zbMATH Keywords

bipartite graphsperfect graphsthickness

Mathematics Subject Classification ID

Perfect graphs (05C17) Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

For a graph \(G\), let \(f(G)\) be the least number of perfect subgraphs of \(G\) whose union is \(G\). Let \(f(n)= \max\{f(G):|V(G)|= n\}\). Improving results of Zs. Tuza, the authors prove that \[ \textstyle{{1\over 2}}(\log n-\log\log n- O(1))\leq f(n)\leq \lceil\log n\rceil, \] where \(\log\) denotes the base-2 logarithm.

Recommendations

• scientific article; zbMATH DE number 3941576
• A note on perfect graphs
• Perfect graph decompositions
• Perfect couples of graphs
• Minimal imperfect graphs: A simple approach

Cited in

(2)

• Precedence thinness in graphs
• scientific article; zbMATH DE number 3941576 (Why is no real title available?)

This page was built for publication: Perfection thickness of graphs

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