共查询到20条相似文献,搜索用时 31 毫秒
1.
Michael Savery 《Journal of Graph Theory》2022,99(1):152-161
A graph is Ramsey for a graph if every colouring of the edges of in two colours contains a monochromatic copy of . Two graphs and are Ramsey equivalent if any graph is Ramsey for if and only if it is Ramsey for . A graph parameter is Ramsey distinguishing if implies that and are not Ramsey equivalent. In this paper we show that the chromatic number is a Ramsey distinguishing parameter. We also extend this to the multicolour case and use a similar idea to find another graph parameter which is Ramsey distinguishing. 相似文献
2.
In 1990, Albertson, Berman, Hutchinson, and Thomassen proved a theorem which gives a minimum degree condition for the existence of a spanning tree with no vertices of degree 2. Such a spanning tree is called a homeomorphically irreducible spanning tree (HIST). In this paper, we prove that every graph of order () contains a HIST if for any nonadjacent vertices and . The degree sum condition is best possible. 相似文献
3.
Nick Brettell Jake Horsfield Andrea Munaro Giacomo Paesani Daniël Paulusma 《Journal of Graph Theory》2022,99(1):117-151
A large number of -hard graph problems are solvable in time when parameterized by some width parameter. Hence, when solving problems on special graph classes, it is helpful to know if the graph class under consideration has bounded width. In this paper we consider maximum-induced matching width (mim-width), a particularly general width parameter that has a number of algorithmic applications whenever a decomposition is “quickly computable” for the graph class under consideration. We start by extending the toolkit for proving (un)boundedness of mim-width of graph classes. By combining our new techniques with known ones we then initiate a systematic study into bounding mim-width from the perspective of hereditary graph classes, and make a comparison with clique-width, a more restrictive width parameter that has been well studied. We prove that for a given graph , the class of -free graphs has bounded mim-width if and only if it has bounded clique-width. We show that the same is not true for -free graphs. We identify several general classes of -free graphs having unbounded clique-width, but bounded mim-width; moreover, we show that a branch decomposition of constant mim-width can be found in polynomial time for these classes. Hence, these results have algorithmic implications: when the input is restricted to such a class of -free graphs, many problems become polynomial-time solvable, including classical problems, such as - Colouring and Independent Set , domination-type problems known as Locally Checkable Vertex Subset and Vertex Partitioning (LC-VSVP) problems, and distance versions of LC-VSVP problems, to name just a few. We also prove a number of new results showing that, for certain and , the class of -free graphs has unbounded mim-width. Boundedness of clique-width implies boundedness of mim-width. By combining our results with the known bounded cases for clique-width, we present summary theorems of the current state of the art for the boundedness of mim-width for -free graphs. In particular, we classify the mim-width of -free graphs for all pairs with . When and are connected graphs, we classify all pairs except for one remaining infinite family and a few isolated cases. 相似文献
4.
Dingding Dong 《Journal of Graph Theory》2021,96(1):160-166
In connection with his solution of the Sensitivity Conjecture, Hao Huang (arXiv: 1907.00847, 2019) asked the following question: Given a graph with high symmetry, what can we say about the smallest maximum degree of induced subgraphs of with vertices, where denotes the size of the largest independent set in ? We study this question for , the ‐dimensional Hamming graph over an alphabet of size . Generalizing a construction by Chung et al. (JCT‐A, 1988), we prove that has an induced subgraph with more than vertices and maximum degree at most . Chung et al. proved this statement for (the ‐dimensional cube). 相似文献
5.
S. Akbari M. Dalirrooyfard K. Ehsani K. Ozeki R. Sherkati 《Journal of Graph Theory》2020,93(4):483-502
Let be a graph and be a mapping. The graph is said to be - avoiding if there exists an orientation of such that for every , where denotes the out-degree of in the directed graph with respect to . In this paper it is shown that if is bipartite and for every , then is -avoiding. The bound is best possible. For every graph , we conjecture that if for every , then is -avoiding. We also argue about this conjecture for the best possibility of the conditions and also show some partial solutions. 相似文献
6.
7.
Daniel Soltész 《Journal of Graph Theory》2020,93(3):350-362
We say that two graphs on the same vertex set are -creating if the union of the two graphs contains as a subgraph. Let be the maximum number of pairwise -creating Hamiltonian paths of the complete graph . The behavior of is much better understood than the behavior of , the former is an exponential function of whereas the latter is larger than exponential, for every fixed . We study for fixed and tending to infinity. The only nontrivial upper bound on was proved by Cohen, Fachini, and Körner in the case of : In this paper, we generalize their method to prove that for every , and a similar, slightly better upper bound holds when is odd. Our proof uses constructions of bipartite, regular, -free graphs with many edges given in papers by Reiman, Benson, Lazebnik, Ustimenko, and Woldar. 相似文献
8.
Let be a graph whose largest independent set has size . A permutation of is an independent set permutation of if where is the number of independent sets of size in . In 1987 Alavi, Malde, Schwenk, and Erd?s proved that every permutation of is an independent set permutation of some graph with , that is, with the largest independent set having size . They raised the question of determining, for each , the smallest number such that every permutation of is an independent set permutation of some graph with and with at most vertices, and they gave an upper bound on of roughly . Here we settle the question, determining , and make progress on a related question, that of determining the smallest order such that every permutation of is the unique independent set permutation of some graph of at most that order. More generally we consider an extension of independent set permutations to weak orders, and extend Alavi et al.'s main result to show that every weak order on can be realized by the independent set sequence of some graph with and with at most vertices. Alavi et al. also considered matching permutations, defined analogously to independent set permutations. They observed that not every permutation of is a matching permutation of some graph with the largest matching having size , putting an upper bound of on the number of matching permutations of . Confirming their speculation that this upper bound is not tight, we improve it to . 相似文献
9.
Martin Rolek 《Journal of Graph Theory》2020,94(2):206-223
We prove the extremal function for minors, where denotes the complete graph with two edges removed. In particular, we show that any graph with vertices and at least edges either contains a minor or is isomorphic to a graph obtained from disjoint copies of and by identifying cliques of size 5. We utilize computer assistance to prove one of our lemmas. 相似文献
10.
A conjecture of Chung and Graham states that every -free graph on vertices contains a vertex set of size that spans at most edges. We make the first step toward this conjecture by showing that it holds for all regular graphs. 相似文献
11.
Every generic linear functional on a convex polytope induces an orientation on the graph of . From the resulting directed graph one can define a notion of -arborescence and -monotone path on , as well as a natural graph structure on the vertex set of -monotone paths. These concepts are important in geometric combinatorics and optimization. This paper bounds the number of -arborescences, the number of -monotone paths, and the diameter of the graph of -monotone paths for polytopes in terms of their dimension and number of vertices or facets. 相似文献
12.
We introduce a new approach and prove that the maximum number of triangles in a -free graph on vertices is at most We show a connection to -uniform hypergraphs without (Berge) cycles of length less than six, and estimate their maximum possible size. Using our approach, we also (slightly) improve the previous estimate on the maximum size of an induced--free and -free graph. 相似文献
13.
We construct highly edge-connected -regular graphs of even order which do not contain pairwise disjoint perfect matchings. When is a multiple of 4, the result solves a problem of Thomassen [4]. 相似文献
14.
Let be a ‐critical graph with . Erd?s and Gallai proved that and the bound was obtained by Erd?s, Hajnal, and Moon. We give here the sharp combined bound and find all graphs with equality. 相似文献
15.
The paper deals with partitions of hypergraphs into induced subhypergraphs satisfying constraints on their degeneracy. Our hypergraphs may have multiple edges, but no loops. Given a hypergraph and a sequence of vertex functions such that for all , we want to find a sequence of vertex disjoint induced subhypergraphs containing all vertices of such that each hypergraph is strictly ‐degenerate, that is, for every nonempty subhypergraph there is a vertex such that . Our main result in this paper says that such a sequence of hypergraphs exists if and only if is not a so‐called hard pair. Hard pairs form a recursively defined family of configurations, obtained from three basic types of configurations by the operation of merging a vertex. Our main result has several interesting applications related to generalized hypergraph coloring problems. 相似文献
16.
17.
We study the maximum number of copies of a graph in graphs with a given number of vertices and edges. We show that for any fixed graph is asymptotically realized by the quasi‐clique provided that the edge density is sufficiently large. We also investigate a variant of this problem, when the host graph is bipartite. 相似文献
18.
For wide classes of locally convex spaces, in particular, for the space of continuous real‐valued functions on a Tychonoff space X equipped with the pointwise topology, we characterize the existence of a fundamental bounded resolution (i.e., an increasing family of bounded sets indexed by the irrationals which swallows the bounded sets). These facts together with some results from Grothendieck's theory of ‐spaces have led us to introduce quasi‐ ‐spaces, a class of locally convex spaces containing ‐spaces that preserves subspaces, countable direct sums and countable products. Regular ‐spaces as well as their strong duals are quasi‐ ‐spaces. Hence the space of distributions provides a concrete example of a quasi‐ ‐space not being a ‐space. We show that has a fundamental bounded resolution if and only if is a quasi‐ ‐space if and only if the strong dual of is a quasi‐ ‐space if and only if X is countable. If X is metrizable, then is a quasi‐ ‐space if and only if X is a σ‐compact Polish space. 相似文献
19.
20.
Tristram Bogart John Goodrick Danny Nguyen Kevin Woods 《Mathematical Logic Quarterly》2019,65(2):237-250
We consider an expansion of Presburger arithmetic which allows multiplication by k parameters . A formula in this language defines a parametric set as varies in , and we examine the counting function as a function of t . For a single parameter, it is known that can be expressed as an eventual quasi‐polynomial (there is a period m such that, for sufficiently large t, the function is polynomial on each of the residue classes mod m). We show that such a nice expression is impossible with 2 or more parameters. Indeed (assuming ) we construct a parametric set such that is not even polynomial‐time computable on input . In contrast, for parametric sets with arbitrarily many parameters, defined in a similar language without the ordering relation, we show that is always polynomial‐time computable in the size of t , and in fact can be represented using the gcd and similar functions. 相似文献