Packing 3-vertex paths in cubic 3-connected graphs
From MaRDI portal
Publication:6208050
arXiv0801.1239MaRDI QIDQ6208050FDOQ6208050
Authors: Alexander Kelmans 
Publication date: 7 January 2008
Abstract: Let v(G) and p(G) be the number of vertices and the maximum number of disjoint 3-vertex paths in G, respectively. We discuss the following old Problem: Is the following claim (P) true ? (P) if G is a 3-connected and cubic graph, then p(G) = [v(G)/3], where [v(G)/3] is the floor of v(G)/3. We show, in particular, that claim (P) is equivalent to some seemingly stronger claims. It follows that if claim (P) is true, then Reed's dominating graph conjecture (see [14]) is true for cubic 3-connected graphs.
Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10)
This page was built for publication: Packing 3-vertex paths in cubic 3-connected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6208050)
