Efficient 2-Distance Coloring Method for Maximum and Average Sparse Graphs in Resource Allocation Optimization of Microgrids
Main Article Content
Abstract
In microgrids management, optimizing resource allocation and enhancing efficiency are critical challenges. This paper introduces the 2-distance coloring technique as a novel approach to address these issues by focusing on the coloring problem of sparse graphs. Through rigorous theoretical derivation, we establish the minimum number of colors required for 2-distance coloring in sparse graph scenarios. Specifically, we demonstrate that for a graph G with an average maximum degree less than 2+17/20 and a maximum degree of 6, it can be list 2-distance colored using no more than 11 colors. This means that, given any set of 11 colors for each vertex, a valid 2-distance coloring can be achieved, ensuring no two adjacent vertices share the same color. This finding is pivotal, as it sets a precedent for the number of resources needed to efficiently manage and allocate resources in microgrids systems through 2-distance coloring. The application of this technique in microgrids promises to revolutionize resource distribution, reducing overlap and maximizing efficiency across the network.
Article Details
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.
References
M. Shao, X. Wu, and Y. Fu, “Scalable nearest neighbor sparse graph approximation by exploiting graph structure,” IEEE Transactions on Big Data, vol. 2, no. 4, pp. 365–380, dec 2016.
K. Lai, L. Wen, J. Lei, P. Xiao, A. Maaref, and M. A. Imran, “Sub-graph based joint sparse graph for sparse code multiple access systems,” IEEE Access, vol. 6, pp. 25 066–25 080, 2018.
A. Adler, M. Elad, and Y. Hel-Or, “Linear-time subspace clustering via bipartite graph modeling,” IEEE Transactions on Neural Networks and Learning Systems, vol. 26, no. 10, pp. 2234–2246, oct 2015.
H. Alghamdi and R. Dahyot, "Sliced L2 Distance for Colour Grading," 2021 29th European Signal Processing Conference (EUSIPCO), Dublin, Ireland, 2021, pp. 671-675
B. Li, Y. -K. Lai and P. L. Rosin, "Sparse Graph Regularized Mesh Color Edit Propagation," in IEEE Transactions on Image Processing, vol. 29, pp. 5408-5419, 2020
E. Kay, “Graph theory with applications,” Journal of the Operational Research Society, vol. 28, no. 1, pp. 237–238, apr 1977.
Y. Bu and X. Wang, “r-hued coloring of planar graphs without short cycles,” Discrete Mathematics, Algorithms and Applications, vol. 12, no. 03, p. 2050034, jun 2020.
W. Wang and K. Lih, “Labeling planar graphs with conditions on girth and distance two,” SIAM Journal on Discrete Mathematics, vol. 17, no. 2, pp. 264–275, jan 2003.
Y. Li, Y. Li, J. Yao, Y. Gong and L. Li, "Global Color Consistency Correction for Large-Scale Images in 3-D Reconstruction," in IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, vol. 15, pp. 3074-3088, 2022.
C. Alappat, G. Hager, O. Schenk and G. Wellein, "Level-Based Blocking for Sparse Matrices: Sparse Matrix-Power-Vector Multiplication," in IEEE Transactions on Parallel and Distributed Systems, vol. 34, no. 2, pp. 581-597, 1 Feb. 2023.
B. O. V and I. A. O, “2-distance (△ + 2)-coloring of planar graphs with girth six and △≥18,” Discrete Math., vol. 309, no. 23–24, pp. 6496–6502, dec 2009. [Online]. Available: https://doi.org/10.1016/j.disc.2009.06.029
O. V. Borodin, A. O. Ivanova, “List 2-distance △+2-coloring of planar graphs with girth six and △≥24,” vol. 50, no. 6, p. 1216–1224, 2009.
Y. Zhang, M. Liu, J. He, F. Pan and Y. Guo, "Affinity Fusion Graph-Based Framework for Natural Image Segmentation," in IEEE Transactions on Multimedia, vol. 24, pp. 440-450, 2022.
Y. -H. Chao, H. Hong, G. Cheung and A. Ortega, "Pre-Demosaic Graph-Based Light Field Image Compression," in IEEE Transactions on Image Processing, vol. 31, pp. 1816-1829, 2022.
W. Gerd, “Graphs with given diameter and a coloring problem,” Ger-many, University of Dortmund, pp. 1–11, 1977.
C. Thomassen, “The square of a planar cubic graph is 7-colorable,” Journal of Combinatorial Theory, Series B, vol. 128, pp. 192–218, jan 2018.
M. Molloy and M. R. Salavatipour, “A bound on the chromatic number of the square of a planar graph,” Journal of Combinatorial Theory, Series B, vol. 94, no. 2, pp. 189–213, jul 2005.
D. W. Cranston and R. ˇSkrekovski, “Sufficient sparseness conditions for g2 to be (△ + 1)-choosable, when △≥5,” Discrete Appl. Math., vol. 162, pp. 167–176, jan 2014.
D. W. Cranston, R. Erman, and R. ˇSkrekovski, “Choosability of the square of a planar graph with maximum degree four,” vol. 59, no. 1, pp. 86–97, Jun. 2013.
Y. Bu and X. Lv, “The choosability of the 2-distance coloring of a graph,” Journal of Zhejiang Normal University (Nat.Sci.), vol. 38, pp. 279-285, 2015.