平面图的单射边染色

图G的k-单射边染色是指映射f:E(G)→{1,2,…,k},若e₁,e₂和e₃是G中的连续边,则f (e₁)≠f(e₃).称χ’_i(G)=min{k|G存在k-单射边染色}为图的单射边染色数.本文证明了:对g(G)≥6的平面图G,有χ’_i(G)≤3Δ(G)-2,对g(G)≥26且Δ(G)≤3的平面图G,有χ’_i(G)≤4,对g(G)≥16且Δ(G)≥4的平面图G,有χ’_i(G)≤Δ(G)+1,其中g(G)表示平面图G的围长.     

平面图的严格邻点可区别染色

图G的严格邻点可区别边染色是一个正常边染色,使得每对相邻顶点所关联的边的颜色集合互不包含.G的严格邻点可区别边色数χ’snd(G)是使G有一个严格邻点可区别k-边染色的最小整数k.本领域存在一个重要猜想:除去一个特殊图H_Δ外,每个没有叶子的简单图G都满足χ’snd(G)≤2Δ.当前最好的已知上界是χ’snd(G)≤3Δ-1.一个自然而有趣的问题是,哪类没有叶子的图满足χ’snd(G)≤Δ+C,其中C是一个不依赖于最大度Δ的常数?本文部分地回答了这个问题,即证明了对围长至少为5的平面图G,有χ’snd(G)≤Δ+25.这里围长大于等于5的条件不能被减弱到小于等于4的情形.     

不含5-圈和相邻6-圈的平面图的全染色

图的正常k-全染色是用k种颜色给图的顶点和边同时进行染色,使得相邻或者相关联的元素(顶点或边)染不同的染色.使得图G存在正常k-全染色的最小正整数k,称为图G的全色数,用χ″(G)表示.证明了若图G是最大度△≥6且不含5-圈和相邻6-圈的平面图,则χ″(G)=△+1.     

围长至少为6的平面图的邻点可区别边染色

邻点可区别边染色是指图G有一个正常边染色且任意两个相邻顶点的颜色集合不相等.邻点可区别边色数是指使图G有一个邻点可区别边染色的最小颜色数值,记作χ_α’(G).本文证明了:若图G是围长至少为6的正常平面图,则有χ_α’(G)≤max{6,△(G)+1}.     

1-树图的邻强边染色

图G的一k-正常边染色f若使得任意uv∈E(G)满足f[u]≠f[v],其中f[u]={f(uω)|uw∈E(G)},则称f为G的一k-邻强边染色,简称k-ASEC,并称χ_as(G)=min{k|存在G的一k-ASEC}为G的邻强边色数.本文提出了邻强边染色猜想:对2-连通图G(V,E)(G(V,E)≠C₅),有△(G)≤χ_as(G)≤△(G)+2,并研究了1-树图的邻强边染色,证明了对△(G)≥4的1-树图G有△(G)≤χ_as<     

最大度为4的图的无圈列表边染色

对于图G=(V(G),E(G)),如果一个映射φ:E(G)→{1,2,…,k},使得G中任意相邻的两边e₁,e₂满足φ(e₁)≠φ(e₂),并且G中不含有双色圈,则称φ为G的一个无圈边染色.对于给定的列表分配L={L(e)|e∈E(G)},如果存在图G的一个无圈边染色φ,使得对于任意边e∈E(G),均有φ(e)∈L(e),则称染色φ为G的一个无圈L-边染色.如果对于任意的列表分配L,当对所有的边e∈E(G)满足|L(e)|≥k时,图G均存在无圈L-边染色,那么称G是无圈k-边可选的.使图G无圈k-边可选的最小的正整数k,称为G的无圈列表边色数,用a’_l(G)表示.本文证明了对于最大度△≤4的连通图G,如果|E(G)|≤2|V(G)|-1,则a’_l(G)≤6,扩展了Basavaraju和Chandran文[J.Graph Theory,2009,61(3):192-209]的结果.     

关于图的点可区别边染色猜想的一点注

图G的一个k-正常边染色f被称为点可区别的是指任意两点的点及其关联边所染色集合不同,所用最少颜色数被称为G的点可区别边色数,张忠辅教授提出一个猜想即对每一个正整数k≥3,总存在一个最大度为△(G)=k≥3的图G,图G一定有一个子图H,使得G的点可区别的边色数不超过子图的.本文证明了对于最大度△≤6时,猜想正确.     

不含4-,6-圈和相交三角形的平面图的无圈边色数

