Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Sequential Coloring of Graphs and its Defining Sets
214
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper, based on the contributions of Tucker (1983) and Seb{H{o}} (1992), we generalize the concept of a sequential coloring of a graph to a framework in which the algorithm may use a coloring rule-base obtained from suitable forcing structures. In this regard, we introduce the {it weak} and {it strong sequential defining numbers} for such colorings and as the main results, after proving some basic properties, we show that these two parameters are intrinsically different and their spectra are nontrivial. Also, we consider the natural problems related to the complexity of computing such parameters and we show that in a variety of cases these problems are ${bf NP}$-complete. We conjecture that this result does not depend on the rule-base for all nontrivial cases.
rate research
Read More
For nonnegative integers $k, d_1, ldots, d_k$, a graph is $(d_1, ldots, d_k)$-colorable if its vertex set can be partitioned into $k$ parts so that the $i$th part induces a graph with maximum degree at most $d_i$ for all $iin{1, ldots, k}$. A class $mathcal C$ of graphs is {it balanced $k$-partitionable} and {it unbalanced $k$-partitionable} if there exists a nonnegative integer $D$ such that all graphs in $mathcal C$ are $(D, ldots, D)$-colorable and $(0, ldots, 0, D)$-colorable, respectively, where the tuple has length $k$. A set $X$ of cycles is a {it cycle obstruction set} of a class $mathcal C$ of planar graphs if every planar graph containing none of the cycles in $X$ as a subgraph belongs to $mathcal C$. This paper characterizes all cycle obstruction sets of planar graphs to be balanced $k$-partitionable and unbalanced $k$-partitionable for all $k$; namely, we identify all inclusion-wise minimal cycle obstruction sets for all $k$.
We confirm the equitable $Delta$-coloring conjecture for interval graphs and establish the monotonicity of equitable colorability for them. We further obtain results on equitable colorability about square (or Cartesian) and cross (or direct) products of graphs.
The star chromatic index of a multigraph $G$, denoted $chi_{st}(G)$, is the minimum number of colors needed to properly color the edges of $G$ such that no path or cycle of length four is bicolored. We survey the results of determining the star chromatic index, present the interesting proofs and techniques, and collect many open problems and conjectures.
We exhibit an explicit list of nine graphs such that a graph drawn in the Klein bottle is 5-colorable if and only if it has no subgraph isomorphic to a member of the list.
For a given graph $G$, the least integer $kgeq 2$ such that for every Abelian group $mathcal{G}$ of order $k$ there exists a proper edge labeling $f:E(G)rightarrow mathcal{G}$ so that $sum_{xin N(u)}f(xu) eq sum_{xin N(v)}f(xv)$ for each edge $uvin E(G)$ is called the textit{group twin chromatic index} of $G$ and denoted by $chi_g(G)$. This graph invariant is related to a few well-known problems in the field of neighbor distinguishing graph colorings. We conjecture that $chi_g(G)leq Delta(G)+3$ for all graphs without isolated edges, where $Delta(G)$ is the maximum degree of $G$, and provide an infinite family of connected graph (trees) for which the equality holds. We prove that this conjecture is valid for all trees, and then apply this result as the base case for proving a general upper bound for all graphs $G$ without isolated edges: $chi_g(G)leq 2(Delta(G)+{rm col}(G))-5$, where ${rm col}(G)$ denotes the coloring number of $G$. This improves the best known upper bound known previously only for the case of cyclic groups $mathbb{Z}_k$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
