A proper edge coloring of a graph G is strict neighbor-distinguishing if for any two adjacent vertices u and v, the set of colors used on the edges incident to u and the set of colors used on the edges incident to v are not included with each other. The strict neighbor-distinguishing index of G is the minimum number χsnd′(G) of colors in a strict neighbor-distinguishing edge coloring of G. It was conjectured that every simple graph G without leaves has χsnd′(G) ⩽ 2Δ except a special graph HΔ. We show that if G is a planar graph without 4-cycles, then χsnd′(G) ⩽ Δ + 300.
An acyclic edge coloring of a graph G is a proper edge coloring such that G contains no bichromatic cycles. The acyclic chromatic index χa′(G) is the minimum number of colors required for an acyclic edge coloring. Fiamčik and Alon et al. independently conjectured that χa′(G)≤Δ+2 for every simple graph G with maximum de...
Given a graph G , an r -hued coloring of G is a proper vertex coloring such that for every vertex v , the number of colors appearing in its neighborhood is at least min { d G ( v ) , r } , where d G ( v ) denotes the degree of v in G . The r -hued chromatic number χ r ( G ) is the smallest number of colors needed for a...
A proper conflict-free coloring of a graph is a proper vertex coloring in which every non-isolated vertex has a color appearing exactly once in its neighborhood. A graph $G$ is proper conflict-free $(\mathrm{degree}+2)$-choosable if every list assignment $L$ with $|L(v)|\ge d_G(v)+2$ for each $v\in V(G)$ admits such a...
We extend the conjecture of Erd\H{o}s and Gy\'arf\'as on monochromatic path covers to the setting of monochromatic cycle covers. We prove that, for all $n$, every 2-edge-coloring of the complete graph on $n$ vertices contains a collection of at most $\lceil\sqrt{n}\rceil$ monochromatic cycles, all of the same color, th...
Suppose that T is a normal spanning tree (depth-first search tree) of a graph G. If e=xy and e′=uv are edges of G, satisfying x≺Tu≺Ty≺Tv, then they are called secant edges of G with respect to T. Suppose that G has no secant edges with respect to T. If T is a path, Ghazal and Al-Mniny proved that the chromatic number i...
The dominated coloring of a graph $G$ is a proper vertex coloring such that each color class is dominated by a vertex. The minimum number of colors required for a dominated coloring of a graph $G$ is called the dominated chromatic number of the graph $G$ and is denoted by $\chi_{dom}(G)$. A graph $G$ is said to be chro...
R. Sneha, J. Geetha, K. Somasundaram· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