图G的一个边染色φ:E(G)→{1,2,…,k},若满足任意相邻边都染不同的颜色,且图G不存在双色圈,则称φ为图G的一个无圈k-边染色.图G的无圈边色数χ’_α(G)为使得图G有一个无圈k-边染色的最小正整数k.本文主要证明了对于无4-,6-圈且3-圈与3-圈不相交的平面图G,若Δ(G)≥9,则χ’_α(G)≤Δ(G)+1.     

双圈图的邻点强可区别全染色

本文研究了双圈图的邻点强可区别全染色问题,并利用结构分析法给出了双圈图的邻点强可区别全色数的上界.即,当G是以∞-图为基图的双圈图时,则χ_ast(G)≤△(G)+2;其他χ_ast(G)≤△(G)+3.从而验证了张忠辅等提出的平面图的邻点强可区别全染色猜想在双圈图上是成立的.     

系列平行图的邻强边色数

本文研究了系列平行图的邻强边染色.从图的结构性质出发,利用双重归纳和换色的方法证明了对于△(G)=3,4的系列平行图满足邻强边染色猜想;对于△(G)≥5的系列平行图G, 有△(G)≤x'as(G)≤△(G) 1,且x'as(G)=△(G) 1当且仅当存在两个最大度点相邻,其中△(G)和x'as(G)分别表示图G的最大度和邻强边色数.     

The Gray graph revisited

Certain graph‐theoretic properties and alternative definitions of the Gray graph, the smallest known cubic edge‐ but not vertex‐transitive graph, are discussed in detail. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 1–7, 2000     

Edge-primitive Cayley graphs on abelian groups and dihedral groups

A graph is called edge-primitive if its automorphism group acts primitively on its edge set. In 1973, Weiss (1973) determined all edge-primitive graphs of valency three, and recently Guo et al. (2013,2015) classified edge-primitive graphs of valencies four and five. In this paper, we determine all edge-primitive Cayley graphs on abelian groups and dihedral groups.     

Hypohamiltonian Planar Cubic Graphs with Girth 5

A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4‐cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices.     

Semisymmetric cubic graphs as regular covers of K 3,3

A regular graph X is called semisymmetric if it is edge-transitive but not vertex-transitive. For G ≤ AutX, we call a G-cover X semisymmetric if X is semisymmetric, and call a G-cover X one-regular if Aut X acts regularly on its arc-set. In this paper, we give the sufficient and necessary conditions for the existence of one-regular or semisymmetric Zn-Covers of K3,3. Also, an infinite family of semisymmetric Zn×Zn-covers of K3,3 are constructed.     

三度边正则图的三个无限族

图X称为边正则图，若X的自同构群Aut(X)在X的边集上的作用是正则的．本文考察了三度边正则图与四度Cayley图的关系，给出了一个由四度Cayley图构造三度边正则图的方法，并且构造了边正则图的三个无限族．     

Hexavalent symmetric graphs of order 9p

A graph is symmetric if its automorphism group acts transitively on the set of arcs of the graph. In this paper, we classify hexavalent symmetric graphs of order $9p$ for each prime $p$.     

Classification of a family of symmetric graphs with complete 2-arc-transitive quotients

In this paper we give a classification of a family of symmetric graphs with complete 2-arc-transitive quotients. Of particular interest are two subfamilies of graphs which admit an arc-transitive action of a projective linear group. The graphs in these subfamilies can be defined in terms of the cross ratio of certain 4-tuples of elements of a finite projective line, and thus may be called the second type ‘cross ratio graphs’, which are different from the ‘cross ratio graphs’ studied in [A. Gardiner, C. E. Praeger, S. Zhou, Cross-ratio graphs, J. London Math. Soc. (2) 64 (2001), 257–272]. We also give a combinatorial characterisation of such second type cross ratio graphs.     

On triconnected and cubic plane graphs on given point sets

Let S be a set of n4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{3n/2,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and hn/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph.     

A Local Analysis of Imprimitive Symmetric Graphs

Let Г be a G-symmetric graph admitting a nontrivial G-invariant partition . Let Г be the quotient graph of Г with respect to . For each block B ∊ , the setwise stabiliser G_B of B in G induces natural actions on B and on the neighbourhood Г (B) of B in Г . Let G_(B) and G_[B] be respectively the kernels of these actions. In this paper we study certain “local actions" induced by G_(B) and G_[B], such as the action of G_[B] on B and the action of G_(B) on Г (B), and their influence on the structure of Г. Supported by a Discovery Project Grant (DP0558677) from the Australian Research Council and a Melbourne Early Career Researcher Grant from The University of Melbourne.