共查询到20条相似文献,搜索用时 484 毫秒
1.
Consider a graph consisting of a vertex set and an edge set . Let and denote the maximum degree and the chromatic number of , respectively. We say that is equitably -colorable if there exists a proper -coloring of such that the sizes of any two color classes differ by at most one. Obviously, if is equitably -colorable, then . Conversely, even if satisfies , we cannot guarantee that must be equitably -colorable. In 1994, the Equitable -Coloring Conjecture asserts that a connected graph with is equitably -colorable if is different from for all . In this paper, we give necessary conditions for a graph (not necessarily connected) with to be equitably -colorable and prove that those necessary conditions are also sufficient conditions when is a bipartite graph, or satisfies , or satisfies . 相似文献
2.
3.
Greg Malen 《Discrete Mathematics》2018,341(9):2567-2574
For any fixed graph , we prove that the topological connectivity of the graph homomorphism complex Hom() is at least , where , for the minimum degree of a vertex in a subgraph . This generalizes a theorem of C?uki? and Kozlov, in which the maximum degree was used in place of , and provides a high-dimensional analogue of the graph theoretic bound for chromatic number, , as . Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes Hom when for a fixed constant . 相似文献
4.
Let and be the adjacency matrix and the degree matrix of a graph , respectively. The matrix is called the signless Laplacian matrix of . The spectrum of the matrix is called the Q-spectrum of . A graph is said to be determined by its Q-spectrum if there is no other non-isomorphic graph with the same Q-spectrum. In this paper, we prove that all starlike trees whose maximum degree exceed are determined by their Q-spectra. 相似文献
5.
Let be a connected regular graph and , , the line, subdivision, total graphs of , respectively. In this paper, we derive formulae and lower bounds of the Kirchhoff index of , and , respectively. In particular, we give special formulae for the Kirchhoff index of , and , where is a complete graph , a regular complete bipartite graph and a cycle . 相似文献
6.
Bojan Vučković 《Discrete Mathematics》2018,341(5):1472-1478
An adjacent vertex distinguishing total -coloring of a graph is a proper total -coloring of such that any pair of adjacent vertices have different sets of colors. The minimum number needed for such a total coloring of is denoted by . In this paper we prove that if , and in general. This improves a result in Huang et al. (2012) which states that for any graph with . 相似文献
7.
The star chromatic index of a mulitigraph , denoted , is the minimum number of colors needed to properly color the edges of such that no path or cycle of length four is bi-colored. A multigraph is star-edge-colorable if . Dvo?ák et al. (2013) proved that every subcubic multigraph is star 7-edge-colorable, and conjectured that every subcubic multigraph should be star 6-edge-colorable. Kerdjoudj, Kostochka and Raspaud considered the list version of this problem for simple graphs and proved that every subcubic graph with maximum average degree less than is star list-5-edge-colorable. It is known that a graph with maximum average degree is not necessarily star 5-edge-colorable. In this paper, we prove that every subcubic multigraph with maximum average degree less than is star 5-edge-colorable. 相似文献
8.
A star edge-coloring of a graph is a proper edge coloring such that every 2-colored connected subgraph of is a path of length at most 3. For a graph , let the list star chromatic index of , , be the minimum such that for any -uniform list assignment for the set of edges, has a star edge-coloring from . Dvo?ák et al. (2013) asked whether the list star chromatic index of every subcubic graph is at most 7. In Kerdjoudj et al. (2017) we proved that it is at most 8. In this paper we consider graphs with any maximum degree, we proved that if the maximum average degree of a graph is less than (resp. 3), then (resp. ). 相似文献
9.
For a graph let , and denote its independence number, matching number, and vertex cover number, respectively. If or, equivalently, , then is a König–Egerváry graph.In this paper we give a new characterization of König–Egerváry graphs. 相似文献
10.
A strong -edge-coloring of a graph G is an edge-coloring with colors in which every color class is an induced matching. The strong chromatic index of , denoted by , is the minimum for which has a strong -edge-coloring. In 1985, Erd?s and Ne?et?il conjectured that , where is the maximum degree of . When is a graph with maximum degree at most 3, the conjecture was verified independently by Andersen and Horák, Qing, and Trotter. In this paper, we consider the list version of strong edge-coloring. In particular, we show that every subcubic graph has strong list-chromatic index at most 11 and every planar subcubic graph has strong list-chromatic index at most 10. 相似文献
11.
Two graphs are said to be -cospectral (respectively, -cospectral) if they have the same (respectively, signless) Laplacian spectra, and a graph is said to be (respectively, ) if there does not exist other non-isomorphic graph such that and are -cospectral (respectively, -cospectral). Let be the degree sequence of a graph with vertices. In this paper, we prove that except for two exceptions (respectively, the graphs with ), if is -cospectral (respectively, -cospectral) with a connected graph and , then has the same degree sequence as . A spider graph is a unicyclic graph obtained by attaching some paths to a common vertex of the cycle. As an application of our result, we show that every spider graph and its complement graph are both , which extends the corresponding results of Haemers et al. (2008), Liu et al. (2011), Zhang et al. (2009) and Yu et al. (2014). 相似文献
12.
Let denote the chromatic polynomial of a graph on vertices. The ‘shameful conjecture’ due to Bartels and Welsh states that, Let denote the expected number of colors used in a uniformly random proper -coloring of . The above inequality can be interpreted as saying that , where is the empty graph on nodes. This conjecture was proved by F.M. Dong, who in fact showed that, for all . There are examples showing that this inequality is not true for all . In this paper, we show that the above inequality holds for all , where is the largest degree of . It is also shown that the above inequality holds true for all when is a claw-free graph. 相似文献
13.
Nina Zubrilina 《Discrete Mathematics》2018,341(7):2083-2088
Given a connected graph , the edge dimension, denoted , is the least size of a set that distinguishes every pair of edges of , in the sense that the edges have pairwise different tuples of distances to the vertices of . The notation was introduced by Kelenc, Tratnik, and Yero, and in their paper they posed several questions about various properties of . In this article we answer two of these questions: we classify the graphs on vertices for which
and show that
is not bounded from above (here is the standard metric dimension of ). We also compute and . 相似文献
14.
Let be a finite group, written multiplicatively. The Davenport constant of is the smallest positive integer such that every sequence of with elements has a non-empty subsequence with product . Let be the Dihedral Group of order and be the Dicyclic Group of order . Zhuang and Gao (2005) showed that and Bass (2007) showed that . In this paper, we give explicit characterizations of all sequences of such that and is free of subsequences whose product is 1, where is equal to or for some . 相似文献
15.
Bojan Vučković 《Discrete Mathematics》2017,340(12):3092-3096
A proper edge coloring is neighbor-distinguishing if any two adjacent vertices have distinct sets consisting of colors of their incident edges. The minimum number of colors needed for a neighbor-distinguishing edge coloring is the neighbor-distinguishing index, denoted by . A graph is normal if it contains no isolated edges. Let be a normal graph, and let and denote the maximum degree and the chromatic index of , respectively. We modify the previously known techniques of edge-partitioning to prove that , which implies that . This improves the result in Wang et al. (2015), which states that for any normal graph. We also prove that when , is an integer with . 相似文献
16.
17.
18.
The decycling number of a graph is the smallest number of vertices which can be removed from so that the resultant graph contains no cycle. A decycling set containing exactly vertices of is called a -set. For any decycling set of a -regular graph , we show that , where is the cycle rank of , is the margin number of , and are, respectively, the number of components of and the number of edges in . In particular, for any -set of a 3-regular graph , we prove that , where is the Betti deficiency of . This implies that the decycling number of a 3-regular graph is . Hence for a 3-regular upper-embeddable graph , which concludes the results in [Gao et al., 2015, Wei and Li, 2013] and solves two open problems posed by Bau and Beineke (2002). Considering an algorithm by Furst et al., (1988), there exists a polynomial time algorithm to compute , the cardinality of a maximum nonseparating independent set in a -regular graph , which solves an open problem raised by Speckenmeyer (1988). As for a 4-regular graph , we show that for any -set of , there exists a spanning tree of such that the elements of are simply the leaves of with at most two exceptions providing . On the other hand, if is a loopless graph on vertices with maximum degree at most , then The above two upper bounds are tight, and this makes an extension of a result due to Punnim (2006). 相似文献
19.
20.