A multicell massive multiple-input multiple-output (MIMO) system, which utilizes a large number of base-station antennas to simultaneously serve a set of users, suffers from pilot contamination (PC) ...due to unavoidable reuse of pilots in adjacent cells. In this paper, a weighted-graph-coloring-based pilot decontamination (WGC-PD) scheme is proposed to mitigate PC for multicell massive MIMO systems. Specifically, based on limited cooperation among cells, an edge-weighted interference graph (EWIG) is first constructed to depict the potential PC relationship among users, whereby two users in different cells are connected by a weighted edge, indicating the strength of potential PC when they reuse the same pilot. Then, inspired by classical graph coloring algorithms, we develop the WGC-PD scheme by denoting each color as a pilot and each vertex as a user in the EWIG, which is able to mitigate PC by assigning different pilots to connected users with a large weight in a greedy way with insufficient pilot resource. Compared with exhaustive search among numerous pilot assignment solutions, the proposed WGC-PD scheme is able to mitigate PC with significantly reduced complexity, which is verified by numerical results.
A vertex coloring c : V(G) → ℕ of a non-trivial connected graph G is called a sigma coloring if σ(u) ≠ σ(v) for any pair of adjacent vertices u and v. Here, σ(x) denotes the sum of the colors ...assigned to vertices adjacent to x. The sigma chromatic number of G, denoted by σ(G), is defined as the fewest number of colors needed to construct a sigma coloring of G. In this paper, we determine the sigma chromatic numbers of the Sierpiński gasket graphs and the Hanoi graphs. Moreover, we prove the uniqueness of the sigma coloring for Sierpiński gasket graphs.
A note on fractional DP-coloring of graphs Dominik, Daniel; Kaul, Hemanshu; Mudrock, Jeffrey A.
Discrete mathematics,
October 2024, 2024-10-00, Volume:
347, Issue:
10
Journal Article
Peer reviewed
DP-coloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvořák and Postle in 2015. In 2019, Bernshteyn, Kostochka, and Zhu introduced a fractional version ...of DP-coloring. They showed that unlike the fractional list chromatic number, the fractional DP-chromatic number of a graph G, denoted χDP⁎(G), can be arbitrarily larger than χ⁎(G), the graph's fractional chromatic number. We generalize a result of Alon, Tuza, and Voigt (1997) on the fractional list chromatic number of odd cycles, and, in the process, show that for each k∈N, χDP⁎(C2k+1)=χ⁎(C2k+1). We also show that for any n≥2 and m∈N, if p⁎ is the solution in (0,1) to p=(1−p)n then χDP⁎(Kn,m)≤1/p⁎, and we prove a generalization of this result for multipartite graphs. Finally, we determine a lower bound on χDP⁎(K2,m) for any m≥3.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Graph coloring is one of the most studied NP-hard problems with a wide range of applications. In this work, the first solution-driven multilevel algorithm for this computationally challenging problem ...is investigated. Following the general idea of multilevel optimization, the proposed algorithm combines an original solution-driven coarsening procedure with an uncoarsening procedure as well as an effective refinement procedure. The algorithm is assessed on 47 popular DIMACS and COLOR benchmark graphs, and compared with 13 state-of-the-art coloring methods in the literature. We close one large graph (wap01a.col) by providing its chromatic number for the first time. Impacts of the key ingredients of the algorithm are also investigated.
•Graph coloring is a highly popular and important problem with many practical applications.•We present the first solution-driven multilevel algorithm for solving the problem.•We present extensive computational results on the popular DIMACS benchmark graphs.•We show comparisons with 13 state-of-the-art coloring algorithms in the literature.•The chromatic number of a large graph is proven for the first time.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
•Determines a number of upper and lower bounds.•Shows how problems can be broken up into smaller subproblems.•Identifies where â; difficult to solveâ; problems reside.
The maximum happy vertices ...problem involves determining a vertex colouring of a graph such that the number of vertices assigned to the same colour as all of their neighbours is maximised. This problem is trivial if no vertices are precoloured, though in general it is NP-hard. In this paper we derive a number of upper and lower bounds on the number of happy vertices that are achievable in a graph and then demonstrate how certain problem instances can be broken up into smaller subproblems. Four different algorithms are also used to investigate the factors that make some problem instances more difficult to solve than others. In general, we find that the most difficult problems are those with relatively few edges and/or a small number of precoloured vertices. Ideas for future research are also discussed.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
A star edge-coloring of a graph G is a proper edge-coloring without 2-colored paths and cycles of length 4. For a graph G, let the list star chromatic index of G be the minimum k such that for any ...k-uniform list assignment L for the set of edges, G has a star edge-coloring from L. In this paper we prove that the list star chromatic index of every k-degenerate graph G with maximum degree Δ is at most (3k−2) Δ − k2 + 2. For K4-minor free graphs (k=2), we decrease this bound to 3 Δ − 3, Δ ≥ 3. We do not use the discharging method but rather we use the fundamental structural properties of k-degenerate graphs and K4-minor free graphs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Vindicating a sophisticated but non-rigorous physics approach called the cavity method, we establish a formula for the mutual information in statistical inference problems induced by random graphs ...and we show that the mutual information holds the key to understanding certain important phase transitions in random graph models. We work out several concrete applications of these general results. For instance, we pinpoint the exact condensation phase transition in the Potts antiferromagnet on the random graph, thereby improving prior approximate results (Contucci et al., 2013) 34. Further, we prove the conjecture from Krzakala et al. (2007) 55 about the condensation phase transition in the random graph coloring problem for any number q≥3 of colors. Moreover, we prove the conjecture on the information-theoretic threshold in the disassortative stochastic block model (Decelle et al., 2011) 35. Additionally, our general result implies the conjectured formula for the mutual information in Low-Density Generator Matrix codes (Montanari, 2005) 73.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
PDF
