从四色猜想到纽结不变量

从四色猜想到纽结不变量高红铸１四色猜想．所谓四色猜想是说，在平面上随便画一张地图，如果把每个国家涂上一种颜色，使得具有公共边界线的国家能以不同的颜色区分，那末只要四种颜色就够了．这个问题可以用图论的语言来表达，一个图可以看成是由顶点、边以及边和顶点的...     

“另一个25阶最大平面图”G′_(M25)的四色着色

利用最大平面图着色的"简化降阶法",对一定拓扑结构的"另一个25阶最大平面图"G′_(M25)进行了着色运作.先逐点"降阶",再逐点"着色、升阶、着色",直至获得G′_(M25)的四色着色方案.由于着色过程中,有些点的着色是可以选择的,在这些点作任意选色后,只是找出其中的二个G′_(M25)的四色着色方案,即"四色着色方案壹"和"四色着色方案贰"(其他的四色着色方案未作求解).然后,在"四色着色方案壹"和"四色着色方案贰"的基础上,利用多层次的"二色交换法",相应地分别求出了G′_(M25)的二个相近四色着色方案集,即"相近四色着色方案集壹"和"相近四色着色方案集贰".在"相近四色着色方案集壹"中,含有72个不同的四色着色方案;在"相近四色着色方案集贰"中,含有156个不同的四色着色方案.文中对这二个相近四色着色方案集进行了分析,得到了有意义的结果.     

颜色中诞生的数学

四色猜想的"晋升"路 1852年,弗南西斯·格思里在给世界地图上色的时候发现了一个有趣的现象——只要用四种颜色就能把相邻的国家区分开,给拥有共同边界的国家涂上不同的颜色!但经过了很多年,都没有人能证明它或推翻它.     

图与其Mycielski图关联色数的关系

本文证明了对n阶图G,若其最大度△(G)的2倍不等于n,且G的关联色数等于△(G) 1,则M(G)的关联色数为△(M(G)) 1．同时还研究了树和完全二部图的Mycielski图的关联色数．文末提出了M(G)的关联色数猜想,其中M(G)为图G的Mycielski图．     

路与完全图的笛卡尔积图和广义图K(n,m)的关联色数

Richrd A.Brualdi和J.Quinn Massey在[1]中引入了图的关联着色概念,并且提出了关联着色猜想,即每一个图G都可以用△(G)+2种色正常关联着色.B.Guiduli[2]说明关联着色的概念是I.Algor和N.Alon[3]提出的有向星荫度的一个特殊情况,并证实[1]的关联着色猜想是错的,给出图G的关联色数的一个新的上界是△(G)+O(Log(△G)).[4]确定了某些特殊图类的关联色数.本文给出了路和完全图的笛卡尔积图的关联色数,而且利用此结果又确定了完全图Kn的广义图K(n,m)的关联色数.     

关于Whitney和Tutte猜想

ｗｈｉｔｎｅｙ和Ｔｕｔｔｅ把平面四色问题化为只与圈上的４染色集有关的问题来研究，从而探讨四色问题的理论证明；提出了一个蕴含着四色定理的猜想。本文研究开集的组合不变性，从而证明Ｗｈｉｔｎｅｙ和Ｔｕｔｔｅ的猜想不成立。     

Hadwiger猜想的一个等价命题

Hadwiger 猜想说:如果简单图 G 的色数为 k,那么它就含有能收缩到 k 点完全图 S_k 的子图.当 k=5时,这个猜想等价于平面地图四色定理.本文用满色集概念来给出Hadwiger 猜想的一个等价命题。当 k=5时,它也是平面地图四色定理的一个新的等价命题.     

基于光的波粒二象性猜想的数学仿真

从现有的经典物理光学理论和专业实验结果出发,运用数学思维,综合光子理论,建立了基于光的波粒二象性猜想的四种数学模型.针对光微子碰撞猜想,建立了基于光子碰撞后概率分布的模型.针对光子作为电磁场自我旋转的猜想,分别从专业证明和数学模型分析方面建立了电磁场偏转模型和光子旋转模型.最后建立了我们自己的猜想模型——光子蜂窝网络模型.该模型引入了"光子域"、"光子电力"、"光子磁力"、"光子键"等概念,从五个子模型出发,定性解释了四个光学现象,合理回答了题目提出的三大问题,并定量证明了衍射光强分布.     

一个不等式猜想的证明

文[1]末提出了四个不等式猜想,文[2],文[3]均给出了猜想1的详细证明,文[2]还对猜想1作了更深入的讨论.事实上,只要取a=-1,b=-2,c=32,便可知:abc>1,因而猜想2并非十分准确,同样猜想3,4亦有漏洞,本文对猜想4作一细小的修正,并给予证明.作为特例的猜想2,3也就一并解决了.猜想4若ni     

关于完全图的Mycielski图的循环色数的若干结果

给出了任意图G的多重Myeielski图M^m(G)的简单定义方式，用不同的方法证明了当完全图Kn的阶数n足够大时，M^m(Kn)的循环色数等于其点色数．特别证明了，n=7，8，9时，M^3(Kn)的循环色数等于其点色数，从而使得“当n≥m 2，有xc(M^m))=x(M^m(Kn))=m n成立”的猜想有了更新的进展．     

Coloring plane graphs with independent crossings

We show that every plane graph with maximum face size four in which all faces of size four are vertex‐disjoint is cyclically 5‐colorable. This answers a question of Albertson whether graphs drawn in the plane with all crossings independent are 5‐colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 184–205, 2010     

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a^′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.     

