## 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_{1, 6}-free graphs'. Together they form a unique fingerprint.