Packing 3-Vertex Paths in Claw-Free Graphs
| dc.creator | Kelmans, Alexander | |
| dc.date | 2007-11-25 | |
| dc.date.accessioned | 2026-07-07T08:44:52Z | |
| dc.date.available | 2026-07-07T08:44:52Z | |
| dc.description | An L-factor of a graph G is a spanning subgraph of G whose every component is a 3-vertex path. Let v(G) denote the number of vertices of G. A graph is called claw-free if it does not have a subgraph isomorphic to the graph with 4 vertices and 3 edges having a common vertex. Our results include the following. Let G$ be a 3-connected claw-free graph, x be a vertex, e = xy be an edge, and P be a 3-vertex path in G. Then (c1) if v(G) = 0 mod 3, then G has an L-factor containing (avoiding) e, (c2) if v(G) = 1 mod 3, then G - x has a L-factor, (c3) if v(G) = 2 mod 3, then G - x -y has an L-factor, (c4) if v(G) = 0 mod 3 and G is either cubic or 4-connected, then G - P has an L-factor, and (c5) if G is cubic and E is a set of three edges in G, then G - E has an L -factor if and only if the subgraph induced by E in G is not a claw and not a triangle. Keywords: claw-free graph, cubic graph, L-packing, L-factor. | |
| dc.description | 12 pages | |
| dc.identifier | https://arxiv.org/abs/0711.3871 | |
| dc.identifier | http://arxiv.org/abs/0711.3871 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/142811 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C10 | |
| dc.title | Packing 3-Vertex Paths in Claw-Free Graphs | |
| dc.type | text |