Results 11 to 20 of about 57,891 (276)
Strong chromatic index of sparse graphs [PDF]
, 2013 A coloring of the edges of a graph $G$ is strong if each color class is an induced matching of $G$. The strong chromatic index of $G$, denoted by $ _{s}^{\prime}(G)$, is the least number of colors in a strong edge coloring of $G$. In this note we prove that $ _{s}^{\prime}(G)\leq (4k-1) (G)-k(2k+1)+1$ for every $k$-degenerate graph $G$.
Dębski, Michał +2 more
openaire +3 more sources
The chromatic index of strongly regular graphs [PDF]
, 2020 We determine (partly by computer search) the chromatic index (edge-chromatic number) of many strongly regular graphs (SRGs), including the SRGs of degree $k \leq 18$ and their complements, the Latin square graphs and their complements, and the triangular
Cioaba, Sebastian M. +2 more
core +2 more sources
Acyclic Chromatic Index of 1-Planar Graphs
Mathematics, 2022 The acyclic chromatic index χa′(G) of a graph G is the smallest k for which G is a proper edge colorable using k colors. A 1-planar graph is a graph that can be drawn in plane such that every edge is crossed by at most one other edge.
Wanshun Yang +5 more
doaj +1 more source
Chromatic index, treewidth and maximum degree [PDF]
Electronic Notes in Discrete Mathematics, 2016 We conjecture that any graph $G$ with treewidth $k$ and maximum degree $\Delta(G)\geq k + \sqrt{k}$ satisfies $\chi'(G)=\Delta(G)$. In support of the conjecture we prove its fractional version. We also show that any graph $G$ with treewidth $k\geq 4$ and maximum degree $2k-1$ satisfies $\chi'(G)=\Delta(G)$, extending an old result of Vizing.
Bruhn, Henning +2 more
openaire +3 more sources
On the edge chromatic vertex stability number of graphs
AKCE International Journal of Graphs and Combinatorics, 2023 For an arbitrary invariant [Formula: see text] of a graph G, the [Formula: see text]vertex stability number [Formula: see text] is the minimum number of vertices of G whose removal results in a graph [Formula: see text] with [Formula: see text] or with ...
Saeid Alikhani, Mohammad R. Piri
doaj +1 more source
Strong Chromatic Index of Chordless Graphs [PDF]
Journal of Graph Theory, 2014 AbstractA strong edge coloring of a graph is an assignment of colors to the edges of the graph such that for every color, the set of edges that are given that color form an induced matching in the graph. The strong chromatic index of a graph G, denoted by , is the minimum number of colors needed in any strong edge coloring of G.
Basavaraju, Manu, Francis, Mathew C.
openaire +3 more sources
SOME EXTREMAL RESULTS ON THE CHROMATIC STABILITY INDEX [PDF]
Bulletin of the Australian Mathematical Society, 2022 AbstractThe $\chi $ -stability index $\mathrm {es}_{\chi }(G)$ of a graph G is the minimum number of its edges whose removal results in a graph with chromatic number smaller than that of G. We consider three open problems from Akbari et al. [‘Nordhaus–Gaddum and other bounds for the chromatic edge-stability number’, European J.
SHENWEI HUANG +4 more
openaire +3 more sources
The Distance-t Chromatic Index of Graphs [PDF]
Combinatorics, Probability and Computing, 2013 We consider two graph colouring problems in which edges at distance at most t are given distinct colours, for some fixed positive integer t. We obtain two upper bounds for the distance-t chromatic index, the least number of colours necessary for such a colouring. One is a bound of (2-ε)Δt for graphs of maximum degree at most Δ, where ε is some absolute
Kaiser, Tomàš, Kang, Ross
openaire +3 more sources
Mixed Graph Colorings: A Historical Review
Mathematics, 2020 This paper presents a historical review and recent developments in mixed graph colorings in the light of scheduling problems with the makespan criterion. A mixed graph contains both a set of arcs and a set of edges. Two types of colorings of the vertices
Yuri N. Sotskov
doaj +1 more source
On the ρ-Edge Stability Number of Graphs
Discussiones Mathematicae Graph Theory, 2022 For an arbitrary invariant ρ(G) of a graph G the ρ-edge stability number esρ(G) is the minimum number of edges of G whose removal results in a graph H ⊆ G with ρ(H) ≠ ρ(G) or with E(H) = ∅.
Kemnitz Arnfried, Marangio Massimiliano
doaj +1 more source