共查询到20条相似文献,搜索用时 78 毫秒
1.
Michał Dębski 《Journal of Graph Theory》2019,90(4):523-534
The strong chromatic index of a graph , denoted by , is defined as the least number of colors in a coloring of edges of , such that each color class is an induced matching (or: if edges and have the same color, then both vertices of are not adjacent to any vertex of ). A graph is a unit distance graph in if vertices of can be uniquely identified with points in , so that is an edge of if and only if the Euclidean distance between the points identified with and is 1. We would like to find the largest possible value of , where is a unit distance graph (in and ) of maximum degree . We show that , where is a unit distance graph in of maximum degree . We also show that the maximum possible size of a strong clique in unit distance graph in is linear in and give a tighter result for unit distance graphs in the plane. 相似文献
2.
The lexicographic sum of graphs is defined as follows. Let be a graph. With each associate a graph . The lexicographic sum of the graphs over is obtained from by substituting each by . Given distinct , we have all the possible edges in the lexicographic sum between and if , and none otherwise. When all the graphs are isomorphic to some graph , the lexicographic sum of the graphs over is called the lexicographic product of by and is denoted by . We say that a graph is fractal if there exists a graph , with at least two vertices, such that . There is a simple way to construct fractal graphs. Let be a graph with at least two vertices. The graph is defined on the set of functions from to as follows. Given distinct is an edge of if is an edge of , where is the smallest integer such that . The graph is fractal because . We prove that a fractal graph is isomorphic to a lexicographic sum over an induced subgraph of , which is itself fractal. 相似文献
3.
Dennis Clemens Matthew Jenssen Yoshiharu Kohayakawa Natasha Morrison Guilherme Oliveira Mota Damian Reding Barnaby Roberts 《Journal of Graph Theory》2019,91(3):290-299
Given graphs and and a positive integer , say that is -Ramsey for , denoted , if every -coloring of the edges of contains a monochromatic copy of . The size-Ramsey number of a graph is defined to be . Answering a question of Conlon, we prove that, for every fixed , we have , where is the th power of the -vertex path (ie, the graph with vertex set and all edges such that the distance between and in is at most ). Our proof is probabilistic, but can also be made constructive. 相似文献
4.
A graph is matching-covered if every edge of is contained in a perfect matching. A matching-covered graph is strongly coverable if, for any edge of , the subgraph is still matching-covered. An edge subset of a matching-covered graph is feasible if there exist two perfect matchings and such that , and an edge subset with at least two edges is an equivalent set if a perfect matching of contains either all edges in or none of them. A strongly matchable graph does not have an equivalent set, and any two independent edges of form a feasible set. In this paper, we show that for every integer , there exist infinitely many -regular graphs of class 1 with an arbitrarily large equivalent set that is not switching-equivalent to either or , which provides a negative answer to a problem of Lukot’ka and Rollová. For a matching-covered bipartite graph , we show that has an equivalent set if and only if it has a 2-edge-cut that separates into two balanced subgraphs, and is strongly coverable if and only if every edge-cut separating into two balanced subgraphs and satisfies and . 相似文献
5.
Given two graphs and , a graph is -free if it contains no induced subgraph isomorphic to or . Let and be the path on vertices and the cycle on vertices, respectively. In this paper we show that for any -free graph it holds that , where and are the chromatic number and clique number of , respectively. Our bound is attained by several graphs, for instance, the 5-cycle, the Petersen graph, the Petersen graph with an additional universal vertex, and all -critical -free graphs other than (see Hell and Huang [Discrete Appl. Math. 216 (2017), pp. 211–232]). The new result unifies previously known results on the existence of linear -binding functions for several graph classes. Our proof is based on a novel structure theorem on -free graphs that do not contain clique cutsets. Using this structure theorem we also design a polynomial time -approximation algorithm for coloring -free graphs. Our algorithm computes a coloring with colors for any -free graph in time. 相似文献
6.
Konrad K. Dabrowski François Dross Matthew Johnson Daniël Paulusma 《Journal of Graph Theory》2019,92(4):377-393
A colouring of a graph is a function such that for every . A -regular list assignment of is a function with domain such that for every , is a subset of of size . A colouring of respects a -regular list assignment of if for every . A graph is -choosable if for every -regular list assignment of , there exists a colouring of that respects . We may also ask if for a given -regular list assignment of a given graph , there exists a colouring of that respects . This yields the -Regular List Colouring problem. For , we determine a family of classes of planar graphs, such that either -Regular List Colouring is -complete for instances with , or every is -choosable. By using known examples of non--choosable and non--choosable graphs, this enables us to classify the complexity of -Regular List Colouring restricted to planar graphs, planar bipartite graphs, planar triangle-free graphs, and planar graphs with no -cycles and no -cycles. We also classify the complexity of -Regular List Colouring and a number of related colouring problems for graphs with bounded maximum degree. 相似文献
7.
Let be a digraph which may contain loops, and let be a loopless digraph with a coloring of its arcs . An -walk of is a walk of such that is an arc of , for every . For , we say that reaches by -walks if there exists an -walk from to in . A subset is a kernel by -walks of if every vertex in reaches by -walks some vertex in , and no vertex in can reach another vertex in by -walks. A panchromatic pattern is a digraph such that every -arc-colored digraph has a kernel by -walks. In this study, we prove that every digraph is either a panchromatic pattern, or the problem of determining whether an arc-colored digraph has a kernel by -walks is -complete. 相似文献
8.
For a given -partition of the vertices of a (di)graph , we study properties of the spanning bipartite subdigraph of induced by those arcs/edges that have one end in each . We determine, for all pairs of nonnegative integers , the complexity of deciding whether has a 2-partition such that each vertex in (for ) has at least (out-)neighbours in . We prove that it is -complete to decide whether a digraph has a 2-partition such that each vertex in has an out-neighbour in and each vertex in has an in-neighbour in . The problem becomes polynomially solvable if we require to be strongly connected. We give a characterisation of the structure of -complete instances in terms of their strong component digraph. When we want higher in-degree or out-degree to/from the other set, the problem becomes -complete even for strong digraphs. A further result is that it is -complete to decide whether a given digraph has a -partition such that is strongly connected. This holds even if we require the input to be a highly connected eulerian digraph. 相似文献
9.
Arès Méroueh 《Journal of Graph Theory》2019,90(2):172-188
Let be the Ramsey number of an -uniform loose cycle of length versus an -uniform clique of order . Kostochka et al. showed that for each fixed , the order of magnitude of is up to a polylogarithmic factor in . They conjectured that for each we have . We prove that , and more generally for every that . We also prove that for every and , if is odd, which improves upon the result of Collier-Cartaino et al. who proved that for every and we have . 相似文献
10.
Bae and Park found an upper bound on the arc index of prime links in terms of the minimal crossing number. In this paper, we extend the definition of the arc presentation to spatial graphs and find an upper bound on the arc index of any spatial graph as where is the minimal crossing number of , is the number of edges, and is the number of bouquet cut-components. This upper bound is lowest possible. 相似文献
11.
Allan Lo 《Journal of Graph Theory》2019,90(3):416-442
Let be an edge-coloured graph. The minimum colour degree of is the largest integer such that, for every vertex , there are at least distinct colours on edges incident to . We say that is properly coloured if no two adjacent edges have the same colour. In this paper, we show that, for any and large, every edge-coloured graph with contains a properly coloured cycle of length at least . 相似文献
12.
Let be a -partite -graph with vertices in each partition class, and let denote the minimum codegree of . We characterize those with and with no perfect matching. As a consequence, we give an affirmative answer to the following question of Rödl and Ruciński: if is even or , does imply that has a perfect matching? We also give an example indicating that it is not sufficient to impose this degree bound on only two types of -sets. 相似文献
13.
Amin Bahmanian 《Journal of Graph Theory》2019,90(4):547-560
Let be the collection of all -subsets of an -set . Given a coloring (partition) of a set , we are interested in finding conditions under which this coloring is extendible to a coloring of so that the number of times each element of appears in each color class (all sets of the same color) is the same number . The case was studied by Sylvester in the 18th century and remained open until the 1970s. The case is extensively studied in the literature and is closely related to completing partial symmetric Latin squares. For , we settle the cases , and completely. Moreover, we make partial progress toward solving the case where . These results can be seen as extensions of the famous Baranyai’s theorem, and make progress toward settling a 40-year-old problem posed by Cameron. 相似文献
14.
The - deck of a graph is its multiset of subgraphs induced by vertices; we study what can be deduced about a graph from its -deck. We strengthen a result of Manvel by proving for that when is large enough ( suffices), the -deck determines whether an -vertex graph is connected ( suffices when , and cannot suffice). The reconstructibility of a graph with vertices is the largest such that is determined by its -deck. We generalize a result of Bollobás by showing for almost all graphs. As an upper bound on , we have . More generally, we compute whenever , which involves extending a result of Stanley. Finally, we show that a complete -partite graph is reconstructible from its -deck. 相似文献
15.
Amelia Taylor 《Journal of Graph Theory》2019,90(3):231-266
A graph has a -decomposition if its edge set can be partitioned into cycles of length . We show that if , then has a -decomposition, and if , then has a -decomposition, where and (we assume is large and satisfies necessary divisibility conditions). These minimum degree bounds are best possible and provide exact versions of asymptotic results obtained by Barber, Kühn, Lo and Osthus. In the process, we obtain asymptotic versions of these results when is bipartite or satisfies certain expansion properties. 相似文献
16.
We present a construction of two infinite graphs and , and of an infinite set of graphs such that is an antichain with respect to the immersion relation and, for each graph in , both and are subgraphs of , but no graph properly immersed in admits an immersion of and of . This shows that the class of infinite graphs ordered by the immersion relation does not have the finite intertwine property. 相似文献
17.
Dániel Gerbner Balázs Keszegh Abhishek Methuku Balázs Patkós Máté Vizer 《Journal of Graph Theory》2019,91(1):88-97
Erdős and Moser raised the question of determining the maximum number of maximal cliques or, equivalently, the maximum number of maximal independent sets in a graph on vertices. Since then there has been a lot of research along these lines. A -dominating independent set is an independent set such that every vertex not contained in has at least neighbors in . Let denote the maximum number of -dominating independent sets in a graph on vertices, and let . Nagy initiated the study of . In this study, we disprove a conjecture of Nagy using a graph product construction and prove that for any even we have We also prove that for any we have improving the upper bound of Nagy. 相似文献
18.
The size Ramsey number of two graphs and is the smallest integer such that there exists a graph on edges with the property that every red-blue colouring of the edges of yields a red copy of or a blue copy of . In 1981, Erdős observed that and he conjectured that this upper bound on is sharp. In 1983, Faudree and Sheehan extended this conjecture as follows: They proved the case . In 2001, Pikhurko showed that this conjecture is not true for and , by disproving the mentioned conjecture of Erdős. Here, we prove Faudree and Sheehan's conjecture for a given and . 相似文献
19.
A graph is called -connected if is -edge-connected and is -edge-connected for every vertex . The study of -connected graphs is motivated by a theorem of Thomassen [J. Combin. Theory Ser. A 110 (2015), pp. 67–78] (that was a conjecture of Frank [SIAM J. Discrete Math. 5 (1992), no. 1, pp. 25–53]), which states that a graph has a -vertex-connected orientation if and only if it is (2,2)-connected. In this paper, we provide a construction of the family of -connected graphs for even, which generalizes the construction given by Jordán [J. Graph Theory 52 (2006), pp. 217–229] for (2,2)-connected graphs. We also solve the corresponding connectivity augmentation problem: given a graph and an integer , what is the minimum number of edges to be added to make -connected. Both these results are based on a new splitting-off theorem for -connected graphs. 相似文献
20.
Bart Litjens 《Journal of Graph Theory》2019,91(2):174-191
Let be a multigraph with for each vertex a cyclic order of the edges incident with it. For , let be the dihedral group of order . Define . Goodall et al in 2016 asked whether admits a nowhere-identity -flow if and only if it admits a nowhere-identity -flow with (a “nowhere-identity dihedral -flow”). We give counterexamples to this statement and provide general obstructions. Furthermore, the complexity of deciding the existence of nowhere-identity -flows is discussed. Lastly, graphs in which the equivalence of the existence of flows as above is true are described. We focus particularly on cubic graphs. 相似文献