Given a simple undirected graph G, its Grundy chromatic number Γ(G) (or Grundy number) defines the worst-case behavior for the well-known and widely-used greedy first-fit coloring heuristic. ...Specifically, Γ(G) is the largest k for which a k-coloring can be obtained with the first-fit heuristic. In this paper, we address the Grundy coloring problem, the optimization problem consisting of obtaining the Grundy number of a graph. First, we propose a new combinatorial upper bound for the problem. Second, we describe a standard integer programming formulation and a formulation by representatives. The latter attempts to overcome the symmetries in the problem and relies on the idea that a subset of the vertices in the graph can be represented by one of its vertices, denoted as a representative. Finally, as integer programming approaches can struggle to tackle instances of the problem, we devise a biased random-key genetic algorithm (BRKGA) to obtain heuristic solutions in low computational times. Computational experiments show that our new upper bound can improve over well-established combinatorial bounds available in the literature for several instances. The results also indicate that the formulation by representatives has an overall superior performance than the standard formulation, achieving better results for the denser instances while slightly underperforming on the sparser ones. Furthermore, the BRKGA can find high-quality solutions and can be used with confidence in large instances where the formulations fail.
•We study the Grundy coloring problem - optimal solution is the Grundy chromatic number.•A new combinatorial upper bound can outperform a well-known one for many instances.•Two integer programming formulations are proposed and compared.•Our BRKGA is robust and obtains state-of-the-art results in low computational times.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
42.
Rainbow Coloring of Three New Graph Classes Fredlina, Ketut Queena; Salman, A.N.M.; Julihara, I Gede Putu Krisna ...
Journal of physics. Conference series,
02/2021, Volume:
1783, Issue:
1
Journal Article
Peer reviewed
Open access
Let G be a simple, finite, and connected graph. A path in an edge colored graph is said a rainbow path, if no two edges on the path have the same color. The graph G is called a rainbow-connected, if ...any two vertices are connected by a rainbow path. An edge-coloring of such G is rainbow coloring. The rainbow connection number rc(G) of G is the smallest number of colors needed in order to make G rainbow connected. In this paper, we introduce three new graph classes, namely tunjung graphs, sandat graphs, and jempiring graphs. We determine the rainbow connection number of the graphs.
In 1943, Hadwiger conjectured that every graph with no Kt minor is (t−1)-colorable for every t≥1. In the 1980s, Kostochka and Thomason independently proved that every graph with no Kt minor has ...average degree O(tlogt) and hence is O(tlogt)-colorable. We show that every graph with no Kt minor is O(t(logt)β)-colorable for every β>1/4, making the first improvement on the order of magnitude of the Kostochka-Thomason bound.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Square coloring is a variant of graph coloring where vertices within distance two must receive different colors. When considering planar graphs, the most famous conjecture (Wegner, 1977) states that ...32Δ+1 colors are sufficient to square color every planar graph of maximum degree Δ. This conjecture has been proven asymptotically for graphs with large maximum degree. We consider here planar graphs with small maximum degree and show that 2Δ+7 colors are sufficient, which improves the best known bounds when 6⩽Δ⩽31.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Abstract
Let
G = (V,E)
be a connected graph with
|V|=n
and
|E|=m.
A bijection
f: V(G)
U
E(G)
→ {1,2,3,
…,n
+
m}
is called local antimagic vertex total coloring if for any two adjacent vertices
u
and
...v, w
t
(u)
≠
w
t
(v),
where
w
t
(u)
= ∑
e∈E(u)
f(e) + f(u),
and
E (u)
is a set of edges incident to
u.
Thus any local antimagic vertex total labeling induces a proper vertex coloring of
G
where the vertex
v
is assigned the color
w
t
(v).
The local antimagic vertex total chromatic number
χ
1να
t
(G)
is the minimum number of colors taken over all colorings induced by local antimagic vertex total. In this paper we investigate local antimagic vertex total coloring on fan graph
(F
n
)
and graph resulting from comb product operation of
F
n
and
F
3
which denoted by
F
n
t> F
3
.
We get two theorems related to the local antimagic vertex total chromatic number. First,
χ
1να
t
(F
n
) =
3 where
n> 3.
Second, 3 < χ1ναt(Fn >
F
3
)
< 5 where n > 3.
Abstract
Locating rainbow connection number determines the minimum number of colors connecting any two vertices of a graph with a rainbow vertex path and also verifies that the given colors produce a ...different rainbow code for each vertex. Locating rainbow connection number of graphs is a new mathematical concept, especially in graph theory, which combines the concepts of the rainbow vertex coloring and the partition dimension. In this paper, we determine the locating rainbow connection number of amalgamation of complete graphs.
Mobile edge computing (MEC) has attracted great interests as a promising approach to augment computational capabilities of mobile devices. An important issue in the MEC paradigm is computation ...offloading. In this paper, we propose an integrated framework for computation offloading and interference management in wireless cellular networks with MEC. In this integrated framework, we formulate the computation offloading decision, physical resource block (PRB) allocation, and MEC computation resource allocation as optimization problems. The MEC server makes the offloading decision according to the local computation overhead estimated by all user equipments (UEs) and the offloading overhead estimated by the MEC server itself. Then, the MEC server performs the PRB allocation using the graph coloring method. The outcomes of the offloading decision and PRB allocation are then used to distribute the computation resource of the MEC server to the UEs. Simulation results are presented to show the effectiveness of the proposed scheme with different system parameters.
In this study, a cellular system with a large-scale distributed multi-user multi-input multi-output (MU-MIMO) is considered, in which a large number of distributed antennas are deployed spatially ...over each base station coverage area (cell) and user clusters are formed in each cell to perform cluster-wise distributed MU-MIMO in parallel. In such a cellular system, the intercell and intracell interferences coexist and limit the link capacity. In this study, a 2-layer interference coordination (IC) framework that can effectively mitigate the two types of interferences simultaneously is proposed. In the 1 st layer, the intercell IC is performed in a centralized manner by the non-real-time (non-RT) radio access network intelligent controller (RIC), and then in the 2 nd layer, under the condition of the results in the 1 st layer, intracell IC is done by each near-RT RICs in a decentralized manner. Furthermore, a restricted conditional graph coloring algorithm (RCGCA) suitable for this 2-layer IC framework is proposed. The proposed RCGCA is designed to be applied on a partial pre-colored graph, such that when it is applied in the 2-layer IC framework, it satisfies the requirement that the 2 nd layer coloring must be applied under the condition of the pre-coloring results of the 1 st layer. In addition, by restricting the total number of colors, the RCGCA can tradeoff between improving the capacity due to interference mitigation and degrading the capacity due to bandwidth partition, thereby maximizing the link capacity. We compare the link capacity achievable by the proposed 2-layer IC framework based on RCGCA with that achievable by the well-known fractional frequency reuse (FFR) scheme, no interference coordination case, fully centralized framework, and fully decentralized framework. Computer simulations confirm that our proposed 2-layer IC framework based on RCGCA can significantly improve the link capacity.
Scheduling lectures is a routine work in the academic system in higher education every time to facing a new semester. In the implementation, often the schedule that has been issued has not been fixed ...so it requires to rescheduling. For this reason, a new lecture scheduling system is needed using the Welch Powell Graph Coloring Algorithm. This study was done in the Informatics Engineering Departement of Universitas Malikussaleh using the subjects schedule during 2013, 2014 and 2015. Based on the results of this study it can be concluded that the Welch Powell Graph Coloring Algorithm can solve properly the problem of scheduling lectures, in this case there are no clashes between scheduled components.
Let G be a simple graph, let d(v) denote the degree of a vertex v and let g be a nonnegative integer function on V (G) with 0 ≤ g(v) ≤ d(v) for each vertex v ∈ V (G). A gc-coloring of G is an edge ...coloring such that for each vertex v ∈ V (G) and each color c, there are at least g(v) edges colored c incident with v. The gc-chromatic index of G, denoted by χ′gc (G), is the maximum number of colors such that a gc-coloring of G exists. Any simple graph G has the gc-chromatic index equal to δg(G) or δg(G) − 1, where δg(G)=minv∈V(G)⌊d(v)/g(v)⌋. A graph G is nearly bipartite, if G is not bipartite, but there is a vertex u ∈ V (G) such that G − u is a bipartite graph. We give some new sufficient conditions for a nearly bipartite graph G to have χ′gc (G) = δg(G). Our results generalize some previous results due to Wang et al. in 2006 and Li and Liu in 2011.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OBVAL, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
PDF
