2024/01/27 by Aram H. Gharibyan, Petros A. Petrosyan, Gharibyan, Aram H. +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2401.15490
openalex publication_date 2024/01/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A 2-partition of a graph G is a function f:V(G)→ \0,1\. A 2-partition f of a graph G is a locally-balanced with an open neighborhood if for every v∈ V(G), \vert \vert \u∈ NG(v)\colon f(u)=0\\vert - \vert \u∈ NG(v)\colon f(u)=1\\vert \vert≤ 1. A 2-partition f′ of a graph G is a locally-balanced with a closed neighborhood if for every v∈ V(G), \vert \vert \u∈ NG[v]\colon f′(u)=0\\vert - \vert \u∈ NG[v]\colon f′(u)=1\\vert \vert≤ 1. In this paper we prove that the problem of the existence of locally-balanced 2-partition with an open (closed) neighborhood is NP-complete for some restricted classes of graphs. In particular, we show that the problem of deciding if a given graph has a locally-balanced 2-partition with an open neighborhood is NP-complete for biregular bipartite graphs and even bipartite graphs with maximum degree 4, and the problem of deciding if a given graph has a locally-balanced 2-partition with a closed neighborhood is NP-complete even for subcubic bipartite graphs and odd graphs with maximum degree 3. Last results prove a conjecture of Balikyan and Kamalian.