Partitioning Claw-Free Subcubic Graphs into Two Dominating Sets

2020 
A dominating set in a graph G is a set $$S\subseteq V(G)$$ such that every vertex in $$V(G){\setminus } S$$ has at least one neighbor in S. Let G be an arbitrary claw-free graph containing only vertices of degree two or three. In this paper, we prove that the vertex set of G can be partitioned into two dominating sets $$V_1$$ and $$V_2$$ such that for $$i=1,2$$, the subgraph of G induced by $$V_i$$ is triangle-free and every vertex $$v\in V_i$$ also has at least one neighbor in $$V_i$$ if v has degree three in G. This gives an affirmative answer to a problem of Bacso et al. and generalizes a result of Desormeaux et al.
    • Correction
    • Source
    • Cite
    • Save
    12
    References
    0
    Citations
    NaN
    KQI
    []