Search

A matching M $M$ in a graph G $G$ is semistrong if every edge of M $M$ has an endvertex of degree one in the subgraph induced by the vertices of M $M$. A semistrong edge‐coloring of a graph G $G$ is a proper edge‐coloring in which every color class induces a semistrong matching. In this paper, we continue investigation of properties of semistrong edge‐colorings initiated by Gyárfás and Hubenko. We establish tight upper bounds for general graphs and for graphs with maximum degree 3. We also present bounds about semistrong edge‐coloring which follow from results regarding other, at first sight nonrelated, problems. We conclude the paper with several open problems. [ABSTRACT FROM AUTHOR]

The weight of an edge is the degree‐sum of its end‐vertices. An edge uv $uv$ is an (i,j) $(i,j)$‐edge if deg(u)≤i $\,\text{deg}\,(u)\le i$ and deg(v)≤j $\,\text{deg}\,(v)\le j$. In 1955, Kotzig proved that every 3‐connected plane graph contains an edge of weight at most 13. Later, Borodin proved the existence of such an edge in plane graphs with minimum degree at least three. If we consider a graph embedded on a surface with nonpositive Euler characteristic, minimum degree at least three and sufficiently large number of vertices, then the existence of an edge of weight at most 15 can be proved. In this paper we consider graphs with minimum degree two, minimum face degree at least three, embedded on a surface with nonpositive Euler characteristic. We prove that every connected graph with sufficiently large number of vertices, minimum degree two and minimum face degree at least ρ $\rho $, embedded on a surface with nonpositive Euler characteristic, contains an edge of type (2,∞) $(2,\infty)$, (3,12) $(3,12)$, (4,8) $(4,8)$ or (6,6) $(6,6)$ if ρ=3 $\rho =3$, (2,∞) $(2,\infty)$, (3,6) $(3,6)$ or (4,4) $(4,4)$ if ρ=4 $\rho =4$, (2,6) $(2,6)$ or (3,3) $(3,3)$ if ρ∈{5,6} $\rho \in \{5,6\}$, (2,4) $(2,4)$ if ρ∈{7,8} $\rho \in \{7,8\}$, (2,3) $(2,3)$ if ρ∈{9,10,11,12} $\rho \in \{9,10,11,12\}$, and (2,2) $(2,2)$ if ρ≥13 $\rho \ge 13$. We will also discuss the quality of our results. [ABSTRACT FROM AUTHOR]

A proper edge coloring of a graph is strong if it creates no bichromatic path of length three. It is well known that for a strong edge coloring of a k $k$‐regular graph at least 2k−1 $2k-1$ colors are needed. We show that a k $k$‐regular graph admits a strong edge coloring with 2k−1 $2k-1$ colors if and only if it covers the Kneser graph K(2k−1,k−1) $K(2k-1,k-1)$. In particular, a cubic graph is strongly 5‐edge‐colorable whenever it covers the Petersen graph. One of the implications of this result is that a conjecture about strong edge colorings of subcubic graphs proposed by Faudree et al. is false. [ABSTRACT FROM AUTHOR]

A star edge‐coloring of a graph is a proper edge‐coloring without bichromatic paths and cycles of length four. In this paper, we consider the list version of this coloring and prove that the list star chromatic index of every subcubic graph is at most 7, answering the question of Dvořák et al (J Graph Theory, 72 (2013), 313‐326). [ABSTRACT FROM AUTHOR]

A graph is locally irregular if the neighbors of every vertex v have degrees distinct from the degree of v. A locally irregular edge-coloring of a graph G is an (improper) edge-coloring such that the graph induced on the edges of any color class is locally irregular. It is conjectured that three colors suffice for a locally irregular edge-coloring. In the paper, we develop a method using which we prove four colors are enough for a locally irregular edge-coloring of any subcubic graph admiting such a coloring. We believe that our method can be further extended to prove the tight bound of three colors for such graphs. Furthermore, using a combination of existing results, we present an improvement of the bounds for bipartite graphs and general graphs, setting the best upper bounds to 7 and 220, respectively. [ABSTRACT FROM AUTHOR]

An incidence in a graph G is a pair ( v, e) where v is a vertex of G and e is an edge of G incident to v. Two incidences ( v, e) and ( u, f) are adjacent if at least one of the following holds: $$(a) v = u, (b) e = f$$ , or $$(c) vu \in \{e,f\}$$ . An incidence coloring of G is a coloring of its incidences assigning distinct colors to adjacent incidences. In this note we prove that every subquartic graph admits an incidence coloring with at most seven colors. [ABSTRACT FROM AUTHOR]

A star edge coloring of a graph is a proper edge coloring without bichromatic paths and cycles of length four. In this article, we establish tight upper bounds for trees and subcubic outerplanar graphs, and derive an upper bound for outerplanar graphs. [ABSTRACT FROM AUTHOR]

For a given graph $$H$$ and $$n \ge 1,$$ let $$f(n, H)$$ denote the maximum number $$m$$ for which it is possible to colour the edges of the complete graph $$K_n$$ with $$m$$ colours in such a way that each subgraph $$H$$ in $$K_n$$ has at least two edges of the same colour. Equivalently, any edge-colouring of $$K_n$$ with at least $$rb(n,H)=f(n,H) + 1$$ colours contains a rainbow copy of $$H.$$ The numbers $$f(n,H)$$ and $$rb(K_n,H)$$ are called anti-ramsey numbers and rainbow numbers, respectively. In this paper we will classify the rainbow number for a given graph $$H$$ with respect to its cyclomatic number. Let $$H$$ be a graph of order $$p \ge 4$$ and cyclomatic number $$v(H) \ge 2.$$ Then $$rb(K_n, H)$$ cannot be bounded from above by a function which is linear in $$n.$$ If $$H$$ has cyclomatic number $$v(H) = 1,$$ then $$rb(K_n, H)$$ is linear in $$n.$$ Moreover, we will compute all rainbow numbers for the bull $$B,$$ which is the unique graph with $$5$$ vertices and degree sequence $$(1,1,2,3,3)$$ . [ABSTRACT FROM AUTHOR]

In the article, the existence of rainbow cycles in edge colored plane triangulations is studied. It is shown that the minimum number [ABSTRACT FROM AUTHOR]

The coloring of disk graphs is motivated by the frequency assignment problem. In 1998, Malesińska et al. introduced double disk graphs as their generalization. They showed that the chromatic number of a double disk graph $$G$$ is at most $$33\,\omega (G) - 35$$ , where $$\omega (G)$$ denotes the size of a maximum clique in $$G$$ . Du et al. improved the upper bound to $$31\,\omega (G) - 1$$ . In this paper we decrease the bound substantially; namely we show that the chromatic number of $$G$$ is at most $$15\,\omega (G) - 14$$ . [ABSTRACT FROM AUTHOR]