共查询到20条相似文献,搜索用时 15 毫秒
1.
The distinguishing chromatic number of a graph, , is the minimum number of colours required to properly colour the vertices of so that the only automorphism of that preserves colours is the identity. There are many classes of graphs for which the distinguishing chromatic number has been studied, including Cartesian products of complete graphs (Jerebic and Klav?ar, 2010). In this paper we determine the distinguishing chromatic number of the complement of the Cartesian product of complete graphs, providing an interesting class of graphs, some of which have distinguishing chromatic number equal to the chromatic number, and others for which the difference between the distinguishing chromatic number and chromatic number can be arbitrarily large. 相似文献
2.
3.
Janja Jerebic 《Discrete Mathematics》2010,310(12):1715-1720
A labeling of a graph G is distinguishing if it is only preserved by the trivial automorphism of G. The distinguishing chromatic number of G is the smallest integer k such that G has a distinguishing labeling that is at the same time a proper vertex coloring. The distinguishing chromatic number of the Cartesian product is determined for all k and n. In most of the cases it is equal to the chromatic number, thus answering a question of Choi, Hartke and Kaul whether there are some other graphs for which this equality holds. 相似文献
4.
5.
Equitable colorings of Kronecker products of graphs 总被引:1,自引:0,他引:1
Wu-Hsiung Lin 《Discrete Applied Mathematics》2010,158(16):1816-1826
For a positive integer k, a graph G is equitably k-colorable if there is a mapping f:V(G)→{1,2,…,k} such that f(x)≠f(y) whenever xy∈E(G) and ||f−1(i)|−|f−1(j)||≤1 for 1≤i<j≤k. The equitable chromatic number of a graph G, denoted by χ=(G), is the minimum k such that G is equitably k-colorable. The equitable chromatic threshold of a graph G, denoted by , is the minimum t such that G is equitably k-colorable for k≥t. The current paper studies equitable chromatic numbers of Kronecker products of graphs. In particular, we give exact values or upper bounds on χ=(G×H) and when G and H are complete graphs, bipartite graphs, paths or cycles. 相似文献
6.
For an integer r>0, a conditional(k,r)-coloring of a graph G is a proper k-coloring of the vertices of G such that every vertex of degree at least r in G will be adjacent to vertices with at least r different colors. The smallest integer k for which a graph G has a conditional (k,r)-coloring is the rth order conditional chromatic number χr(G). In this paper, the behavior and bounds of conditional chromatic number of a graph G are investigated. 相似文献
7.
In a simple graphG=(X.E) a positive integerc
i is associated with every nodei. We consider node colorings where nodei receives a setS(i) ofc
i consecutive colors andS(i)S(j)=Ø whenever nodesi andj are linked inG. Upper bounds on the minimum number of colors needed are derived. The case of perfect graphs is discussed.
Zusammenfassung In einem schlichten GraphenG=(X, E) gibt man jedem Knotenpunkti einen positiven ganzzahligen Wertc i. Wir betrachten Färbungen der Knotenpunkte, bei denen jeder Knotenpunkti eine MengeS(i) vonc i konsekutiven Farben erhält mitS(i)S(j)=Ø wenn die Kante [i.j] existiert. Obere Grenzen für die minimale Anzahl der Farben solcher Färbungen werden hergeleitet. Der Fall der perfekten Graphen wird auch kurz diskutiert.相似文献
8.
We consider lower bounds on the the vertex‐distinguishing edge chromatic number of graphs and prove that these are compatible with a conjecture of Burris and Schelp 8 . We also find upper bounds on this number for certain regular graphs G of low degree and hence verify the conjecture for a reasonably large class of such graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 95–109, 2003 相似文献
9.
An (r, n)-split coloring of a complete graph is an edge coloring with r colors under which the vertex set is partitionable into r parts so that for each i, part i does not contain Kn in color i. This generalizes the notion of split graphs which correspond to (2, 2)-split colorings. The smallest N for which the complete graph KN has a coloring which is not (r, n)-split is denoted by ƒr(n). Balanced (r,n)-colorings are defined as edge r-colorings of KN such that every subset of [N/r] vertices contains a monochromatic Kn in all colors. Then gr(n) is defined as the smallest N such that KN has a balanced (r, n)-coloring. The definitions imply that fr(n) gr(n). The paper gives estimates and exact values of these functions for various choices of parameters. 相似文献
10.
《Discrete Mathematics》2022,345(2):112690
For a bipartite graph G with parts X and Y, an X-interval coloring is a proper edge coloring of G by integers such that the colors on the edges incident to any vertex in X form an interval. Denote by the minimum k such that G has an X-interval coloring with k colors. Casselgren and Toft (2016) [12] asked whether there is a polynomial such that if G has maximum degree at most Δ, then . In this short note, we answer this question in the affirmative; in fact, we prove that a cubic polynomial suffices. We also deduce some improved upper bounds on for bipartite graphs with small maximum degree. 相似文献
11.
12.
The distinguishing number D(G) of a graph is the least integer d such that there is a d‐labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G ≠ K2, K3 with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 ( 1 ), #N17] on powers of prime graphs, and results of Klav?ar and Zhu [Eu J Combin, to appear]. More generally, we also prove that d(G □ H) = 2 if G and H are relatively prime and |H| ≤ |G| < 2|H| ? |H|. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 250–260, 2006 相似文献
13.
A proper coloring of the edges of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. For certain graphs G, a′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ 16 Δ(G) for any graph G. We prove that there exists a constant c such that a′(G) ≤ Δ(G) + 2 for any graph G whose girth is at least cΔ(G) log Δ(G), and conjecture that this upper bound for a′(G) holds for all graphs G. We also show that a′(G) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001 相似文献
14.
The distinguishing chromatic number of a graph , denoted , is defined as the minimum number of colors needed to properly color such that no non-trivial automorphism of fixes each color class of . In this paper, we consider random Cayley graphs defined over certain abelian groups with , and show that with probability at least , . 相似文献
15.
Robert E. Jamison 《Discrete Applied Mathematics》2011,159(7):595-604
An edge coloring of a graph is orientable if and only if it is possible to orient the edges of the graph so that the color of each edge is determined by the head of its corresponding oriented arc. The goals of this paper include finding a forbidden substructure characterization of orientable colorings and giving a linear time recognition algorithm for orientable colorings.An edge coloring is lexical if and only if it is possible to number the vertices of the graph so that the color of each edge is determined by its lower endpoint. Lexical colorings are, of course, the orientable colorings in which the underlying orientation is acyclic. Lexical colorings play an important role in Canonical Ramsey theory, and it is this standpoint that motivates the current study. 相似文献
16.
A well-established generalization of graph coloring is the concept of list coloring. In this setting, each vertex v of a graph G is assigned a list L(v) of k colors and the goal is to find a proper coloring c of G with c(v)∈L(v). The smallest integer k for which such a coloring c exists for every choice of lists is called the list chromatic number of G and denoted by χl(G).We study list colorings of Cartesian products of graphs. We show that unlike in the case of ordinary colorings, the list chromatic number of the product of two graphs G and H is not bounded by the maximum of χl(G) and χl(H). On the other hand, we prove that χl(G×H)?min{χl(G)+col(H),col(G)+χl(H)}-1 and construct examples of graphs G and H for which our bound is tight. 相似文献
17.
18.
An injective coloring of a graph is a vertex coloring where two vertices have distinct colors if a path of length two exists between them. In this paper some results on injective colorings of planar graphs with few colors are presented. We show that all planar graphs of girth ≥ 19 and maximum degree Δ are injectively Δ-colorable. We also show that all planar graphs of girth ≥ 10 are injectively (Δ+1)-colorable, that Δ+4 colors are sufficient for planar graphs of girth ≥ 5 if Δ is large enough, and that subcubic planar graphs of girth ≥ 7 are injectively 5-colorable. 相似文献
19.
We show some consequences of results of Gallai concerning edge colorings of complete graphs that contain no tricolored triangles. We prove two conjectures of Bialostocki and Voxman about the existence of special monochromatic spanning trees in such colorings. We also determine the size of largest monochromatic stars guaranteed to occur. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 211–216, 2004 相似文献
20.