共查询到20条相似文献,搜索用时 78 毫秒
1.
《Discrete Mathematics》2022,345(2):112690
For a bipartite graph G with parts X and Y, an X-interval coloring is a proper edge coloring of G by integers such that the colors on the edges incident to any vertex in X form an interval. Denote by the minimum k such that G has an X-interval coloring with k colors. Casselgren and Toft (2016) [12] asked whether there is a polynomial such that if G has maximum degree at most Δ, then . In this short note, we answer this question in the affirmative; in fact, we prove that a cubic polynomial suffices. We also deduce some improved upper bounds on for bipartite graphs with small maximum degree. 相似文献
2.
Let be a polynomial ring, where is a field, and G be a simple graph on n vertices. Let be the vertex cover ideal of G. Herzog, Hibi and Ohsugi have conjectured that all powers of vertex cover ideals of chordal graph are componentwise linear. Here we establish the conjecture for the special case of trees. We also show that if G is a unicyclic vertex decomposable graph, then symbolic powers of are componentwise linear. 相似文献
3.
4.
《Discrete Mathematics》2022,345(8):112902
For a simple graph G, denote by n, , and its order, maximum degree, and chromatic index, respectively. A graph G is edge-chromatic critical if and for every proper subgraph H of G. Let G be an n-vertex connected regular class 1 graph, and let be obtained from G by splitting one vertex of G into two vertices. Hilton and Zhao in 1997 conjectured that must be edge-chromatic critical if , and they verified this when . In this paper, we prove it for . 相似文献
5.
《Discrete Mathematics》2021,344(12):112600
An -colored-mixed graph is a graph having m colors of arcs and n colors of edges. We do not allow two arcs or edges to have the same endpoints. A homomorphism from an -colored-mixed graph G to another -colored-mixed graph H is a morphism such that each edge (resp. arc) of G is mapped to an edge (resp. arc) of H of the same color (and orientation). An -colored-mixed graph T is said to be -universal if every graph in (the planar -colored-mixed graphs with girth at least g) admits a homomorphism to T.We show that planar -universal graphs do not exist for (and any value of g) and find a minimal (in the number vertices) planar -universal graphs in the other cases. 相似文献
6.
A graph G is called a pseudo-core if every endomorphism of G is either an automorphism or a colouring. A graph G is a core if every endomorphism of G is an automorphism. Let be the finite field with q elements where q is a power of an odd prime number. The quadratic forms graph, denoted by where , has all quadratic forms on as vertices and two vertices f and g are adjacent whenever or 2. We prove that every is a pseudo-core. Further, when n is even, is a core. When n is odd, is not a core. On the other hand, we completely determine the independence number of . 相似文献
7.
《Discrete Mathematics》2022,345(7):112866
Let G be a graph with n vertices. A path decomposition of G is a set of edge-disjoint paths containing all the edges of G. Let denote the minimum number of paths needed in a path decomposition of G. Gallai Conjecture asserts that if G is connected, then . If G is allowed to be disconnected, then the upper bound for was obtained by Donald [7], which was improved to independently by Dean and Kouider [6] and Yan [14]. For graphs consisting of vertex-disjoint triangles, is reached and so this bound is tight. If triangles are forbidden in G, then can be derived from the result of Harding and McGuinness [11], where g denotes the girth of G. In this paper, we also focus on triangle-free graphs and prove that , which improves the above result with . 相似文献
8.
9.
10.
11.
12.
Nursel Erey 《Journal of Pure and Applied Algebra》2019,223(7):3071-3080
Let G be a -free graph with edge ideal . We show that has linear resolution for every . Also, we show that every power of the vertex cover ideal of G has linear quotients. As a result, we describe the Castelnuovo–Mumford regularity of powers of in terms of the maximum degree of G. 相似文献
13.
14.
15.
16.
17.
18.
19.