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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
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ć.