Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEquitable coloring of interval graphs and products of graphs
234
0
0.0
(
0
)
Authors
Bor-Liang Chen
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
If the vertices of a graph $G$ are colored with $k$ colors such that no adjacent vertices receive the same color and the sizes of any two color classes differ by at most one, then $G$ is said to be equitably $k$-colorable. Let $|G|$ denote the number of vertices of $G$ and $Delta=Delta(G)$ the maximum degree of a vertex in $G$. We prove that a graph $G$ of order at least 6 is equitably $Delta$-colorable if $G$ satisfies $(|G|+1)/3 leq Delta < |G|/2$ and none of its components is a $K_{Delta +1}$.
An equitable $k$-partition of a graph $G$ is a collection of induced subgraphs $(G[V_1],G[V_2],ldots,G[V_k])$ of $G$ such that $(V_1,V_2,ldots,V_k)$ is a partition of $V(G)$ and $-1le |V_i|-|V_j|le 1$ for all $1le i<jle k$. We prove that every planar graph admits an equitable $2$-partition into $3$-degenerate graphs, an equitable $3$-partition into $2$-degenerate graphs, and an equitable $3$-partition into two forests and one graph.
Let $G = (V, E)$ be a finite simple undirected graph without $K_2$ components. A bijection $f : E rightarrow {1, 2,cdots, |E|}$ is called a {bf local antimagic labeling} if for any two adjacent vertices $u$ and $v$, they have different vertex sums, i.e. $w(u) eq w(v)$, where the vertex sum $w(u) = sum_{e in E(u)} f(e)$, and $E(u)$ is the set of edges incident to $u$. Thus any local antimagic labeling induces a proper vertex coloring of $G$ where the vertex $v$ is assigned the color(vertex sum) $w(v)$. The {bf local antimagic chromatic number} $chi_{la}(G)$ is the minimum number of colors taken over all colorings induced by local antimagic labelings of $G$. In this article among others we determine completely the local antimagic chromatic number $chi_{la}(Gcirc overline{K_m})$ for the corona product of a graph $G$ with the null graph $overline{K_m}$ on $mgeq 1$ vertices, when $G$ is a path $P_n$, a cycle $C_n$, and a complete graph $K_n$.
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$.
The textit{$k$-weak-dynamic number} of a graph $G$ is the smallest number of colors we need to color the vertices of $G$ in such a way that each vertex $v$ of degree $d(v)$ sees at least $rm{min}{k,d(v)}$ colors on its neighborhood. We use reducible configurations and list coloring of graphs to prove that all planar graphs have 3-weak-dynamic number at most 6.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
