Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEquitable partition of planar graphs
75
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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}$.
In this paper, we study the achromatic and the pseudoachromatic numbers of planar and outerplanar graphs as well as planar graphs of girth 4 and graphs embedded on a surface. We give asymptotically tight results and lower bounds for maximal embedded graphs.
In this article we associate a combinatorial differential graded algebra to a cubic planar graph G. This algebra is defined combinatorially by counting binary sequences, which we introduce, and several explicit computations are provided. In addition, in the appendix by K. Sackel the F(q)-rational points of its graded augmentation variety are shown to coincide with (q+1)-colorings of the dual graph.
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
