On Locally-Balanced 2-Partitions of Complete Multipartite Graphs
DOI:
https://doi.org/10.51408/1963-0001Keywords:
2-partition, Locally-balanced 2-partition, Equitable coloring, Complete multipartite graphAbstract
A 2-partition of a graph G is a function f : V (G) →{White; Black}. A 2-partition f of a graph G is locally-balanced with an open neighborhood if for every ϑ ϵ V (G), ||{u ϵ NG(v): f (u) = White} |-| {u ϵ NG(v): f(u) = Black} ≤1; where NG(v) ={u ϵ V (G): uv ϵ E(G) }. A 2-partition f՛ 0 of a graph G is locallybalanced with a closed neighborhood if for every v ϵ V(G), ||{u ϵ NG(v): f՛ (u) = White} |-| {u ϵ NG[v]:; where NG[v] = NG(v)∪{v.} In this paper we give necessary and su±cient conditions for the existence of locally-balanced 2-partitions of complete multipartite graphs
References
C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985.
S.V. Balikyan, “On existence of certain locally-balanced 2-partition of a tree", Mathematical Problems of Computer Science, Vol. 30, pp. 25-30, 2008.
S.V. Balikyan and R. R. Kamalian, “On existence of 2-partition of a tree, which obeys the given priority", Mathematical Problems of Computer Science, Vol. 30, pp. 31-35, 2008.
S.V. Balikyan and R. R. Kamalian, “Necessary and sufficient condition for existence of locally-balanced 2-partition of a tree under the extended definition of a neighbourhood of a vertex", Mathematical Problems of Computer Science, vol. 31, pp. 116-121, 2008.
A. H. Gharibyan and P.A. Petrosyan, “Locally-balanced 2-partitions of complete multipartite graphs", 6th Polish Combinatorial Conference, Bedlewo, Poland, p. 19, 2016.
A .H. Gharibyan and P.A. Petrosyan, “On locally-balanced 2-partitions of some graphs", Proceedings of the CSIT Conference, Yerevan, pp. 196-197, 2017.
A. Hajnal and E. Szemeredi, “Proof of a conjecture of P. Erdős", Combinatorial theory and its applications, II (Proc. Colloq., Balatonfred, 1969), North-Holland, pp. 601-623, 1970.
G. Chartrand and P. Zhang, Chromatic Graph Theory, Discrete Mathematics and Its Applications, CRC Press, 2009.
W. Meyer, “Equitable coloring", American Mathematical Monthly, vol. 80, no. 8, pp. 920-922, 1 973.
A.V. Kostochka, “Equitable colorings of outerplanar graphs", Discrete Mathematics vol. 258, pp. 373-377, 2002.
J. Kratochvil, “Complexity of hypergraph coloring and Seidel's switching", Graph Theoretic Concepts in Computer Science, 29th International Workshop, WG 2003, Elspeet, The Netherlands, Revised Papers, vol. 2880, pp. 297-308, June 19-21, 2003.
S. V. Balikyan and R. R. Kamalian, “On NP-completeness of the problem of existence of locally-balanced 2-partition for bipartite graphs G with Δ(G) = 3", Doklady NAN RA, vol. 105, no. 1, pp. 21-27, 2005.
S.V. Balikyan and R.R. Kamalian, “On NP-completeness of the problem of existence of locally-balanced 2-partition for bipartite graphs G with Δ(G) = 4 under the extended definition of the neighbourhood of a vertex", Doklady NAN RA, vol. 106, no. 3, pp. 218-226, 2006.
D. de Werra, “On good and equitable colorings", In Cahiers du C.E.R.O., vol. 17, pp. 417-426, 1975.
D.B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 2001.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
