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: 20

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

Wyniki wyszukiwania

help Sortuj według:

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

A Note on Neighbor Expanded Sum Distinguishing Index

100%
Flandrin E., Li H., Marczyk A., Saclé J.-F., Woźniak M.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
29-37
EN
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.
2
Content available remote

Unique-Maximum Coloring Of Plane Graphs

100%
Fabrici I., Göring F.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
95-102
EN
A unique-maximum k-coloring with respect to faces of a plane graph G is a coloring with colors 1, . . . , k so that, for each face of G, the maximum color occurs exactly once on the vertices of α. We prove that any plane graph is unique-maximum 3-colorable and has a proper unique-maximum coloring with 6 colors.
3
Content available remote

Characterization Results for theL(2, 1, 1)-Labeling Problem on Trees

100%
Zhang X., Deng K.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
611-622
EN
An L(2, 1, 1)-labeling of a graph G is an assignment of non-negative integers (labels) to the vertices of G such that adjacent vertices receive labels with difference at least 2, and vertices at distance 2 or 3 receive distinct labels. The span of such a labelling is the difference between the maximum and minimum labels used, and the minimum span over all L(2, 1, 1)-labelings of G is called the L(2, 1, 1)-labeling number of G, denoted by λ2,1,1(G). It was shown by King, Ras and Zhou in [The L(h, 1, 1)-labelling problem for trees, European J. Combin. 31 (2010) 1295–1306] that every tree T has Δ2(T) − 1 ≤ λ2,1,1(T) ≤ Δ2(T), where Δ2(T) = maxuv∈E(T)(d(u) + d(v)). And they conjectured that almost all trees have the L(2, 1, 1)-labeling number attain the lower bound. This paper provides some sufficient conditions for λ2,1,1(T) = Δ2(T). Furthermore, we show that the sufficient conditions we provide are also necessary for trees with diameter at most 6.
4
Content available remote

M2-Edge Colorings Of Cacti And Graph Joins

100%
Czap J., Šugerek P., Ivančo J.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
59-69
EN
An edge coloring φ of a graph G is called an M2-edge coloring if |φ(v)| ≤ 2 for every vertex v of G, where φ(v) is the set of colors of edges incident with v. Let 𝒦2(G) denote the maximum number of colors used in an M2-edge coloring of G. In this paper we determine 𝒦2(G) for trees, cacti, complete multipartite graphs and graph joins.
5
Content available remote

All Tight Descriptions of 3-Stars in 3-Polytopes with Girth 5

100%
Borodin O. V., Ivanova A. O.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
5-12
EN
Lebesgue (1940) proved that every 3-polytope P5 of girth 5 has a path of three vertices of degree 3. Madaras (2004) refined this by showing that every P5 has a 3-vertex with two 3-neighbors and the third neighbor of degree at most 4. This description of 3-stars in P5s is tight in the sense that no its parameter can be strengthened due to the dodecahedron combined with the existence of a P5 in which every 3-vertex has a 4-neighbor. We give another tight description of 3-stars in P5s: there is a vertex of degree at most 4 having three 3-neighbors. Furthermore, we show that there are only these two tight descriptions of 3-stars in P5s. Also, we give a tight description of stars with at least three rays in P5s and pose a problem of describing all such descriptions. Finally, we prove a structural theorem about P5s that might be useful in further research.
6
Content available remote

Upper Bounds for the Strong Chromatic Index of Halin Graphs

100%
Hu Z., Lih K.-W., Liu D. D.-F.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
5-26
EN
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 maximum degree Δ and characteristic tree T. We prove that χ′s(G) ⩽ 2Δ + 1 when Δ ⩾ 4. In addition, we show that if Δ = 4 and G is not a wheel, then χ′s(G) ⩽ χ′s(T) + 2. A similar result for Δ = 3 was established by Lih and Liu [21].
7
Content available remote

Coloring subgraphs with restricted amounts of hues

