All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 15 Next

Displaying 281 – 300 of 715

Showing per page

Generalized total colorings of graphs

Mieczysław Borowiecki, Arnfried Kemnitz, Massimiliano Marangio, Peter Mihók (2011)

Discussiones Mathematicae Graph Theory

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let P and Q be additive hereditary properties of graphs. A (P,Q)-total coloring of a simple graph G is a coloring of the vertices V(G) and edges E(G) of G such that for each color i the vertices colored by i induce a subgraph of property P, the edges colored by i induce a subgraph of property Q and incident vertices and edges obtain different colors. In this paper we present...

Graph colorings with local constraints - a survey

Zsolt Tuza (1997)

Discussiones Mathematicae Graph Theory

We survey the literature on those variants of the chromatic number problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the list colorings and the precoloring extensions are considered. In one of the most general formulations, a graph G = (V,E), sets L(v) of admissible colors, and natural numbers c v for the vertices v ∈ V are given, and the question is whether...

Graphs maximal with respect to hom-properties

Jan Kratochvíl, Peter Mihók, Gabriel Semanišin (1997)

Discussiones Mathematicae Graph Theory

For a simple graph H, →H denotes the class of all graphs that admit homomorphisms to H (such classes of graphs are called hom-properties). We investigate hom-properties from the point of view of the lattice of hereditary properties. In particular, we are interested in characterization of maximal graphs belonging to →H. We also provide a description of graphs maximal with respect to reducible hom-properties and determine the maximum number of edges of graphs belonging to →H.

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

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

Discussiones Mathematicae Graph Theory

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 G, denoted by...

Graphs with 4-Rainbow Index 3 and n − 1

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

Discussiones Mathematicae Graph Theory

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 by rxk(G)....

Graphs with rainbow connection number two

Arnfried Kemnitz, Ingo Schiermeyer (2011)

Discussiones Mathematicae Graph Theory

An edge-coloured graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colours. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow connected. In this paper we prove that rc(G) = 2 for every connected graph G of order n and size m, where n - 1 2 + 1 ≤ m ≤ n 2 - 1 . We also characterize graphs with rainbow connection number two and large clique number.

Grundy number of graphs

Brice Effantin, Hamamache Kheddouci (2007)

Discussiones Mathematicae Graph Theory

The Grundy number of a graph G is the maximum number k of colors used to color the vertices of G such that the coloring is proper and every vertex x colored with color i, 1 ≤ i ≤ k, is adjacent to (i-1) vertices colored with each color j, 1 ≤ j ≤ i -1. In this paper we give bounds for the Grundy number of some graphs and cartesian products of graphs. In particular, we determine an exact value of this parameter for n-dimensional meshes and some n-dimensional toroidal meshes. Finally, we present an...

Hajós' theorem for list colorings of hypergraphs

Claude Benzaken, Sylvain Gravier, Riste Skrekovski (2003)

Discussiones Mathematicae Graph Theory

A well-known theorem of Hajós claims that every graph with chromathic number greater than k can be constructed from disjoint copies of the complete graph K k + 1 by repeated application of three simple operations. This classical result has been extended in 1978 to colorings of hypergraphs by C. Benzaken and in 1996 to list-colorings of graphs by S. Gravier. In this note, we capture both variations to extend Hajós’ theorem to list-colorings of hypergraphs.

Hamiltonian colorings of graphs with long cycles

Ladislav Nebeský (2003)

Mathematica Bohemica

By a hamiltonian coloring of a connected graph G of order n ≥ 1 we mean a mapping c of V ( G ) into the set of all positive integers such that | c ( x ) - c ( y ) | ≥ n - 1 - D G ( x , y ) (where D G ( x , y ) denotes the length of a longest x - y path in G ) for all distinct x , y ∈ G . In this paper we study hamiltonian colorings of non-hamiltonian connected graphs with long cycles, mainly of connected graphs of order n ≥ 5 with circumference n - 2 .

Currently displaying 281 – 300 of 715