Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStrong chromatic index of chordless graphs
275
0
0.0
(
0
)
Added by
Mathew Francis
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A strong edge colouring of a graph is an assignment of colours to the edges of the graph such that for every colour, the set of edges that are given that colour form an induced matching in the graph. The strong chromatic index of a graph $G$, denoted by $chi_s(G)$, is the minimum number of colours needed in any strong edge colouring of $G$. A graph is said to be emph{chordless} if there is no cycle in the graph that has a chord. Faudree, Gyarfas, Schelp and Tuza~[The Strong Chromatic Index of Graphs, Ars Combin., 29B (1990), pp.~205--211] considered a particular subclass of chordless graphs, namely the class of graphs in which all the cycle lengths are multiples of four, and asked whether the strong chromatic index of these graphs can be bounded by a linear function of the maximum degree. Chang and Narayanan~[Strong Chromatic Index of 2-degenerate Graphs, J. Graph Theory, 73(2) (2013), pp.~119--126] answered this question in the affirmative by proving that if $G$ is a chordless graph with maximum degree $Delta$, then $chi_s(G) leq 8Delta -6$. We improve this result by showing that for every chordless graph $G$ with maximum degree $Delta$, $chi_s(G)leq 3Delta$. This bound is tight up to to an additive constant.
rate research
Read More
A strong $k$-edge-coloring of a graph G is an edge-coloring with $k$ colors in which every color class is an induced matching. The strong chromatic index of $G$, denoted by $chi_{s}(G)$, is the minimum $k$ for which $G$ has a strong $k$-edge-coloring. In 1985, ErdH{o}s and Nev{s}etv{r}il conjectured that $chi_{s}(G)leqfrac{5}{4}Delta(G)^2$, where $Delta(G)$ is the maximum degree of $G$. When $G$ is a graph with maximum degree at most 3, the conjecture was verified independently by Andersen and Hor{a}k, Qing, and Trotter. In this paper, we consider the list version of strong edge-coloring. In particular, we show that every subcubic graph has strong list-chromatic index at most 11 and every planar subcubic graph has strong list-chromatic index at most 10.
The strong chromatic index of a graph $G$, denoted $chi_s(G)$, is the least number of colors needed to edge-color $G$ so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted $chi_{s,ell}(G)$, is the least integer $k$ such that if arbitrary lists of size $k$ are assigned to each edge then $G$ can be edge-colored from those lists where edges at distance at most two receive distinct colors. We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if $G$ is a subcubic planar graph with $operatorname{girth}(G) geq 41$ then $chi_{s,ell}(G) leq 5$, answering a question of Borodin and Ivanova [Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory, 33(4), (2014) 759--770]. We further show that if $G$ is a subcubic planar graph and $operatorname{girth}(G) geq 30$, then $chi_s(G) leq 5$, improving a bound from the same paper. Finally, if $G$ is a planar graph with maximum degree at most four and $operatorname{girth}(G) geq 28$, then $chi_s(G) leq 7$, improving a more general bound of Wang and Zhao from [Odd graphs and its application on the strong edge coloring, arXiv:1412.8358] in this case.
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$ on $n$ vertices with $Delta(G)>n/3$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph. Glock, K{u}hn and Osthus in 2016 showed that the conjecture is true for dense quasirandom graphs with even order, and they conjectured that the same should hold for such graphs with odd order. In this paper, we show that the conjecture of Glock, K{u}hn and Osthus is affirmative.
Let $chi_k(G)$ denote the minimum number of colors needed to color the edges of a graph $G$ in a way that the subgraph spanned by the edges of each color has all degrees congruent to $1 pmod k$. Scott [{em Discrete Math. 175}, 1-3 (1997), 289--291] proved that $chi_k(G)leq5k^2log k$, and thus settled a question of Pyber [{em Sets, graphs and numbers} (1992), pp. 583--610], who had asked whether $chi_k(G)$ can be bounded solely as a function of $k$. We prove that $chi_k(G)=O(k)$, answering affirmatively a question of Scott.
An extension of the well-known Szeged index was introduced recently, named as weighted Szeged index ($textrm{sz}(G)$). This paper is devoted to characterizing the extremal trees and graphs of this new topological invariant. In particular, we proved that the star is a tree having the maximal $textrm{sz}(G)$. Finding a tree with the minimal $textrm{sz}(G)$ is not an easy task to be done. Here, we present the minimal trees up to 25 vertices obtained by computer and describe the regularities which retain in them. Our preliminary computer tests suggest that a tree with the minimal $textrm{sz}(G)$ is also the connected graph of the given order that attains the minimal weighted Szeged index. Additionally, it is proven that among the bipartite connected graphs the complete balanced bipartite graph $K_{leftlfloor n/2rightrfloorleftlceil n/2 rightrceil}$ attains the maximal $textrm{sz}(G)$,. We believe that the $K_{leftlfloor n/2rightrfloorleftlceil n/2 rightrceil}$ is a connected graph of given order that attains the maximum $textrm{sz}(G)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
