共查询到20条相似文献,搜索用时 0 毫秒
1.
2.
Acta Mathematicae Applicatae Sinica, English Series - A k-coloring of a graph G is a mapping c: V(G) → {1, 2, ?, k}. The coloring c is called injective if any two vertices have a common... 相似文献
3.
The vertex-arboricity a(G) of a graph G is the minimum number of colors required for a vertex coloring of G such that no cycle is monochromatic. The list vertex-arboricity al(G) is the list-coloring version of this concept. In this paper, we prove that every planar graph G without intersecting 5-cycles has al(G) ≤ 2.This extends a result by Raspaud and Wang [On the vertex-arboricity of planar graphs, European J. Combin.29(2008), 1064-1075] that every planar graph G without 5-cycles has a(G) ≤ 2. 相似文献
4.
Acta Mathematicae Applicatae Sinica, English Series - A 2-distance coloring of a graph is a coloring of the vertices such that two vertices at distance at most two receive distinct colors. A list... 相似文献
5.
6.
A clique-colouring of a graph G is a colouring of the vertices of G so that no maximal clique of size at least two is monochromatic. The clique-hypergraph, ${\mathcal{H}(G)}$ , of a graph G has V(G) as its set of vertices and the maximal cliques of G as its hyperedges. A vertex-colouring of ${\mathcal{H}(G)}$ is a clique-colouring of G. Determining the clique-chromatic number, the least number of colours for which a graph G admits a clique-colouring, is known to be NP-hard. In this work, we establish that the clique-chromatic number of powers of cycles is equal to two, except for odd cycles of size at least five, that need three colours. For odd-seq circulant graphs, we show that their clique-chromatic number is at most four, and determine the cases when it is equal to two. Similar bounds for the chromatic number of these graphs are also obtained. 相似文献
7.
In this paper, we find out the achromatic number of Central graph of Banana Tree, Helm Graph and Web Graph. 相似文献
8.
School timetabling problems containing multiple period lessons are formulated in terms of the colouring of composite graphs. Several approximate colouring algorithms are proposed and compared empirically. 相似文献
9.
In this paper we discuss the achromatic coloring of graphs, and the achromatic number of central graph of Wheel graphs and Gear graphs and generalize the achromatic colouring of central graphs. 相似文献
10.
11.
Given a Steiner triple system , we say that a cubic graph G is -colourable if its edges can be coloured by points of in such way that the colours of any three edges meeting at a vertex form a triple of . We prove that there is Steiner triple system of order 21 which is universal in the sense that every simple cubic graph is -colourable. This improves the result of Grannell et al. [J. Graph Theory 46 (2004), 15–24] who found a similar system of order 381. On the other hand, it is known that any universal Steiner triple
system must have order at least 13, and it has been conjectured that this bound is sharp (Holroyd and Škoviera [J. Combin.
Theory Ser. B 91 (2004), 57–66]).
Research partially supported by APVT, project 51-027604.
Research partially supported by VEGA, grant 1/3022/06. 相似文献
12.
Michael Capalbo 《Combinatorica》2002,22(3):345-359
For all positive integers N and k, let denote the family of planar graphs on N or fewer vertices, and with maximum degree k. For all positive integers N and k, we construct a -universal graph of size . This construction answers with an explicit construction the previously open question of the existence of such a graph.
Received July 8, 1998
RID="*"
ID="*" Supported by NSF grant CCR98210-58 and ARO grant DAAH04-96-1-0013. 相似文献
13.
Order - Let κ be a successor cardinal. We prove that consistently every bipartite graph of size κ+ × κ+ contains either an independent set or a clique of size τ ×... 相似文献
14.
We describe several classes of finite, planar Toeplitz graphs and present results on their chromatic number. We then turn to counting maximal independent sets in these graphs and determine recurrence equations and generating functions for some special cases. 相似文献
15.
Tomasz Bartnicki Bartłomiej Bosek Sebastian Czerwiński Jarosław Grytczuk Grzegorz Matecki Wiktor Żelazny 《Graphs and Combinatorics》2014,30(5):1087-1098
An additive coloring of a graph G is an assignment of positive integers \({\{1,2,\ldots ,k\}}\) to the vertices of G such that for every two adjacent vertices the sums of numbers assigned to their neighbors are different. The minimum number k for which there exists an additive coloring of G is denoted by \({\eta (G)}\) . We prove that \({\eta (G) \, \leqslant \, 468}\) for every planar graph G. This improves a previous bound \({\eta (G) \, \leqslant \, 5544}\) due to Norin. The proof uses Combinatorial Nullstellensatz and the coloring number of planar hypergraphs. We also demonstrate that \({\eta (G) \, \leqslant \, 36}\) for 3-colorable planar graphs, and \({\eta (G) \, \leqslant \, 4}\) for every planar graph of girth at least 13. In a group theoretic version of the problem we show that for each \({r \, \geqslant \, 2}\) there is an r-chromatic graph G r with no additive coloring by elements of any abelian group of order r. 相似文献
16.
Adam Berliner Ulrike Bostelmann Richard A. Brualdi Louis Deaett 《Graphs and Combinatorics》2006,22(2):173-183
Let G=(V,E) be a graph with n vertices and e edges. The sum choice number of G is the smallest integer p such that there exist list sizes (f(v):v ∈ V) whose sum is p for which G has a proper coloring no matter which color lists of size f(v) are assigned to the vertices v. The sum choice number is bounded above by n+e. If the sum choice number of G equals n+e, then G is sum choice greedy. Complete graphs Kn are sum choice greedy as are trees. Based on a simple, but powerful, lemma we show that a graph each of whose blocks is sum
choice greedy is also sum choice greedy. We also determine the sum choice number of K2,n, and we show that every tree on n vertices can be obtained from Kn by consecutively deleting single edges where all intermediate graphs are sc-greedy. 相似文献
17.
In McDiarmid, B. Reed, A. Schrijver, and B. Shepherd (Univ. of Waterloo Tech. Rep., 1990) a polynomial-time algorithm is given for the problem of finding a minimum cost circuit without chords (induced circuit) traversing two given vertices of a planar graph. The algorithm is based on the ellipsoid method. Here we give an O(n2) combinatorial algorithm to determine whether two nodes in a planar graph lie on an induced circuit. We also give a min-max relation for the problem of finding a maximum number of paths connecting two given vertices in a planar graph so that each pair of these paths forms an induced circuit. 相似文献
18.
Stefan Felsner 《Order》2003,20(2):135-150
Schnyder labelings are known to have close links to order dimension and drawings of planar graphs. It was observed by Ezra
Miller that geodesic embeddings of planar graphs are another class of combinatorial or geometric objects closely linked to
Schnyder labelings. We aim to contribute to a better understanding of the connections between these objects. In this article
we prove
• a characterization of 3-connected planar graphs as those graphs admitting rigid geodesic embeddings,
• a bijection between Schnyder labelings and rigid geodesic embeddings,
• a strong version of the Brightwell–Trotter theorem.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
19.
A graph is a strict-quasi parity (SQP) graph if every induced subgraph that is not a clique contains a pair of vertices with
no odd chordless path between them (an “even pair”). We present an O(n
3) algorithm for recognizing planar strict quasi-parity graphs, based on Wen-Lian Hsu's decomposition of planar (perfect) graphs
and on the (non-algorithmic) characterization of planar minimal non-SQP graphs given in [9].
Received: September 21, 1998 Final version received: May 9, 2000 相似文献
20.
An even pair in a graph is a pair of vertices such that every chordless path between them has even length. A graph is called perfectly contractile when every induced subgraph can be transformed into a clique through a sequence of even-pair contractions. In this paper we characterize the planar graphs that are perfectly contractile by determining all the minimal forbidden subgraphs. We give a polynomial algorithm for the recognition of perfectly contractile planar graphs. 相似文献