Abstract
Let
G
be a nontrivial connected graph and let
c
:
V
(
G
) → ℕ be a vertex coloring of
G
, where adjacent vertices may have the same color. For a vertex
υ
of
G
, the color sum
σ
(
υ
) of
υ
is ...the sum of the colors of the vertices adjacent to
υ
. The coloring
c
is said to be a sigma coloring of
G
if
σ
(
u
) ≠
σ
(
υ
) whenever
u
and
υ
are adjacent vertices in
G
. The minimum number of colors that can be used in a sigma coloring of
G
is called the sigma chromatic number of
G
and is denoted by
σ
(
G
). In this study, we investigate sigma coloring in relation to a unary graph operation called middle graph. We will show that the sigma chromatic number of the middle graph of any path, cycle, sunlet graph, tadpole graph, ladder graph, or triangular snake graph is 2 except for some small cases. We also determine the sigma chromatic number of the middle graph of stars.
Abstract
We examine that all graphs in this paper are limited, simple and connected. A graceful
k
-coloring of a graph is a proper vertex coloring
f
1
:
V
(
G
) → {1, 2,…,
k
} where
k
≥ 2 which ...induces a proper edge coloring
f
2
:
E
(
G
) → {1, 2,…,
k
− 1} characterized by
f
2
(
uυ
) = |
f
1
(
u
) —
f
2
(
υ
)|. Nethermost k for which a graph
G
has a graceful
k
-coloring is named a graceful chromatic number of a graph
G
, denoted by
χ
g
(
G
). In our research, we will obtain the exact value of the graceful chromatic number of some graphs.
In this paper, we present a random iterative graph based hyper-heuristic to produce a collection of heuristic sequences to construct solutions of different quality. These heuristic sequences can be ...seen as dynamic hybridisations of different graph colouring heuristics that construct solutions step by step. Based on these sequences, we statistically analyse the way in which graph colouring heuristics are automatically hybridised. This, to our knowledge, represents a new direction in hyper-heuristic research. It is observed that spending the search effort on hybridising Largest Weighted Degree with Saturation Degree at the early stage of solution construction tends to generate high quality solutions. Based on these observations, an iterative hybrid approach is developed to adaptively hybridise these two graph colouring heuristics at different stages of solution construction. The overall aim here is to automate the heuristic design process, which draws upon an emerging research theme on developing computer methods to design and adapt heuristics automatically. Experimental results on benchmark exam timetabling and graph colouring problems demonstrate the effectiveness and generality of this adaptive hybrid approach compared with previous methods on automatically generating and adapting heuristics. Indeed, we also show that the approach is competitive with the state of the art human produced methods.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
Extending a recent breakthrough of Shitov, we prove that the chromatic number of the tensor product of two graphs can be a constant factor smaller than the minimum chromatic number of the two graphs. ...More precisely, we prove that there exists an absolute constant δ>0 such that for all c sufficiently large, there exist graphs G and H with chromatic number at least (1+δ)c for which χ(G×H)≤c.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ
There has been recently keen interest in finding polynomial-time algorithms for the VERTEX COLORING problem for graphs G that are F-free for a given set F of graphs. If L is a set of four-vertex ...graphs, then the complexity of VERTEX COLORING for L-free graphs is known with three exceptions: L1 = {claw, 4K1}, L2 = {claw, 4K1, co-diamond}, and L3 = {4K1, C4}. In this paper, we study a problem arising from the class L3. A hole is an induced cycle with at least four vertices. A hole-twin is the graph obtained from a hole by adding a vertex that forms true twins with some vertex of the hole. A 5-wheel is the graph obtained from a C5 by adding a vertex that is adjacent to all vertices of the C5. We prove that a (4K1, hole-twin, 5-wheel)-free graph is perfect or has bounded clique width. As consequence we obtain a polynomial time algorithm for VERTEX COLORING for (4K1, hole-twin, 5-wheel)-free graphs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ
Abstract
Let G be a connected and simple graph. Proper vertex colouring c : V(G) — {1, 2, 3,…, k} where k → 2 that induces a proper edge colouring c’ :
E(G) —
{1, 2, 3,…, k — 1} define by ...c’(uv)=|c(u) — c(v)|, where uv in E(G) is called graceful k— colouring. Graceful colouring is a vertex colouring c of graph G if c is a graceful k-coloring for some k ∈ N. Graceful chromatic number of a graph G, denoted by
χ
β
(G) is the minimum k for which G has a graceful k—colouring. In our paper, we investigate the establish exact value of graceful chromatic number of comb product of ladder graph.
We consider that all graph in this paper are finite, simple and connected graph. A graceful k−coloring of a graph is a proper vertex coloring f : V(G) → {1, 2, ..., k}, where k ≥ 2 which induces a ...proper edge coloring f' : E(G) → {1, 2, ..., k − 1} defined by f' (uv) = |f(u) − f(v)|. A vertex coloring f of graph is a graceful coloring if f is a graceful k−coloring for k ≥ 2. The minimum k for which a graph G has a graceful k−coloring is called a graceful chromatic number of a graph G, denoted by χg(G). In our paper, we will investigate the establish exact value of graceful chromatic number of unicyclic graph namely (m, n)−tadpole graph, n−pan graph and sun graphs
A married of vertex coloring partition and dimension of graph, became a definition of locating chromatic number of graph. That draught only can apply for connected graph. Because that, Welyyanti et ...al. expand concept of the locating chromatic number for disconnected graph. For this paper, the locating-chromatic number of disconnected graph contains one path and wheel graph as its components, is determined.
PDF
