共查询到20条相似文献,搜索用时 375 毫秒
1.
Daniel W. Cranston William B. Kinnersley Suil O Douglas B. West 《Discrete Applied Mathematics》2013,161(13-14):1828-1836
2.
3.
Aysel Erey 《Discrete Mathematics》2018,341(5):1419-1431
4.
Greg Malen 《Discrete Mathematics》2018,341(9):2567-2574
For any fixed graph , we prove that the topological connectivity of the graph homomorphism complex Hom() is at least , where , for the minimum degree of a vertex in a subgraph . This generalizes a theorem of C?uki? and Kozlov, in which the maximum degree was used in place of , and provides a high-dimensional analogue of the graph theoretic bound for chromatic number, , as . Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes Hom when for a fixed constant . 相似文献
5.
Haiyang Zhu Lianying Miao Sheng Chen Xinzhong Lü Wenyao Song 《Discrete Mathematics》2018,341(8):2211-2219
Let be the set of all positive integers. A list assignment of a graph is a function that assigns each vertex a list for all . We say that is --choosable if there exists a function such that for all , if and are adjacent, and if and are at distance 2. The list--labeling number of is the minimum such that for every list assignment , is --choosable. We prove that if is a planar graph with girth
and its maximum degree is large enough, then . There are graphs with large enough and having . 相似文献
6.
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. 相似文献
7.
8.
Jeong-Hyun Kang 《Discrete Mathematics》2018,341(1):96-103
The vertices of Kneser graph are the subsets of of cardinality , two vertices are adjacent if and only if they are disjoint. The square of a graph is defined on the vertex set of with two vertices adjacent if their distance in is at most 2. Z. Füredi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when . It is believed that where is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: for 1 (Kim and Park, 2014) and for (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to , where is a constant in , depending on . 相似文献
9.
In this paper, we employed lattice model to describe the three internally vertex-disjoint paths that span the vertex set of the generalized Petersen graph . We showed that the is 3-spanning connected for odd . Based on the lattice model, five amalgamated and one extension mechanisms are introduced to recursively establish the 3-spanning connectivity of the . In each amalgamated mechanism, a particular lattice trail was amalgamated with the lattice trails that was dismembered, transferred, or extended from parts of the lattice trails for , where a lattice tail is a trail in the lattice model that represents a path in . 相似文献
10.
11.
A matching in a 3-uniform hypergraph is a set of pairwise disjoint edges. A -matching in a 3-uniform hypergraph is a matching of size . Let be a partition of vertices such that and . Denote by the 3-uniform hypergraph with vertex set consisting of all those edges which contain at least two vertices of . Let be a 3-uniform hypergraph of order such that for any two adjacent vertices . In this paper, we prove contains a -matching if and only if is not a subgraph of . 相似文献
12.
A graph is minimally -tough if the toughness of is and the deletion of any edge from decreases the toughness. Kriesell conjectured that for every minimally -tough graph the minimum degree . We show that in every minimally -tough graph . We also prove that every minimally -tough, claw-free graph is a cycle. On the other hand, we show that for every positive rational number any graph can be embedded as an induced subgraph into a minimally -tough graph. 相似文献
13.
14.
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 . 相似文献
15.
16.
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. 相似文献
17.
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. 相似文献
18.
19.
Let and be two positive integers such that and . A graph is an -parity factor of a graph if is a spanning subgraph of and for all vertices , and . In this paper we prove that every connected graph with vertices has an -parity factor if is even, , and for any two nonadjacent vertices , . This extends an earlier result of Nishimura (1992) and strengthens a result of Cai and Li (1998). 相似文献
20.
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. ). 相似文献