Displaying similar documents to “Vertex-distinguishing edge-colorings of linear forests”

Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least six

Yuehua Bu, Ko-Wei Lih, Weifan Wang (2011)

Discussiones Mathematicae Graph Theory

Similarity:

An adjacent vertex distinguishing edge-coloring of a graph G is a proper edge-coloring o G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring of G is denoted by χ'ₐ(G). We prove that χ'ₐ(G) is at most the maximum degree plus 2 if G is a planar graph without isolated edges whose girth is at least 6. This gives new evidence to a conjecture proposed in [Z. Zhang, L. Liu,...

A Note on Neighbor Expanded Sum Distinguishing Index

Evelyne Flandrin, Hao Li, Antoni Marczyk, Jean-François Saclé, Mariusz Woźniak (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A total k-coloring of a graph G is a coloring of vertices and edges of G using colors of the set [k] = {1, . . . , k}. These colors can be used to distinguish the vertices of G. There are many possibilities of such a distinction. In this paper, we consider the sum of colors on incident edges and adjacent vertices.

Rainbow H -factors.

Yuster, Raphael (2006)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

On the Vertex Folkman Numbers Fv(2,...,2;q)

Nenov, Nedyalko (2009)

Serdica Mathematical Journal

Similarity:

2000 Mathematics Subject Classification: 05C55. In this paper we shall compute the Folkman numbers ... We prove also new bounds for some vertex and edge Folkman numbers.

On Twin Edge Colorings of Graphs

Eric Andrews, Laars Helenius, Daniel Johnston, Jonathon VerWys, Ping Zhang (2014)

Discussiones Mathematicae Graph Theory

Similarity:

A twin edge k-coloring of a graph G is a proper edge coloring of G with the elements of Zk so that the induced vertex coloring in which the color of a vertex v in G is the sum (in Zk) of the colors of the edges incident with v is a proper vertex coloring. The minimum k for which G has a twin edge k-coloring is called the twin chromatic index of G. Among the results presented are formulas for the twin chromatic index of each complete graph and each complete bipartite graph

A decomposition of gallai multigraphs

Alexander Halperin, Colton Magnant, Kyle Pula (2014)

Discussiones Mathematicae Graph Theory

Similarity:

An edge-colored cycle is rainbow if its edges are colored with distinct colors. A Gallai (multi)graph is a simple, complete, edge-colored (multi)graph lacking rainbow triangles. As has been previously shown for Gallai graphs, we show that Gallai multigraphs admit a simple iterative construction. We then use this structure to prove Ramsey-type results within Gallai colorings. Moreover, we show that Gallai multigraphs give rise to a surprising and highly structured decomposition into directed...

A Tight Bound on the Set Chromatic Number

Jean-Sébastien Sereni, Zelealem B. Yilma (2013)

Discussiones Mathematicae Graph Theory

Similarity:

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, respectively. This answers in the affirmative a conjecture of Gera, Okamoto, Rasmussen and Zhang.

Three edge-coloring conjectures

Richard H. Schelp (2002)

Discussiones Mathematicae Graph Theory

Similarity:

The focus of this article is on three of the author's open conjectures. The article itself surveys results relating to the conjectures and shows where the conjectures are known to hold.