Abstract
Let G be a graph of minimum degree at least 2 with no induced subgraph isomorphic to K1, 6. We prove that if G is not isomorphic to one of eight exceptional graphs, then it is possible to assign two-element subsets of {1,2,3,4,5} to the vertices of G in such a way that for every i∈{1,2,3,4,5} and every vertex v∈V(G) the label i is assigned to v or one of its neighbors. It follows that G has fractional domatic number at least 5/2. This is motivated by a problem in robotics and generalizes a result of Fujita, Yamashita, and Kameda who proved that the same conclusion holds for all 3-regular graphs.
Original language | English (US) |
---|---|
Pages (from-to) | 236-252 |
Number of pages | 17 |
Journal | Journal of Graph Theory |
Volume | 82 |
Issue number | 3 |
DOIs | |
State | Published - Jul 1 2016 |
All Science Journal Classification (ASJC) codes
- Geometry and Topology
Keywords
- K-free
- domination
- fractional domatic number