Factor d-domatic colorings of graphs

Noga Alon, Guillaume Fertin, Arthur L. Liestman, Thomas C. Shermer, Ladislav Stacho

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

Consider a graph and a collection of (not necessarily edge-disjoint) connected spanning subgraphs (factors) of the graph. We consider the problem of coloring the vertices of the graph so that each color class of the vertices dominates each factor. We find upper and lower bounds on α(t,k), which we define as the minimum radius of domination d such that every graph with a collection of k factors can be vertex colored with t colors so that each color class d-dominates each factor. It is perhaps surprising that the upper bound is finite and does not depend on the order of the graph. We obtain similar results for a variant of the problem where the number of colors is equal to the number of factors and each color class must d-dominate only the corresponding factor rather than all factors.

Original languageEnglish (US)
Pages (from-to)17-25
Number of pages9
JournalDiscrete Mathematics
Volume262
Issue number1-3
DOIs
StatePublished - Feb 6 2003

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • All-factor
  • Coloring
  • Distance
  • Domination
  • Factor
  • Matched-factor

Fingerprint Dive into the research topics of 'Factor d-domatic colorings of graphs'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Fertin, G., Liestman, A. L., Shermer, T. C., & Stacho, L. (2003). Factor d-domatic colorings of graphs. Discrete Mathematics, 262(1-3), 17-25. https://doi.org/10.1016/S0012-365X(02)00518-6