共查询到20条相似文献,搜索用时 15 毫秒
1.
We say a graph is -colorable with of ’s and of ’s if may be partitioned into independent sets and sets whose induced graphs have maximum degree at most . The maximum average degree, , of a graph is the maximum average degree over all subgraphs of . In this note, for nonnegative integers , we show that if , then is -colorable. 相似文献
2.
Dong Ye 《Discrete Mathematics》2018,341(5):1195-1198
It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph with has a maximum matching such that any two -unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for -regular graphs with . All counterexamples for -regular graphs given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all -regular simple graphs and also -regular multigraphs with . 相似文献
3.
Gentner and Rautenbach conjectured that the size of a minimum zero forcing set in a connected graph on vertices with maximum degree is at most . We disprove this conjecture by constructing a collection of connected graphs with maximum degree 3 of arbitrarily large order having zero forcing number at least . 相似文献
4.
5.
6.
7.
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. 相似文献
8.
The star chromatic index of a mulitigraph , denoted , is the minimum number of colors needed to properly color the edges of such that no path or cycle of length four is bi-colored. A multigraph is star-edge-colorable if . Dvo?ák et al. (2013) proved that every subcubic multigraph is star 7-edge-colorable, and conjectured that every subcubic multigraph should be star 6-edge-colorable. Kerdjoudj, Kostochka and Raspaud considered the list version of this problem for simple graphs and proved that every subcubic graph with maximum average degree less than is star list-5-edge-colorable. It is known that a graph with maximum average degree is not necessarily star 5-edge-colorable. In this paper, we prove that every subcubic multigraph with maximum average degree less than is star 5-edge-colorable. 相似文献
10.
11.
12.
For integers , a -coloring of a graph is a proper coloring with at most colors such that for any vertex with degree , there are at least min different colors present at the neighborhood of . The -hued chromatic number of , , is the least integer such that a -coloring of exists. The list-hued chromatic number of is similarly defined. Thus if , then . We present examples to show that, for any sufficiently large integer , there exist graphs with maximum average degree less than 3 that cannot be -colored. We prove that, for any fraction , there exists an integer such that for each , every graph with maximum average degree is list -colorable. We present examples to show that for some there exist graphs with maximum average degree less than 4 that cannot be -hued colored with less than colors. We prove that, for any sufficiently small real number , there exists an integer such that every graph with maximum average degree satisfies . These results extend former results in Bonamy et al. (2014). 相似文献
13.
14.
15.
16.
In this paper, it is shown that an ASP exists for and . The existence of a -PDF is investigated by taking advantage of the relationship between ASPs and perfect difference families (PDFs). It is proved that a -PDF exists for and . Several recursive constructions for ASPs and PDFs are also presented. As a consequence, the existence results of an optimal -OOC is updated. 相似文献
17.
Duo-Yuan Chen Min-Jei Huang 《Journal of Mathematical Analysis and Applications》2012,389(2):1251-1258
We consider two types of Schrödinger operators and defined on , where q is an even potential that is bounded from below, A is a constant, and is a parameter. We assume that has at least two eigenvalues below its essential spectrum; and we denote by and the lowest eigenvalue and the second one, respectively. The purpose of this paper is to study the asymptotics of the gap in the limit as . 相似文献
18.
19.
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. ). 相似文献