Displaying similar documents to “Some maximum multigraphs and edge/vertex distance colourings”

Upper Bounds for the Strong Chromatic Index of Halin Graphs

Ziyu Hu, Ko-Wei Lih, Daphne Der-Fen Liu (2018)

Discussiones Mathematicae Graph Theory

Similarity:

The strong chromatic index of a graph G, denoted by χ′s(G), is the minimum number of vertex induced matchings needed to partition the edge set of G. Let T be a tree without vertices of degree 2 and have at least one vertex of degree greater than 2. We construct a Halin graph G by drawing T on the plane and then drawing a cycle C connecting all its leaves in such a way that C forms the boundary of the unbounded face. We call T the characteristic tree of G. Let G denote a Halin graph with...

Graphs with 4-Rainbow Index 3 and n − 1

Xueliang Li, Ingo Schiermeyer, Kang Yang, Yan Zhao (2015)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a nontrivial connected graph with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ ℕ, where adjacent edges may be colored the same. A tree T in G is called a rainbow tree if no two edges of T receive the same color. For a vertex set S ⊆ V (G), a tree that connects S in G is called an S-tree. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for every set S of k vertices of V (G) is called the k-rainbow index of G, denoted...

Coloring with no 2-colored P 4 's.

Albertson, Michael O., Chappell, Glenn G., Kierstead, H.A., Kündgen, André, Ramamurthi, Radhika (2004)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

On-line Ramsey theory for bounded degree graphs.

Butterfield, Jane, Grauman, Tracy, Kinnersley, William B., Milans, Kevin G., Stocker, Christopher, West, Douglas B. (2011)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Backbone colorings along stars and matchings in split graphs: their span is close to the chromatic number

Hajo Broersma, Bert Marchal, Daniel Paulusma, A.N.M. Salman (2009)

Discussiones Mathematicae Graph Theory

Similarity:

We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a λ-backbone coloring for G and H is a proper vertex coloring V→ {1,2,...} of G in which the colors assigned to adjacent vertices in H differ by at least λ. The algorithmic and combinatorial properties of backbone colorings have been studied for various types of backbones in a number of papers....

A note on total colorings of planar graphs without 4-cycles

Ping Wang, Jian-Liang Wu (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a 2-connected planar graph with maximum degree Δ such that G has no cycle of length from 4 to k, where k ≥ 4. Then the total chromatic number of G is Δ +1 if (Δ,k) ∈ {(7,4),(6,5),(5,7),(4,14)}.

Graphs with 3-Rainbow Index n − 1 and n − 2

Xueliang Li, Ingo Schiermeyer, Kang Yang, Yan Zhao (2015)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V (G),E(G)) be a nontrivial connected graph of order n with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ N, where adjacent edges may be colored the same. A tree T in G is a rainbow tree if no two edges of T receive the same color. For a vertex set S ⊆ V (G), a tree connecting S in G is called an S-tree. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for each k-subset S of V (G) is called the k-rainbow index of...