共查询到20条相似文献,搜索用时 31 毫秒
1.
Bojan Vučković 《Discrete Mathematics》2018,341(5):1472-1478
An adjacent vertex distinguishing total -coloring of a graph is a proper total -coloring of such that any pair of adjacent vertices have different sets of colors. The minimum number needed for such a total coloring of is denoted by . In this paper we prove that if , and in general. This improves a result in Huang et al. (2012) which states that for any graph with . 相似文献
2.
An -dynamic -coloring of a graph is a proper -coloring such that for any vertex , there are at least distinct colors in . The -dynamic chromatic number of a graph is the least such that there exists an -dynamic -coloring of . The list-dynamic chromatic number of a graph is denoted by .Recently, Loeb et al. (0000) showed that the list -dynamic chromatic number of a planar graph is at most 10. And Cheng et al. (0000) studied the maximum average condition to have , or . On the other hand, Song et al. (2016) showed that if is planar with girth at least 6, then for any .In this paper, we study list 3-dynamic coloring in terms of maximum average degree. We show that if , if , and if . All of the bounds are tight. 相似文献
3.
Yoshihiro Asayama Yuki Kawasaki Seog-Jin Kim Atsuhiro Nakamoto Kenta Ozeki 《Discrete Mathematics》2018,341(11):2988-2994
An -dynamic -coloring of a graph is a proper -coloring such that any vertex has at least distinct colors in . The -dynamic chromatic number of a graph is the least such that there exists an -dynamic -coloring of .Loeb et al. (2018) showed that if is a planar graph, then , and there is a planar graph with . Thus, finding an optimal upper bound on for a planar graph is a natural interesting problem. In this paper, we show that if is a planar triangulation. The upper bound is sharp. 相似文献
4.
For a subgraph of , let be the maximum number of vertices of that are pairwise distance at least three in . In this paper, we prove three theorems. Let be a positive integer, and let be a subgraph of an -connected claw-free graph . We prove that if , then either can be covered by a cycle in , or there exists a cycle in such that . This result generalizes the result of Broersma and Lu that has a cycle covering all the vertices of if . We also prove that if , then either can be covered by a path in , or there exists a path in such that . By using the second result, we prove the third result. For a tree , a vertex of with degree one is called a leaf of . For an integer , a tree which has at most leaves is called a -ended tree. We prove that if , then has a -ended tree covering all the vertices of . This result gives a positive answer to the conjecture proposed by Kano et al. (2012). 相似文献
5.
A star edge-coloring of a graph is a proper edge coloring such that every 2-colored connected subgraph of is a path of length at most 3. For a graph , let the list star chromatic index of , , be the minimum such that for any -uniform list assignment for the set of edges, has a star edge-coloring from . Dvo?ák et al. (2013) asked whether the list star chromatic index of every subcubic graph is at most 7. In Kerdjoudj et al. (2017) we proved that it is at most 8. In this paper we consider graphs with any maximum degree, we proved that if the maximum average degree of a graph is less than (resp. 3), then (resp. ). 相似文献
6.
7.
Jianbei An Heiko Dietrich Shih-Chang Huang 《Journal of Pure and Applied Algebra》2018,222(12):4020-4039
We consider the finite exceptional group of Lie type (universal version) with , where and . We classify, up to conjugacy, all maximal-proper 3-local subgroups of G, that is, all 3-local which are maximal with respect to inclusion among all proper subgroups of G which are 3-local. To this end, we also determine, up to conjugacy, all elementary-abelian 3-subgroups containing , all extraspecial subgroups containing , and all cyclic groups of order 9 containing . These classifications are an important first step towards a classification of the 3-radical subgroups of G, which play a crucial role in many open conjectures in modular representation theory. 相似文献
8.
A strong -edge-coloring of a graph G is an edge-coloring with colors in which every color class is an induced matching. The strong chromatic index of , denoted by , is the minimum for which has a strong -edge-coloring. In 1985, Erd?s and Ne?et?il conjectured that , where is the maximum degree of . When is a graph with maximum degree at most 3, the conjecture was verified independently by Andersen and Horák, Qing, and Trotter. In this paper, we consider the list version of strong edge-coloring. In particular, we show that every subcubic graph has strong list-chromatic index at most 11 and every planar subcubic graph has strong list-chromatic index at most 10. 相似文献
9.
The neighbor-distinguishing total chromatic number of a graph is the smallest integer such that can be totally colored using colors with a condition that any two adjacent vertices have different sets of colors. In this paper, we give a sufficient and necessary condition for a planar graph with maximum degree 13 to have or . Precisely, we show that if is a planar graph of maximum degree 13, then ; and if and only if contains two adjacent 13-vertices. 相似文献
10.
Daniel W. Cranston William B. Kinnersley Suil O Douglas B. West 《Discrete Applied Mathematics》2013,161(13-14):1828-1836
11.
12.
13.
Bojan Vučković 《Discrete Mathematics》2017,340(12):3092-3096
A proper edge coloring is neighbor-distinguishing if any two adjacent vertices have distinct sets consisting of colors of their incident edges. The minimum number of colors needed for a neighbor-distinguishing edge coloring is the neighbor-distinguishing index, denoted by . A graph is normal if it contains no isolated edges. Let be a normal graph, and let and denote the maximum degree and the chromatic index of , respectively. We modify the previously known techniques of edge-partitioning to prove that , which implies that . This improves the result in Wang et al. (2015), which states that for any normal graph. We also prove that when , is an integer with . 相似文献
14.
Yehong Shao 《Discrete Mathematics》2018,341(12):3441-3446
Let be a graph and be its line graph. In 1969, Chartrand and Stewart proved that , where and denote the edge connectivity of and respectively. We show a similar relationship holds for the essential edge connectivity of and , written and , respectively. In this note, it is proved that if is not a complete graph and does not have a vertex of degree two, then . An immediate corollary is that for such graphs , where the vertex connectivity of the line graph
and the second iterated line graph are written as and respectively. 相似文献
15.
Let and be a sufficiently large real number. In this paper, we prove that, for almost all , the Diophantine inequality is solvable in primes . Moreover, we also investigate the problem of six primes and prove that the Diophantine inequality is solvable in primes for sufficiently large real number . 相似文献
16.
This paper considers a degree sum condition sufficient to imply the existence of vertex-disjoint cycles in a graph . For an integer , let be the smallest sum of degrees of independent vertices of . We prove that if has order at least and , with , then contains vertex-disjoint cycles. We also show that the degree sum condition on is sharp and conjecture a degree sum condition on sufficient to imply contains vertex-disjoint cycles for . 相似文献
17.
18.
19.
20.
Using properties of Gauss and Jacobi sums, we derive explicit formulas for the number of solutions to a diagonal equation of the form over a finite field of characteristic . All of the evaluations are effected in terms of parameters occurring in quadratic partitions of some powers of p. 相似文献