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
In 1976, Loupekine introduced (via Isaacs) a very general way of constructing new snarks from old snarks by cyclically connecting multipoles constructed by pulling out a path of length 2 from smaller ...snarks. In this paper, we use Zm lifts of voltage graphs formed by a similar construction to produce a variety of snarks which can be drawn with m-fold rotational symmetry for m≥3. In particular, we discuss three infinite families of snarks which can be drawn with Zm rotational symmetry whose smallest element is constructed from 3 snarks with 3-fold rotational symmetry on 28 vertices; one family has the property that the oddness of the family increases with m. We also develop a new infinite family of snarks, of order 12m for each odd m≥3, which can be drawn with m-fold rotational symmetry and which are constructed beginning with a 3-edge-colorable graph, instead of a snark.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
33.
On twin edge mean colorings of graphs Tolentino, J D; Tolentino, M A C; Bernales, E B
Journal of physics. Conference series,
01/2022, Volume:
2157, Issue:
1
Journal Article
Peer reviewed
Open access
Abstract
Let
k
≥ 2 be an integer and
G
be a connected graph of order at least 3. In this paper, we introduce a new neighbor-distinguishing coloring called twin edge mean coloring. A proper edge ...coloring of
G
that uses colors from ℕ
k
= {0,1,…,
k
− 1} is called a twin
k
-edge mean coloring of
G
if it induces a proper vertex coloring of
G
such that the color of each vertex
υ
of
G
is the average of the colors of the edges incident with
υ
, and is an integer. The minimum
k
for which
G
has a twin
k
-edge mean coloring is called the twin chromatic mean index of
G
and is denoted by
χ
t
m
′
(
G
)
. First, we establish lower and upper bounds for
χ
t
m
′
(
G
)
under general or more specific assumptions. Then we determine the twin chromatic mean indices of paths, cycles, and stars.
•We obtained a classification of the finiteness of certain P5-free k-critical graphs.•We obtained a complete characterization of 5-critical (P5,K4)-free graphs.•The dual of Dilworth's Theorem was ...used in the study of k-critical graphs for the first time.
Given two graphs H1 and H2, a graph G is (H1,H2)-free if it contains no induced subgraph isomorphic to H1 or H2. Let Pt be the path on t vertices. A graph G is k-vertex-critical if G has chromatic number k but every proper induced subgraph of G has chromatic number less than k. The study of k-vertex-critical graphs for graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there is a polynomial-time algorithm to decide if a graph in the class is (k−1)-colorable.
In this paper, we initiate a systematic study of the finiteness of k-vertex-critical graphs in subclasses of P5-free graphs. Our main result is a complete classification of the finiteness of k-vertex-critical graphs in the class of (P5,H)-free graphs for all graphs H on 4 vertices. To obtain the complete dichotomy, we prove the finiteness for four new graphs H using various techniques – such as Ramsey-type arguments and the dual of Dilworth's Theorem – that may be of independent interest.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
In a cellular system with distributed MU-MIMO, an application of cluster-wise distributed MU-MIMO reduces the computational complexity. However, both the intracell interference and the intercell ...interference are produced. Considering the scalability of the system, in this letter, we propose a fully decentralized interference coordination (IC) which jointly applies the graph coloring algorithm (GCA) and the deep reinforcement learning (DRL). Based on online training with consideration of the time-varying wireless environment, our proposed joint IC can adapt quickly to the changing environment. The simulation reveals that our proposed joint IC can significantly improve the capacity compared to the no IC case.
The \\mathbb {Z}_2\-index \\mathrm{ind}(X)\ of a \\mathbb {Z}_2\-CW-complex X is the smallest number n such that there is a \\mathbb {Z}_2\-map from X to \S^n\. Here we consider \S^n\ as a \\mathbb ...{Z}_2\-space by the antipodal map. Hedetniemi’s conjecture is a long standing conjecture in graph theory concerning the graph coloring problem of tensor products of finite graphs. We show that if Hedetniemi’s conjecture is true, then \\mathrm{ind}(X \times Y) = \min \{ \mathrm{ind}(X) , \mathrm{ind}(Y)\}\ for every pair X and Y of finite \\mathbb {Z}_2\-complexes.
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
Graph coloring-in a generic sense-is used to identify subsets of independent tasks in parallel scientific computing applications. Traditional coloring heuristics aim to reduce the number of colors ...used as that number also corresponds to the number of parallel steps in the application. However, if the color classes produced have a skew in their sizes, utilization of hardware resources becomes inefficient, especially for the smaller color classes. Equitable coloring is a theoretical formulation of coloring that guarantees a perfect balance among color classes, and its practical relaxation is referred to here as balanced coloring. In this paper, we consider balanced coloring models in the context of parallel computing. The goal is to achieve a balanced coloring of an input graph without increasing the number of colors that an algorithm oblivious to balance would have used. We propose and study multiple heuristics that aim to achieve such a balanced coloring for two variants of coloring problem, distance-1 coloring (the standard coloring problem) and partial distance-2 coloring (defined on a bipartite graph). We present parallelization approaches for multi-core and manycore architectures and cross-evaluate their effectiveness with respect to the quality of balance achieved and performance. Furthermore, we study the impact of the proposed balanced coloring heuristics on a concrete application-viz. parallel community detection, which is an example of an irregular application. In addition, we propose several extensions to our basic balancing schemes and evaluate their balancing efficacy and performance characteristics. The thorough treatment of balanced coloring presented in this paper from algorithms to application is expected to serve as a valuable resource to parallel application developers who seek to improve parallel performance of their applications using coloring.
Abstract
This article discusses irregular coloring. Irregular coloring was first introduced by Mary Radcliffe and Ping Zhang in 2007. The coloring c is called irregular coloring if distinct vertices ...of G have distinct codes. The color code of a vertex v of G with respect to c is
code(v)
= (a
0
,
a
1
, a
2
,…, a
k
) =
a
0
a
1
a
2
, …a
k
,
where
a
0
= c(v) and
a
i
,
(1 < i <
k)
is the number of vertices that are adjacent to v and colored i. The minimum k-color used in irregular coloring is called the irregular chromatic number and is denoted by \
ir
. Irregular coloring is included in proper coloring, where each vertex that is the neighbors must not be the same color. The graphs used in this article are a family of bipartite graphs and a family of tree graphs, including complete bipartite graphs, crown graphs, star graphs, centipede graphs, and double star graphs.
In 1980, Akiyama, Exoo and Harary posited the Linear Arboricity Conjecture which states that any graph
G
of maximum degree
Δ
can be decomposed into at most
linear forests. (A forest is linear if all ...of its components are paths.) In 1988, Alon proved the conjecture holds asymptotically. The current best bound is due to Ferber, Fox and Jain from 2020 who showed that
Δ
2
+
O
(
Δ
0.661
)
suffices for large enough
Δ
. Here, we show that
G
admits a decomposition into at most
Δ
2
+
3
Δ
log
4
Δ
linear forests provided
Δ
is large enough. Moreover, our result also holds in the more general list setting, where edges have (possibly different) sets of permissible linear forests. Thus our bound also holds for the List Linear Arboricity Conjecture which was only recently shown to hold asymptotically by Kim and the second author. Indeed, our proof method ties together the Linear Arboricity Conjecture and the well-known List Colouring Conjecture; consequently, our error term for the Linear Arboricity Conjecture matches the best known error-term for the List Colouring Conjecture due to Molloy and Reed from 2000. This follows as we make two copies of every colour and then seek a proper edge colouring where we avoid bicoloured cycles between a colour and its copy; we achieve this via a clever modification of the nibble method.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
We present OIM (Oscillator Ising Machines), a new way to make Ising machines using networks of coupled self-sustaining nonlinear oscillators. OIM is theoretically rooted in a novel result that ...establishes that the phase dynamics of coupled oscillator systems, under the influence of subharmonic injection locking, are governed by a Lyapunov function that is closely related to the Ising Hamiltonian of the coupling graph. As a result, the dynamics of such oscillator networks evolve naturally to local minima of the Lyapunov function. Two simple additional steps (i.e., turning subharmonic locking on and off smoothly, and adding noise) enable the network to find excellent solutions of Ising problems. We demonstrate our method on Ising versions of the MAX-CUT and graph colouring problems, showing that it improves on previously published results on several problems in the G benchmark set. Using synthetic problems with known global minima, we also present initial scaling results. Our scheme, which is amenable to realisation using many kinds of oscillators from different physical domains, is particularly well suited for CMOS IC implementation, offering significant practical advantages over previous techniques for making Ising machines. We report working hardware prototypes using CMOS electronic oscillators.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
PDF
![[\mathbb {Z}_2\] -Indices a...](http://api.summon.serialssolutions.com/2.0.0/image/issn/XR4PS5YY4K/0179-5376/small "[\mathbb {Z}_2\] -Indices and Hedetniemi’s Conjecture")
