### Abstract

Let G be a graph of minimum degree at least 2 with no induced subgraph isomorphic to K_{1, 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

## Fingerprint Dive into the research topics of 'Deploying robots with two sensors in K<sub>1, 6</sub>-free graphs'. Together they form a unique fingerprint.

## Cite this

Abbas, W., Egerstedt, M., Liu, C. H., Thomas, R., & Whalen, P. (2016). Deploying robots with two sensors in K

_{1, 6}-free graphs.*Journal of Graph Theory*,*82*(3), 236-252. https://doi.org/10.1002/jgt.21898