Regular subpseudographs of regular pseudographs
It is easily seen that each \(r\)-regular graph has an \((r-1)\)-regular subgraph for \(1\leq r\leq 3\). The well-known Berge conjecture that each 4- regular graph has a 3-regular subgraph has been proved in author's paper [Math. Notes 36, 612-623 (1984; Zbl 0558.05051); translation from Mat. Zametki 36, No. 2, 239-259 (1984)]. It will be proved in this note that for arbitrary \(r\geq 5\) there exists an \(r\)-regular graph that does not have any \((r-1)\)-regular subgraph. The following natural question arises: For what \(r\) and \(\rho\) does each \(r\)-regular graph have a \(\rho\)-regular subgraph? (For example, Erdős has asked: For what \(r\) each \(r\)-regular graph has a 3-regular subgraph?) In the present note we give an exhaustive solution of this problem for the class of regular pseudographs.
- Regular colorings in regular graphs
- Maximum hypergraphs without regular subgraphs
- scientific article; zbMATH DE number 3902701 (Why is no real title available?)
- scientific article; zbMATH DE number 691480 (Why is no real title available?)
- scientific article; zbMATH DE number 1456823 (Why is no real title available?)
- scientific article; zbMATH DE number 2188467 (Why is no real title available?)
- Three-regular subgraphs of four-regular graphs
This page was built for publication: Regular subpseudographs of regular pseudographs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1813087)
