共查询到17条相似文献,搜索用时 15 毫秒
1.
2.
主要围绕Steinberg提出猜想:每个不包含4-圈和5-圈的平面图都是3-可染色的,对一些平面图类展开研究,提出要解决的问题:不包含{4,8,9}-圈的平面图是3-可染的.现从四个方面:不包含{4,8,9}-圈的平面图G的一些结构性质;不包含{4,8,9}-圈的平面图G中内部非分离6-圈的性质;不包含{4,8,9}-圈的平面图G不包含内部的6-面;f0不是一个6-面来证明结论,即不包含{4,8,9}-圈的平面图是3-可染的. 相似文献
3.
朱晓颖 《纯粹数学与应用数学》2013,(6):609-614
寻找平面图是3-或者4-可选择的充分条件是图的染色理论中一个重要研究课题,本文研究了围长至少是4的特殊平面图的选择数,通过权转移的方法证明了每个围长至少是4且不合8-圈,9-圈和10-圈的平面图是3-可选择的. 相似文献
4.
Cycle base theory of a graph has been well studied in abstract mathematical field such matroid theory as Whitney and Tutte did and found many applications in pratical uses such as electric circuit theory and structure analysis, etc. In this paper graph embedding theory is used to investigate cycle base structures of a 2-(edge)-connected graph on the sphere and the projective plane and it is shown that short cycles do generate the cycle spaces in the case of ““““small face-embeddings““““. As applications the authors find the exact formulae for the minimum lengthes of cycle bases of some types of graphs and present several known results. Infinite examples shows that the conditions in their main results are best possible and there are many 3-connected planar graphs whose minimum cycle bases can not be determined by the planar formulae but may be located by re-embedding them into the projective plane. 相似文献
5.
6.
7.
完全三部图K(n_1,n_2,n_3)的色唯一性 总被引:4,自引:0,他引:4
设G是简单图,用P(G,λ)表示图G的色多项式.若对任意简单图H使P(H,λ)=P(G,λ),都有H与G同构,则称G是色唯一图.令K(n 相似文献
8.
Bao-gang Xu 《应用数学学报(英文版)》2014,30(3):765-772
In 2003, Borodin and Raspaud proved that if G is a plane graph without 5-circuits and without triangles of distance less than four, then G is 3-colorable. In this paper, we prove that if G is a plane graph without 5- and 6-circuits and without triangles of distance less than 2, then G is 3-colorable. 相似文献
9.
ON 3-CHOOSABILITY OF PLANE GRAPHS WITHOUT 6-,7- AND 9-CYCLES 总被引:2,自引:0,他引:2
ZhangHaihui XuBaogang 《高校应用数学学报(英文版)》2004,19(1):109-115
The choice number of a graph G,denoted by X1(G),is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. In this paper,it is showed that X1 (G)≤3 for each plane graph of girth not less than 4 which contains no 6-, 7- and 9-cycles. 相似文献
10.
《Discrete Mathematics》2022,345(9):112942
A graph G is k-degenerate if every subgraph of G has a vertex with degree at most k. Using the Euler's formula, one can obtain that planar graphs without 3-cycles are 3-degenerate. Wang and Lih, and Fijav? et al. proved the analogue results for planar graphs without 5-cycles and planar graphs without 6-cycles, respectively. Recently, Liu et al. showed that planar graphs without 3-cycles adjacent to 5-cycles are 3-degenerate. In this work, we generalized all aforementioned results by showing that planar graphs without mutually adjacent 3-,5-, and 6-cycles are 3-degenerate. A graph G without mutually adjacent 3-,5-, and 6-cycles means that G cannot contain three graphs, say , and , where is a 3-cycle, is a 5-cycle, and is a 6-cycle such that each pair of , and are adjacent. As an immediate consequence, we have that every planar graph without mutually adjacent 3-,5-, and 6-cycles is DP-4-colorable. This consequence also generalizes the result by Chen et al that planar graphs without 5-cycles adjacent to 6-cycles are DP-4-colorable. 相似文献
11.
It is known that planar graphs without cycles of length 4, i, j, or 9 with 4<i<j<9, except that i=7 and j=8, are 3-choosable. This paper proves that planar graphs without cycles of length 4, 7, 8, or 9 are also 3-choosable. 相似文献
12.
阶为$n$的图$G$的圈长分布是序列($c_1,c_2,\ldots,c_n$), 其中$c_i$是图$G$中长为$i$的圈数.本文得到如下结果: 设$A\subseteq E(K_{n,n+7})$,在以下情况, 图 $G$ 由其圈长分布唯一确定.(1) $G=K_{n,n+7}$(n\geq10)$;(2) $G=K_{n,n+7}-A$ $(|A|=1,n\geq12)$;(3)$G=K_{n,n+7}-A$(|A|=2,n\geq14)$;(4)$G=K_{n,n+7}-A$ $(|A|=3 相似文献
13.
We complete the determination of the maximum sizes of (k,n)-arcs,n≤12,in the projective Hjelmslev planes over the two (proper) chain rings Z 9=Z/9Z and S 3=F 3 [X]/(X 2) of order 9 by resolving the hitherto open cases n=6 and n=7.Parts of our proofs rely on decidedly geometric properties of the planes such as Desargues’ theorem and the existence of certain subplanes. 相似文献
14.
The second author's (B.A.R.) ω, Δ, χ conjecture proposes that every graph satisfies . In this article, we prove that the conjecture holds for all claw‐free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way, we discuss a stronger local conjecture, and prove that it holds for claw‐free graphs with a three‐colorable complement. To prove our results, we introduce a very useful χ‐preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so‐called skeletal graphs. 相似文献
15.
In this paper, we mainly prove that planar graphs without 4-, 7- and 9-cycles are 3-colorable. 相似文献
16.
17.
An m‐cycle system (S,C) of order n is said to be {2,3}‐perfect provided each pair of vertices is connected by a path of length 2 in an m‐cycle of C and a path of length 3 in an m‐cycle of C. The class of {2,3}‐perfect m‐cycle systems is said to be equationally defined provided, there exists a variety of quasigroups V with the property that a finite quasigroup (Q, , \, /) belongs to V if and only if its multiplicative (Q, ) part can be constructed from a {2,3}‐perfect m‐cycle system using the 2‐construction (a a = a for all a ∈ Q and if a ≠ b, a b = c and b a = d if and only if the m‐cycle (…, d, x, a, b, y, c, …) ∈ C). The object of this paper is to show that the class of {2,3}‐perfect m‐cycle systems cannot be equationally defined for all m ≥ 10, m ≠ 11. This combined with previous results shows that {2, 3}‐perfect m‐cycle systems are equationally defined for m = 5, 7, 8, 9, and 11 only. © 2004 Wiley Periodicals, Inc. 相似文献