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 相似文献
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. 相似文献
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. 相似文献
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. 相似文献
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 相似文献
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. 相似文献
Let denote that any -coloring of contains a monochromatic . The degree Ramsey number of a graph , denoted by , is . We consider degree Ramsey numbers where is a fixed even cycle. Kinnersley, Milans, and West showed that , and Kang and Perarnau showed that . Our main result is that and . Additionally, we substantially improve the lower bound for for general . 相似文献