Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 10

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  vertex coloring
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

Star Coloring of Subcubic Graphs

100%
Karthick T., Subramanian C. R.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
373-385
EN
A star coloring of an undirected graph G is a coloring of the vertices of G such that (i) no two adjacent vertices receive the same color, and (ii) no path on 4 vertices is bi-colored. The star chromatic number of G, χs(G), is the minimum number of colors needed to star color G. In this paper, we show that if a graph G is either non-regular subcubic or cubic with girth at least 6, then χs(G) ≤ 6, and the bound can be realized in linear time.
2
Content available remote

On the Rainbow Vertex-Connection

100%
Li X., Shi Y.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
307-313
EN
A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertexconnected. It was proved that if G is a graph of order n with minimum degree δ, then rvc(G) < 11n/δ. In this paper, we show that rvc(G) ≤ 3n/(δ+1)+5 for [xxx] and n ≥ 290, while rvc(G) ≤ 4n/(δ + 1) + 5 for [xxx] and rvc(G) ≤ 4n/(δ + 1) + C(δ) for 6 ≤ δ ≤ 15, where [xxx]. We also prove that rvc(G) ≤ 3n/4 − 2 for δ = 3, rvc(G) ≤ 3n/5 − 8/5 for δ = 4 and rvc(G) ≤ n/2 − 2 for δ = 5. Moreover, an example constructed by Caro et al. shows that when [xxx] and δ = 3, 4, 5, our bounds are seen to be tight up to additive constants.
3
Content available remote

Kaleidoscopic Colorings of Graphs

100%
Chartrand G., English S., Zhang P.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
711-727
EN
For an r-regular graph G, let c : E(G) → [k] = {1, 2, . . . , k}, k ≥ 3, be an edge coloring of G, where every vertex of G is incident with at least one edge of each color. For a vertex v of G, the multiset-color cm(v) of v is defined as the ordered k-tuple (a1, a2, . . . , ak) or a1a2 … ak, where ai (1 ≤ i ≤ k) is the number of edges in G colored i that are incident with v. The edge coloring c is called k-kaleidoscopic if cm(u) ≠ cm(v) for every two distinct vertices u and v of G. A regular graph G is called a k-kaleidoscope if G has a k-kaleidoscopic coloring. It is shown that for each integer k ≥ 3, the complete graph Kk+3 is a k-kaleidoscope and the complete graph Kn is a 3-kaleidoscope for each integer n ≥ 6. The largest order of an r-regular 3-kaleidoscope is [...] (r−12) $\left( {\matrix{{r - 1} \cr 2 } } \right)$ . It is shown that for each integer r ≥ 5 such that r ≢ 3 (mod 4), there exists an r-regular 3-kaleidoscope of order [...] (r−12) $\left( {{{r - 1} \over 2}} \right)$ .
4
Content available remote

On Twin Edge Colorings of Graphs

100%
Andrews E., Helenius L., Johnston D., VerWys J., Zhang P.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
613-627
EN
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
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Grundy number of graphs

100%
Effantin B., Kheddouci H.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 1
5-18
EN
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 algorithm to generate all graphs for a given Grundy number.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On multiset colorings of graphs

100%
Okamoto F., Salehi E., Zhang P.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 1
137-153
EN
A vertex coloring of a graph G is a multiset coloring if the multisets of colors of the neighbors of every two adjacent vertices are different. The minimum k for which G has a multiset k-coloring is the multiset chromatic number χₘ(G) of G. For every graph G, χₘ(G) is bounded above by its chromatic number χ(G). The multiset chromatic numbers of regular graphs are investigated. It is shown that for every pair k, r of integers with 2 ≤ k ≤ r - 1, there exists an r-regular graph with multiset chromatic number k. It is also shown that for every positive integer N, there is an r-regular graph G such that χ(G) - χₘ(G) = N. In particular, it is shown that χₘ(Kₙ × K₂) is asymptotically √n. In fact, $χₘ(Kₙ × K₂) = χₘ(cor(K_{n+1}))$. The corona cor(G) of a graph G is the graph obtained from G by adding, for each vertex v in G, a new vertex v' and the edge vv'. It is shown that χₘ(cor(G)) ≤ χₘ(G) for every nontrivial connected graph G. The multiset chromatic numbers of the corona of all complete graphs are determined. On Multiset Colorings of Graphs From this, it follows that for every positive integer N, there exists a graph G such that χₘ(G) - χₘ(cor(G)) ≥ N. The result obtained on the multiset chromatic number of the corona of complete graphs is then extended to the corona of all regular complete multipartite graphs.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

3-consecutive c-colorings of graphs

100%
Bujtás C., Sampathkumar E., Tuza Z., Subramanya M., Dominic C.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 3
393-405
EN
A 3-consecutive C-coloring of a graph G = (V,E) is a mapping φ:V → ℕ such that every path on three vertices has at most two colors. We prove general estimates on the maximum number $(χ̅)_{3CC}(G)$ of colors in a 3-consecutive C-coloring of G, and characterize the structure of connected graphs with $(χ̅)_{3CC}(G) ≥ k$ for k = 3 and k = 4.
8
Content available remote

Distinguishing Cartesian Products of Countable Graphs

88%
Estaji E., Imrich W., Kalinowski R., Pilśniak M., Tucker T.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
155-164
EN
The distinguishing number D(G) of a graph G is the minimum number of colors needed to color the vertices of G such that the coloring is preserved only by the trivial automorphism. In this paper we improve results about the distinguishing number of Cartesian products of finite and infinite graphs by removing restrictions to prime or relatively prime factors.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Erdős regular graphs of even degree

88%
Dobrynin A., Mel'nikov L., Pyatkin A.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 2
269-279
EN
In 1960, Dirac put forward the conjecture that r-connected 4-critical graphs exist for every r ≥ 3. In 1989, Erdös conjectured that for every r ≥ 3 there exist r-regular 4-critical graphs. A method for finding r-regular 4-critical graphs and the numbers of such graphs for r ≤ 10 have been reported in [6,7]. Results of a computer search for graphs of degree r = 12,14,16 are presented. All the graphs found are both r-regular and r-connected.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Color-bounded hypergraphs, V: host graphs and subdivisions

63%
Bujtás C., Tuza Z., Voloshin V.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
223-238
EN
A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set 𝓔 = {E₁,...,Eₘ}, together with integers $s_i$ and $t_i$ satisfying $1 ≤ s_i ≤ t_i ≤ |E_i|$ for each i = 1,...,m. A vertex coloring φ is proper if for every i, the number of colors occurring in edge $E_i$ satisfies $s_i ≤ |φ(E_i)| ≤ t_i$. The hypergraph ℋ is colorable if it admits at least one proper coloring. We consider hypergraphs ℋ over a "host graph", that means a graph G on the same vertex set X as ℋ, such that each $E_i$ induces a connected subgraph in G. In the current setting we fix a graph or multigraph G₀, and assume that the host graph G is obtained by some sequence of edge subdivisions, starting from G₀. The colorability problem is known to be NP-complete in general, and also when restricted to 3-uniform "mixed hypergraphs", i.e., color-bounded hypergraphs in which $|E_i| = 3$ and $1 ≤ s_i ≤ 2 ≤ t_i ≤ 3$ holds for all i ≤ m. We prove that for every fixed graph G₀ and natural number r, colorability is decidable in polynomial time over the class of r-uniform hypergraphs (and more generally of hypergraphs with $|E_i| ≤ r$ for all 1 ≤ i ≤ m) having a host graph G obtained from G₀ by edge subdivisions. Stronger bounds are derived for hypergraphs for which G₀ is a tree.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.