Odd 4‐edge‐colorability of graphs

An odd k‐edge‐coloring of a graph G is a (not necessarily proper) edge‐coloring with at most k colors such that each nonempty color class induces a graph in which every vertex is of odd degree. Pyber (1991) showed that every simple graph is odd 4‐edge‐colorable, and Lužar et al. (2015) showed that connected loopless graphs are odd 5‐edge‐colorable, with one particular exception that is odd 6‐edge‐colorable. In this article, we prove that connected loopless graphs are odd 4‐edge‐colorable, with two particular exceptions that are respectively odd 5‐ and odd 6‐edge‐colorable. Moreover, a color class can be reduced to a size at most 2.     

Invalid proofs on incidence coloring

Incidence coloring of a graph G is a mapping from the set of incidences to a color-set C such that adjacent incidences of G are assigned distinct colors. Since 1993, numerous fruitful results as regards incidence coloring have been proved. However, some of them are incorrect. We remedy the error of the proof in [R.A. Brualdi, J.J.Q. Massey, Incidence and strong edge colorings of graphs, Discrete Math. 122 (1993) 51-58] concerning complete bipartite graphs. Also, we give an example to show that an outerplanar graph with Δ=4 is not 5-incidence colorable, which contradicts [S.D. Wang, D.L. Chen, S.C. Pang, The incidence coloring number of Halin graphs and outerplanar graphs, Discrete Math. 256 (2002) 397-405], and prove that the incidence chromatic number of the outerplanar graph with Δ≥7 is Δ+1. Moreover, we prove that the incidence chromatic number of the cubic Halin graph is 5. Finally, to improve the lower bound of the incidence chromatic number, we give some sufficient conditions for graphs that cannot be (Δ+1)-incidence colorable.     

6‐Star‐Coloring of Subcubic Graphs

A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two adjacent vertices are assigned the same color) such that no path on four vertices is 2‐colored. The star chromatic number of G is the smallest integer k for which G admits a star coloring with k colors. In this paper, we prove that every subcubic graph is 6‐star‐colorable. Moreover, the upper bound 6 is best possible, based on the example constructed by Fertin, Raspaud, and Reed (J Graph Theory 47(3) (2004), 140–153).     

Plane Graphs with Maximum Degree Are Entirely ‐Colorable

Let be a plane graph with the sets of vertices, edges, and faces V, E, and F, respectively. If one can color all elements in using k colors so that any two adjacent or incident elements receive distinct colors, then G is said to be entirely k‐colorable. Kronk and Mitchem [Discrete Math 5 (1973) 253‐260] conjectured that every plane graph with maximum degree Δ is entirely ‐colorable. This conjecture has now been settled in Wang and Zhu (J Combin Theory Ser B 101 (2011) 490–501), where the authors asked: is every simple plane graph entirely ‐colorable? In this article, we prove that every simple plane graph with is entirely ‐colorable, and conjecture that every simple plane graph, except the tetrahedron, is entirely ‐colorable.     

On Triangle‐Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph

We prove a decomposition theorem for the class of triangle‐free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph. We prove that every graph of girth at least five in this class is 3‐colorable.     

Complexity of clique‐coloring odd‐hole‐free graphs

In this paper we investigate the problem of clique‐coloring, which consists in coloring the vertices of a graph in such a way that no monochromatic maximal clique appears, and we focus on odd‐hole‐free graphs. On the one hand we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, but on the other hand it is NP‐hard to decide if they are 2‐clique‐colorable, and we do not know if there exists any bound k₀ such that they are all k₀ ‐clique‐colorable. First we will prove that (odd hole, codiamond)‐free graphs are 2‐clique‐colorable. Then we will demonstrate that the complexity of 2‐clique‐coloring odd‐hole‐free graphs is actually Σ₂ P‐complete. Finally we will study the complexity of deciding whether or not a graph and all its subgraphs are 2‐clique‐colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 139–156, 2009     

Interval Non‐edge‐Colorable Bipartite Graphs and Multigraphs

An edge‐coloring of a graph G with colors is called an interval t‐coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. In 1991, Erd?s constructed a bipartite graph with 27 vertices and maximum degree 13 that has no interval coloring. Erd?s's counterexample is the smallest (in a sense of maximum degree) known bipartite graph that is not interval colorable. On the other hand, in 1992, Hansen showed that all bipartite graphs with maximum degree at most 3 have an interval coloring. In this article, we give some methods for constructing of interval non‐edge‐colorable bipartite graphs. In particular, by these methods, we construct three bipartite graphs that have no interval coloring, contain 20, 19, 21 vertices and have maximum degree 11, 12, 13, respectively. This partially answers a question that arose in [T.R. Jensen, B. Toft, Graph coloring problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995, p. 204]. We also consider similar problems for bipartite multigraphs.     

A note on random greedy coloring of uniform hypergraphs

The smallest number of edges forming an n‐uniform hypergraph which is not r‐colorable is denoted by m(n,r). Erd?s and Lovász conjectured that . The best known lower bound was obtained by Radhakrishnan and Srinivasan in 2000. We present a simple proof of their result. The proof is based on the analysis of a random greedy coloring algorithm investigated by Pluhár in 2009. The proof method extends to the case of r‐coloring, and we show that for any fixed r we have improving the bound of Kostochka from 2004. We also derive analogous bounds on minimum edge degree of an n‐uniform hypergraph that is not r‐colorable. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 407–413, 2015