A note on domatically critical and cocritical graphs
Igor Edmundovich Zverovich, Vadim E. Zverovich · Czechoslovak Mathematical Journal · 1991
This paper deals with domatically critical and cocritical graphs.Two problems concerning such graphs are settled.With minor adaptations, we adopt the terminology ofHarary [3].be an undirected graph with no loops and multiple edges., v e V(H)}.We denote by p(G) and q(G) the number of vertices and edges of G, respectively.Finally, <5(G) will denote the minimum degree among the vertices of G.A graph G is calledWe shall say that the partition V i9 V 2 , • ., V d of V{G) possesses property (P), if it satisfies the following conditions:(i) Vi is an independent set for any / e {1, 2,..., d}, (ii) the subgraph G itj of G, induced by V t u Vj, is a disjoint union of stars (K t is not a star) for any i,j є {l, 2, ..., d}, і ф j.Conjecture [4].Let G be a graph, d(G) = d and let there exist a partition V\, V 2 , ..., V d of V(G) satisfying (P).Then G is domatically critical.