100%
Goddard W., Melville R.
Open Mathematics
|
2017
|
tom 15
|
nr 1
1171-1180
EN
We consider vertex colorings where the number of colors given to specified subgraphs is restricted. In particular, given some fixed graph F and some fixed set A of positive integers, we consider (not necessarily proper) colorings of the vertices of a graph G such that, for every copy of F in G, the number of colors it receives is in A. This generalizes proper colorings, defective coloring, and no-rainbow coloring, inter alia. In this paper we focus on the case that A is a singleton set. In particular, we investigate the colorings where the graph F is a star or is 1-regular.
8
Content available remote

The structure of plane graphs with independent crossings and its applications to coloring problems

81%
Zhang X., Liu G.
Open Mathematics
|
2013
|
tom 11
|
nr 2
308-321
EN
If a graph G has a drawing in the plane in such a way that every two crossings are independent, then we call G a plane graph with independent crossings or IC-planar graph for short. In this paper, the structure of IC-planar graphs with minimum degree at least two or three is studied. By applying their structural results, we prove that the edge chromatic number of G is Δ if Δ ≥ 8, the list edge (resp. list total) chromatic number of G is Δ (resp. Δ + 1) if Δ ≥ 14 and the linear arboricity of G is ℈Δ/2⌊ if Δ ≥ 17, where G is an IC-planar graph and Δ is the maximum degree of G.
9
Content available remote

Maximum Edge-Colorings Of Graphs

81%
Jendrol’ S., Vrbjarová M.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
117-125
EN
An r-maximum k-edge-coloring of G is a k-edge-coloring of G having a property that for every vertex v of degree dG(v) = d, d ≥ r, the maximum color, that is present at vertex v, occurs at v exactly r times. The r-maximum index [...] χr′(G) $\chi _r^\prime (G)$ is defined to be the minimum number k of colors needed for an r-maximum k-edge-coloring of graph G. In this paper we show that [...] χr′(G)≤3 $\chi _r^\prime (G) \le 3$ for any nontrivial connected graph G and r = 1 or 2. The bound 3 is tight. All graphs G with [...] χ1′(G)=i $\chi _1^\prime (G) = i$ , i = 1, 2, 3 are characterized. The precise value of the r-maximum index, r ≥ 1, is determined for trees and complete graphs.
10
Content available remote

Cubic Graphs with Total Domatic Number at Least Two

81%
Akbari S., Motiei M., Mozaffari S., Yazdanbod S.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
75-82
EN
Let G be a graph with no isolated vertex. A total dominating set of G is a set S of vertices of G such that every vertex is adjacent to at least one vertex in S. The total domatic number of a graph is the maximum number of total dominating sets which partition the vertex set of G. In this paper we provide a criterion under which a cubic graph has total domatic number at least two.
11
Content available remote

Kaleidoscopic Colorings of Graphs

81%
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)$ .
12
Content available remote

Rainbow Connection Number of Graphs with Diameter 3

81%
Li H., Li X., Sun Y.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 1
141-154
EN
A path in an edge-colored graph G is rainbow if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the smallest integer k for which there exists a k-edge-coloring of G such that every pair of distinct vertices of G is connected by a rainbow path. Let f(d) denote the minimum number such that rc(G) ≤ f(d) for each bridgeless graph G with diameter d. In this paper, we shall show that 7 ≤ f(3) ≤ 9.
13
Content available remote

On (p, 1)-total labelling of 1-planar graphs

81%
Zhang X., Yu Y., Liu G.
Open Mathematics
|
2011
|
tom 9
|
nr 6
1424-1434
EN
A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is proved that the (p, 1)-total labelling number of every 1-planar graph G is at most Δ(G) + 2p − 2 provided that Δ(G) ≥ 8p+4 or Δ(G) ≥ 6p+2 and g(G) ≥ 4. As a consequence, the well-known (p, 1)-total labelling conjecture has been confirmed for some 1-planar graphs.
14
Content available remote

