Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA survey on star edge-coloring of graphs
80
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Let $G$ be a simple graph with maximum degree $Delta(G)$. A subgraph $H$ of $G$ is overfull if $|E(H)|>Delta(G)lfloor |V(H)|/2 rfloor$. Chetwynd and Hilton in 1985 conjectured that a graph $G$ with $Delta(G)>|V(G)|/3$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph. The 1-factorization conjecture is a special case of this overfull conjecture, which states that for even $n$, every regular $n$-vertex graph with degree at least about $n/2$ has a 1-factorization and was confirmed for large graphs in 2014. Supporting the overfull conjecture as well as generalizing the 1-factorization conjecture in an asymptotic way, in this paper, we show that for any given $0<varepsilon <1$, there exists a positive integer $n_0$ such that the following statement holds: if $G$ is a graph on $2nge n_0$ vertices with minimum degree at least $(1+varepsilon)n$, then $G$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph.
A strong edge-coloring of a graph $G$ is an edge-coloring such that any two edges on a path of length three receive distinct colors. We denote the strong chromatic index by $chi_{s}(G)$ which is the minimum number of colors that allow a strong edge-coloring of $G$. ErdH{o}s and Nev{s}etv{r}il conjectured in 1985 that the upper bound of $chi_{s}(G)$ is $frac{5}{4}Delta^{2}$ when $Delta$ is even and $frac{1}{4}(5Delta^{2}-2Delta +1)$ when $Delta$ is odd, where $Delta$ is the maximum degree of $G$. The conjecture is proved right when $Deltaleq3$. The best known upper bound for $Delta=4$ is 22 due to Cranston previously. In this paper we extend the result of Cranston to list strong edge-coloring, that is to say, we prove that when $Delta=4$ the upper bound of list strong chromatic index is 22.
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$.
Motivated by the Erdos-Faber Lovasz conjecture (EFL) for hypergraphs, we explore relationships between several conjectures on the edge coloring of linear hypergraphs. In particular, we are able to increase the class of hypergraphs for which EFL is true.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
