Results 31 to 40 of about 2,302 (247)
Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number [PDF]
The Electronic Journal of Combinatorics, 2013 Nordhaus and Gaddum proved, for any graph $G$, that $\chi(G) + \chi(\overline{G}) \leq n + 1$, where $\chi$ is the chromatic number and $n=|V(G)|$. Finck characterized the class of graphs, which we call NG-graphs, that satisfy equality in this bound. In this paper, we provide a new characterization of NG-graphs, based on vertex degrees, which yields a ...
Karen L. Collins, Ann N. Trenk
openaire +3 more sources
Adjacent vertex distinguishing acyclic edge coloring of the Cartesian product of graphs [PDF]
Transactions on Combinatorics, 2017 Let $G$ be a graph and $chi^{prime}_{aa}(G)$ denotes the minimum number of colors required for an acyclic edge coloring of $G$ in which no two adjacent vertices are incident to edges colored with the same set of colors. We prove a general bound for $
Fatemeh Sadat Mousavi, Massomeh Noori
doaj +1 more source
The harmonious chromatic number of almost all trees [PDF]
, 1995 A harmonious colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colours in such a colouring.For any positive integer ...
Edwards, Keith
core +1 more source
On multiset colorings of generalized corona graphs [PDF]
Mathematica Bohemica, 2016 A vertex $k$-coloring of a graph $G$ is a \emph{multiset $k$-coloring} if $M(u)\neq M(v)$ for every edge $uv\in E(G)$, where $M(u)$ and $M(v)$ denote the multisets of colors of the neighbors of $u$ and $v$, respectively. The minimum $k$ for which $G$ has
Yun Feng, Wensong Lin
doaj +1 more source
Group twin coloring of graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2018 For a given graph $G$, the least integer $k\geq 2$ such that for every Abelian group $\mathcal{G}$ of order $k$ there exists a proper edge labeling $f:E(G)\rightarrow \mathcal{G}$ so that $\sum_{x\in N(u)}f(xu)\neq \sum_{x\in N(v)}f(xv)$ for each edge ...
Sylwia Cichacz, Jakub Przybyło
doaj +1 more source
On distinguishing and distinguishing chromatic numbers of hypercubes [PDF]
, 2008 The distinguishing number D(G) of a graph G is the least integer d such that G has a labeling with d colors that is not preserved by any nontrivial automorphism.
Klöckl, Werner
core +1 more source
A Tight Bound on the Set Chromatic Number
Discussiones Mathematicae Graph Theory, 2013 We provide a tight bound on the set chromatic number of a graph in terms of its chromatic number. Namely, for all graphs G, we show that χs(G) > ⌈log2 χ(G)⌉ + 1, where χs(G) and χ(G) are the set chromatic number and the chromatic number of G ...
Sereni Jean-Sébastien +1 more
doaj +1 more source
On the total and AVD-total coloring of graphs
AKCE International Journal of Graphs and Combinatorics, 2020 A total coloring of a graph G is an assignment of colors to the vertices and the edges such that (i) no two adjacent vertices receive same color, (ii) no two adjacent edges receive same color, and (iii) if an edge e is incident on a vertex v, then v and ...
B. S. Panda, Shaily Verma, Yash Keerti
doaj +1 more source
Neighbor Sum Distinguishing Total Choosability of IC-Planar Graphs
Discussiones Mathematicae Graph Theory, 2020 Two distinct crossings are independent if the end-vertices of the crossed pair of edges are mutually different. If a graph G has a drawing in the plane such that every two crossings are independent, then we call G a plane graph with independent crossings
Song Wen-Yao +2 more
doaj +1 more source
Additive List Coloring of Planar Graphs with Given Girth
Discussiones Mathematicae Graph Theory, 2020 An additive coloring of a graph G is a labeling of the vertices of G from {1, 2, . . . , k} such that two adjacent vertices have distinct sums of labels on their neighbors.
Brandt Axel +2 more
doaj +1 more source