共查询到20条相似文献,搜索用时 93 毫秒
1.
2.
A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define for and We say that is -colorable if has a 2-coloring such that is an empty set or the induced subgraph has the maximum degree at most for and Let be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether is -colorable is NP-complete for every positive integer Moreover, we construct non--colorable planar graphs without 4-cycles and 5-cycles for every positive integer In contrast, we prove that is -colorable where and 相似文献
3.
For bipartite graphs , the bipartite Ramsey number is the least positive integer so that any coloring of the edges of with colors will result in a copy of in the th color for some . In this paper, our main focus will be to bound the following numbers: and for all for and for Furthermore, we will also show that these mentioned bounds are generally better than the bounds obtained by using the best known Zarankiewicz-type result. 相似文献
4.
5.
6.
7.
8.
9.
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. 相似文献
10.
Vahan V. Mkrtchyan Samvel S. Petrosyan Gagik N. Vardanyan 《Discrete Mathematics》2010,310(10-11):1588-1613
For and a cubic graph let denote the maximum number of edges that can be covered by matchings. We show that and . Moreover, it turns out that . 相似文献
11.
12.
In a pursuit evasion game on a finite, simple, undirected, and connected graph , a first player visits vertices of , where is in the closed neighborhood of for every , and a second player probes arbitrary vertices of , and learns whether or not the distance between and is at most the distance between and . Up to what distance can the second player determine the position of the first? For trees of bounded maximum degree and grids, we show that is bounded by a constant. We conjecture that for every graph of order , and show that if may differ from only if is a multiple of some sufficiently large integer. 相似文献
13.
14.
15.
16.
The conservative number of a graph is the minimum positive integer , such that admits an orientation and a labeling of its edges by distinct integers in , such that at each vertex of degree at least three, the sum of the labels on the in-coming edges is equal to the sum of the labels on the out-going edges. A graph is conservative if . It is worth noting that determining whether certain biregular graphs are conservative is equivalent to find integer Heffter arrays.In this work we show that the conservative number of a galaxy (a disjoint union of stars) of size is for , , and otherwise. Consequently, given positive integers , , …, with for , we construct a cyclic -cycle system of infinitely many circulant graphs, generalizing a result of Bryant, Gavlas and Ling (2003). In particular, it allows us to construct a cyclic -cycle system of the complete graph , where . Also, we prove necessary and sufficient conditions for the existence of a cyclic -cycle system of , where is a 1-factor. Furthermore, we give a sufficient condition for a subset of to be sequenceable. 相似文献
17.
The Catalan numbers occur in various counting problems in combinatorics. This paper reveals a connection between the Catalan numbers and list colouring of graphs. Assume is a graph and is a mapping. For a nonnegative integer , let be the extension of to the graph for which for each vertex of . Let be the minimum such that is not -choosable and be the minimum such that is not -paintable. We study the parameter and for arbitrary mappings . For , an -dominated path ending at is a monotonic path of the grid from to such that each vertex on satisfies . Let be the number of -dominated paths ending at . By this definition, the Catalan number equals . This paper proves that if has vertices and , then , where and for . Therefore, if , then equals the Catalan number . We also show that if is the disjoint union of graphs and , then and . This generalizes a result in Carraher et al. (2014), where the case each is a copy of is considered. 相似文献
18.
19.
Susan A. van Aardt Christoph Brause Alewyn P. Burger Marietjie Frick Arnfried Kemnitz Ingo Schiermeyer 《Discrete Mathematics》2017,340(11):2673-2677
An edge-coloured graph is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a connected graph denoted by , is the smallest number of colours that are needed in order to make properly connected. Our main result is the following: Let be a connected graph of order and . If , then except when and where and 相似文献