Results 1 to 10 of about 4,748 (121)
Strong Chromatic Index of Outerplanar Graphs
Axioms, 2022 The strong chromatic index χs′(G) of a graph G is the minimum number of colors needed in a proper edge-coloring so that every color class induces a matching in G. It was proved In 2013, that every outerplanar graph G with Δ≥3 has χs′(G)≤3Δ−3.
Ying Wang +3 more
doaj +4 more sources
Strong chromatic index of products of graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 The strong chromatic index of a graph is the minimum number of colours needed to colour the edges in such a way that each colour class is an induced matching.
Olivier Togni
doaj +5 more sources
A stronger bound for the strong chromatic index [PDF]
Electronic Notes in Discrete Mathematics, 2015 We prove χ′s(G) ≤ 1.93 Δ(G)2 for graphs of sufficiently large maximum degree where χ′s(G) is the strong chromatic index of G. This improves an old bound of Molloy and Reed. As a by-product, we present a Talagrand-type inequality where we are allowed to exclude unlikely bad outcomes that would otherwise render the inequality unusable.
Henning Brühn
exaly +3 more sources
The strong chromatic index of 1-planar graphs [PDF]
Discrete Mathematics & Theoretical Computer ScienceThe chromatic index $\chi'(G)$ of a graph $G$ is the smallest $k$ for which $G$ admits an edge $k$-coloring such that any two adjacent edges have distinct colors.
Yiqiao Wang +3 more
doaj +3 more sources
The strong chromatic index of sparse graphs [PDF]
Information Processing Letters, 2015 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Michał Debski +2 more
exaly +4 more sources
The Strong Chromatic Index of Random Graphs [PDF]
SIAM Journal on Discrete Mathematics, 2005 The strong chromatic index of a graph $G$, denoted by $\chi_s(G)$, is the minimum number of colors needed to color its edges so that each color class is an induced matching. In this paper we analyze the asymptotic behavior of this parameter in a random graph $G(n,p)$, for two regions of the edge probability $p=p(n)$.
Alan Frieze, Benny Sudakov
exaly +2 more sources
The strong chromatic index of a class of graphs
Discrete Mathematics, 2008 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Wensong Lin
exaly +2 more sources
Strong list-chromatic index of subcubic graphs [PDF]
Discrete Mathematics, 2018 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 $χ'_{s}(G)$, is the minimum $k$ for which $G$ has a strong $k$-edge-coloring.
Gexin Yu, Donglei Yang
exaly +4 more sources
Upper Bounds for the Strong Chromatic Index of Halin Graphs
Discussiones Mathematicae Graph Theory, 2018 The strong chromatic index of a graph G, denoted by χ′s(G), is the minimum number of vertex induced matchings needed to partition the edge set of G. Let T be a tree without vertices of degree 2 and have at least one vertex of degree greater than 2.
Hu Ziyu, Lih Ko-Wei, Liu Daphne Der-Fen
doaj +3 more sources
Strong Chromatic Index Of Planar Graphs With Large Girth
Discussiones Mathematicae Graph Theory, 2014 Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 1 Δ+46 is strong (2Δ−1)-edgecolorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of ...
Jennhwa Chang Gerard +3 more
doaj +4 more sources