Jul 2026· Anais do XI Encontro de Teoria da Computação (ETC 2026)· pp. 175-198· 0 citations· 14 references
Abstract
An r-dynamic coloring of a graph G is a proper vertex coloring in which each vertex sees at least min{r, d(v)} distinct colors in its neighborhood. The minimum number of colors in such a coloring is the r-dynamic chromatic number χdr(G). We determine exact values and upper bounds of χdr for several graph classes, including triangular grids, planar 3-trees for r ≤ 4, and planar Eulerian triangulations for r ≤ 3 (with a partial result for r = 4), confirming the conjecture of [Song et al. 2014] for these subclasses. We also establish exact values for the 2-dynamic chromatic number of a subclass of circulant graphs, confirming a conjecture of [Montgomery 2001] for this regular family.
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 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 χs...
We introduce and begin the study of sequence b-colorings, a natural generalization of the classical notion of b-colorings introduced by Irving and Manlove in 1999. In a sequence b-coloring, each color class is required to contain a prescribed minimum number of color-dominating vertices (CDVs). We establish several fund...
A graph has an
‐coloring
if there exists an assignment from the vertices to subsets of with size such that adjacent vertices are assigned disjoint subsets. Odd girth at least is a necessary condition for a graph to have a ‐coloring. Chen and Raspaud conjectured a tight upper bound on the maximum average degree of...
Ilkyoo Choi· Journal of Graph Theory· 1 citation· ⚡1
For a graph and a graph family , let denote the maximum number of copies of in an ‐free ‐vertex graph. Let . Bai, Tompkins, and Well conjectured that is attained if and each block of the graph is a . In this paper, we determine the exact value of and the extremal graphs for all . The novelty of our proof is to give a...
Xiaojun Zhao, Yuejian Peng· Journal of Graph Theory· 2 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