On Generalized Sierpiński Graphs

62%
Rodríguez-Velázquez J. A., Rodríguez-Bazan E. D., Estrada-Moreno A.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
547-560
EN
In this paper we obtain closed formulae for several parameters of generalized Sierpiński graphs S(G, t) in terms of parameters of the base graph G. In particular, we focus on the chromatic, vertex cover, clique and domination numbers.
15
Content available remote

Note On The Game Colouring Number Of Powers Of Graphs

62%
Andres S. D., Theuser A.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 1
31-42
EN
We generalize the methods of Esperet and Zhu [6] providing an upper bound for the game colouring number of squares of graphs to obtain upper bounds for the game colouring number of m-th powers of graphs, m ≥ 3, which rely on the maximum degree and the game colouring number of the underlying graph. Furthermore, we improve these bounds in case the underlying graph is a forest.
16
Content available remote

Chromatic Properties of the Pancake Graphs

62%
Konstantinova E.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
777-787
EN
Chromatic properties of the Pancake graphs Pn, n ⩾ 2, that are Cayley graphs on the symmetric group Symn generated by prefix-reversals are investigated in the paper. It is proved that for any n ⩾ 3 the total chromatic number of Pn is n, and it is shown that the chromatic index of Pn is n − 1. We present upper bounds on the chromatic number of the Pancake graphs Pn, which improve Brooks’ bound for n ⩾ 7 and Katlin’s bound for n ⩽ 28. Algorithms of a total n-coloring and a proper (n − 1)-coloring are given.
17
Content available remote

Distinguishing Cartesian Products of Countable Graphs

62%
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.
18
Content available remote

Packing Coloring of Some Undirected and Oriented Coronae Graphs

62%
Laïche D., Bouchemakh I., Sopena É.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
665-690
EN
The packing chromatic number χρ(G) of a graph G is the smallest integer k such that its set of vertices V(G) can be partitioned into k disjoint subsets V1, . . . , Vk, in such a way that every two distinct vertices in Vi are at distance greater than i in G for every i, 1 ≤ i ≤ k. For a given integer p ≥ 1, the p-corona of a graph G is the graph obtained from G by adding p degree-one neighbors to every vertex of G. In this paper, we determine the packing chromatic number of p-coronae of paths and cycles for every p ≥ 1. Moreover, by considering digraphs and the (weak) directed distance between vertices, we get a natural extension of the notion of packing coloring to digraphs. We then determine the packing chromatic number of orientations of p-coronae of paths and cycles.
19
Content available remote

Rainbow Vertex-Connection and Forbidden Subgraphs

52%
Li W., Li X., Zhang J.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 38
|
nr 1
143-154
EN
A path in a vertex-colored graph is called vertex-rainbow if its internal vertices have pairwise distinct colors. A vertex-colored graph G is rainbow vertex-connected if for any two distinct vertices of G, there is a vertex-rainbow path connecting them. For a connected graph G, the rainbow vertex-connection number of G, denoted by rvc(G), is defined as the minimum number of colors that are required to make G rainbow vertex-connected. In this paper, we find all the families ℱ of connected graphs with |ℱ| ∈ {1, 2}, for which there is a constant kℱ such that, for every connected ℱ-free graph G, rvc(G) ≤ diam(G) + kℱ, where diam(G) is the diameter of G.
20
Content available remote

Onθ-commutators and the corresponding non-commuting graphs

52%
Shalchi S., Erfanian A., Farrokhi DG M.
Open Mathematics
|
2017
|
tom 15
|
nr 1
1530-1538
EN
The θ-commutators of elements of a group with respect to an automorphism are introduced and their properties are investigated. Also, corresponding to θ-commutators, we define the θ-non-commuting graphs of groups and study their correlations with other notions. Furthermore, we study independent sets in θ-non-commuting graphs, which enable us to evaluate the chromatic number of such graphs.
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ć.