Triangle-Free Planar Graphs as Segment Intersection Graphs

Pure Mathematics 理论数学, 2019, 9(8), 949-960Published Online October 2019 in Hans. /journal/pmhttps:///10.12677/pm.2019.98121Tait’s Conjecture Continue—The Proof of the Four-Color TheoremWenzhen HanJincheng Energy Co. Ltd., Jincheng ShanxiReceived: Sep. 30th, 2019; accepted: Oct. 22nd, 2019; published: Oct. 29th, 2019AbstractThe four-color theorem also known as the four-color conjecture or the four-color problem is one of the world’s three largest mathematical conjecture. Although it has been proved on computer, which owes to its powerful computing ability, after all, it isn’t strictly reasoned mathematically.Lots of math enthusiasts devote themselves to studying the problem around the globe. In this pa-per, the new concepts of two-color dyeable continuous line are put forward. A new method is used to prove that the 3-coloring of 3-regular planar graph lines is equivalent to the 4-coloring of maximal graph points. It is also proved that the 3-coloring of 3-regular planar graph lines is in-evitably possible. Thus, a universal four-color coloring method for vertices of any maximal graph is given.KeywordsFour Colors Enough, Two-Color Dyeable Continuous Line, 3-Regular Plane, Maximum Graph,Even Ring Elimination Method泰特猜想的延续——四色定理的书面证明韩文镇晋城能源有限责任公司，山西晋城收稿日期：2019年9月30日；录用日期：2019年10月22日；发布日期：2019年10月29日摘要四色定理，又称四色猜想、四色问题，是世界三大数学猜想之一。

带断层约束的Delaunay三角剖分混合算法张群会;解子毅【摘要】三角剖分是构建高精度数字高程模型(DEM)的基础,在各个领域都有广泛的应用.特别是在约束数据域下的Delaunay三角剖分更具有重大的研究价值,前人已经做了大量的工作,并提出了一系列经典的剖分算法.在对传统算法进行研究与分析后,总结了传统算法的优缺点,结合了逐点插入法、三角网生长法以及分治法的思想,提出了一种高效的、带断层约束的Delaunay三角剖分混合算法.该算法在建立无约束的DT(Delaunay Triangulation,DT)网格的基础上通过嵌入加密后的断层数据来实现带断层约束的CDT(Constrained Delaunay Triangulation,CDT)网格.通过实例比较,说明了混合算法在构网质量和时间效率上都优于传统算法.【期刊名称】《西安科技大学学报》【年(卷),期】2014(034)001【总页数】5页(P52-56)【关键词】Delaunay三角剖分;混合算法;加密;断层约束【作者】张群会;解子毅【作者单位】西安科技大学计算机科学与技术学院,陕西西安710054;西安科技大学计算机科学与技术学院,陕西西安710054【正文语种】中文【中图分类】TP3900 引言目前比较流行的构建数据高程模型(DEM)的方法主要有2种:一种是基于不规则三角形(Triangular Irregular Networks，TIN)网格法，另一种是四边形(GRID)网格法。

和GRID相比，TIN能够精确地表达网格边界和断层，是一种比较理想的三维层面建模方法，在地质层面可视化方面得到了广泛应用。

Delaunay三角剖分法是建立TIN模型最常用的方法。

由于Delaunay三角化满足最小角最大准则和外接圆不包含其他点准则，总是能尽可能避免狭长的三角形，自动向等边三角形逼近，具有网格形态优美等特点。

因此利用Delaunay三角剖分来建立带断层约束的地质模型具有十分重要的价值。

CGAL功能⼤纲Computational Geometry Algorithms Library，CGAL，计算⼏何算法库。

使⽤C++语⾔编写的，提供⾼效、可控的算法库。

⼴泛应⽤于计算⼏何相关领域，如地理信息系统、计算机图形学、计算机辅助设计、信息可视化系统、⽣物医学等。

CGAL，提供了计算⼏何相关的数据结构和算法，如：（1）三⾓剖分。

2D约束三⾓剖分，2D和3D Delaunay三⾓剖分；（2）Voronoi图。

2D和3D的点，2D加权Voronoi图，分割Voronoi图等；（3）多边形。

布尔运算、偏移、直⾻架等；（4）多⾯体。

布尔运算、2D流型结构、闭合体；（5）曲线（6）⽹格⽣成。

2D Delaunay⽹格⽣成和3D Surface和体积⽹格⽣成；（7）⼏何处理。

表⾯⽹格（Surface Mesh）简化，细分和参数化等；（8）凸壳算法。

适⽤于2D、3D以及dD；（9）搜索结构。

近邻搜索，kd树等；（10）插值（11）形状分析（12）拟合（13）距离算术与代数Arithmetic and Algebra主要提供了计算⼏何⽤到的数学基础：数据类型、多项式、数据结构与算法代数基础Algebraic Foundations这个包从概念、类和函数的⾓度定义了代数对CGAL的意义。

数据类型Number Types这个包为第三⽅数据类型库提供数据类型概念以及数据类型类和包装器类。

模运算Modular Arithmetic这个包提供了有限域的算法。

所提供的⼯具对于基于模块化算法的过滤器和基于余数的算法尤其有⽤。

多项式Polynomial这个包介绍了单变量多项式和多变量多项式的概念。

虽然这个概念是为任意数量的变量编写的，但是对于这个概念的特定模型，变量的数量被认为是固定的。

代数框架Algebraic Kernel解多项式的实解是⼀个应⽤范围很⼴的基本问题。

这个包的⽬标是提供最先进算法的⿊盒实现，以逼近或近似的求解出单变量多项式和双变量多项式的真实根。

Progressive Simplicial Complexes Jovan Popovi´c Hugues HoppeCarnegie Mellon University Microsoft ResearchABSTRACTIn this paper,we introduce the progressive simplicial complex(PSC) representation,a new format for storing and transmitting triangu-lated geometric models.Like the earlier progressive mesh(PM) representation,it captures a given model as a coarse base model together with a sequence of refinement transformations that pro-gressively recover detail.The PSC representation makes use of a more general refinement transformation,allowing the given model to be an arbitrary triangulation(e.g.any dimension,non-orientable, non-manifold,non-regular),and the base model to always consist of a single vertex.Indeed,the sequence of refinement transforma-tions encodes both the geometry and the topology of the model in a unified multiresolution framework.The PSC representation retains the advantages of PM’s.It defines a continuous sequence of approx-imating models for runtime level-of-detail control,allows smooth transitions between any pair of models in the sequence,supports progressive transmission,and offers a space-efficient representa-tion.Moreover,by allowing changes to topology,the PSC sequence of approximations achieves betterfidelity than the corresponding PM sequence.We develop an optimization algorithm for constructing PSC representations for graphics surface models,and demonstrate the framework on models that are both geometrically and topologically complex.CR Categories:I.3.5[Computer Graphics]:Computational Geometry and Object Modeling-surfaces and object representations.Additional Keywords:model simplification,level-of-detail representa-tions,multiresolution,progressive transmission,geometry compression.1INTRODUCTIONModeling and3D scanning systems commonly give rise to triangle meshes of high complexity.Such meshes are notoriously difficult to render,store,and transmit.One approach to speed up rendering is to replace a complex mesh by a set of level-of-detail(LOD) approximations;a detailed mesh is used when the object is close to the viewer,and coarser approximations are substituted as the object recedes[6,8].These LOD approximations can be precomputed Work performed while at Microsoft Research.Email:jovan@,hhoppe@Web:/jovan/Web:/hoppe/automatically using mesh simplification methods(e.g.[2,10,14,20,21,22,24,27]).For efficient storage and transmission,meshcompression schemes[7,26]have also been developed.The recently introduced progressive mesh(PM)representa-tion[13]provides a unified solution to these problems.In PM form,an arbitrary mesh M is stored as a coarse base mesh M0together witha sequence of n detail records that indicate how to incrementally re-fine M0into M n=M(see Figure7).Each detail record encodes theinformation associated with a vertex split,an elementary transfor-mation that adds one vertex to the mesh.In addition to defininga continuous sequence of approximations M0M n,the PM rep-resentation supports smooth visual transitions(geomorphs),allowsprogressive transmission,and makes an effective mesh compressionscheme.The PM representation has two restrictions,however.First,it canonly represent meshes:triangulations that correspond to orientable12-dimensional manifolds.Triangulated2models that cannot be rep-resented include1-d manifolds(open and closed curves),higherdimensional polyhedra(e.g.triangulated volumes),non-orientablesurfaces(e.g.M¨o bius strips),non-manifolds(e.g.two cubes joinedalong an edge),and non-regular models(i.e.models of mixed di-mensionality).Second,the expressiveness of the PM vertex splittransformations constrains all meshes M0M n to have the same topological type.Therefore,when M is topologically complex,the simplified base mesh M0may still have numerous triangles(Fig-ure7).In contrast,a number of existing simplification methods allowtopological changes as the model is simplified(Section6).Ourwork is inspired by vertex unification schemes[21,22],whichmerge vertices of the model based on geometric proximity,therebyallowing genus modification and component merging.In this paper,we introduce the progressive simplicial complex(PSC)representation,a generalization of the PM representation thatpermits topological changes.The key element of our approach isthe introduction of a more general refinement transformation,thegeneralized vertex split,that encodes changes to both the geometryand topology of the model.The PSC representation expresses anarbitrary triangulated model M(e.g.any dimension,non-orientable,non-manifold,non-regular)as the result of successive refinementsapplied to a base model M1that always consists of a single vertex (Figure8).Thus both geometric and topological complexity are recovered progressively.Moreover,the PSC representation retains the advantages of PM’s,including continuous LOD,geomorphs, progressive transmission,and model compression.In addition,we develop an optimization algorithm for construct-ing a PSC representation from a given model,as described in Sec-tion4.1The particular parametrization of vertex splits in[13]assumes that mesh triangles are consistently oriented.2Throughout this paper,we use the words“triangulated”and“triangula-tion”in the general dimension-independent sense.Figure 1:Illustration of a simplicial complex K and some of its subsets.2BACKGROUND2.1Concepts from algebraic topologyTo precisely define both triangulated models and their PSC repre-sentations,we find it useful to introduce some elegant abstractions from algebraic topology (e.g.[15,25]).The geometry of a triangulated model is denoted as a tuple (K V )where the abstract simplicial complex K is a combinatorial structure specifying the adjacency of vertices,edges,triangles,etc.,and V is a set of vertex positions specifying the shape of the model in 3.More precisely,an abstract simplicial complex K consists of a set of vertices 1m together with a set of non-empty subsets of the vertices,called the simplices of K ,such that any set consisting of exactly one vertex is a simplex in K ,and every non-empty subset of a simplex in K is also a simplex in K .A simplex containing exactly d +1vertices has dimension d and is called a d -simplex.As illustrated pictorially in Figure 1,the faces of a simplex s ,denoted s ,is the set of non-empty subsets of s .The star of s ,denoted star(s ),is the set of simplices of which s is a face.The children of a d -simplex s are the (d 1)-simplices of s ,and its parents are the (d +1)-simplices of star(s ).A simplex with exactly one parent is said to be a boundary simplex ,and one with no parents a principal simplex .The dimension of K is the maximum dimension of its simplices;K is said to be regular if all its principal simplices have the same dimension.To form a triangulation from K ,identify its vertices 1m with the standard basis vectors 1m ofm.For each simplex s ,let the open simplex smdenote the interior of the convex hull of its vertices:s =m:jmj =1j=1jjsThe topological realization K is defined as K =K =s K s .The geometric realization of K is the image V (K )where V :m 3is the linear map that sends the j -th standard basis vector jm to j 3.Only a restricted set of vertex positions V =1m lead to an embedding of V (K )3,that is,prevent self-intersections.The geometric realization V (K )is often called a simplicial complex or polyhedron ;it is formed by an arbitrary union of points,segments,triangles,tetrahedra,etc.Note that there generally exist many triangulations (K V )for a given polyhedron.(Some of the vertices V may lie in the polyhedron’s interior.)Two sets are said to be homeomorphic (denoted =)if there ex-ists a continuous one-to-one mapping between them.Equivalently,they are said to have the same topological type .The topological realization K is a d-dimensional manifold without boundary if for each vertex j ,star(j )=d .It is a d-dimensional manifold if each star(v )is homeomorphic to either d or d +,where d +=d:10.Two simplices s 1and s 2are d-adjacent if they have a common d -dimensional face.Two d -adjacent (d +1)-simplices s 1and s 2are manifold-adjacent if star(s 1s 2)=d +1.Figure 2:Illustration of the edge collapse transformation and its inverse,the vertex split.Transitive closure of 0-adjacency partitions K into connected com-ponents .Similarly,transitive closure of manifold-adjacency parti-tions K into manifold components .2.2Review of progressive meshesIn the PM representation [13],a mesh with appearance attributes is represented as a tuple M =(K V D S ),where the abstract simpli-cial complex K is restricted to define an orientable 2-dimensional manifold,the vertex positions V =1m determine its ge-ometric realization V (K )in3,D is the set of discrete material attributes d f associated with 2-simplices f K ,and S is the set of scalar attributes s (v f )(e.g.normals,texture coordinates)associated with corners (vertex-face tuples)of K .An initial mesh M =M n is simplified into a coarser base mesh M 0by applying a sequence of n successive edge collapse transforma-tions:(M =M n )ecol n 1ecol 1M 1ecol 0M 0As shown in Figure 2,each ecol unifies the two vertices of an edgea b ,thereby removing one or two triangles.The position of the resulting unified vertex can be arbitrary.Because the edge collapse transformation has an inverse,called the vertex split transformation (Figure 2),the process can be reversed,so that an arbitrary mesh M may be represented as a simple mesh M 0together with a sequence of n vsplit records:M 0vsplit 0M 1vsplit 1vsplit n 1(M n =M )The tuple (M 0vsplit 0vsplit n 1)forms a progressive mesh (PM)representation of M .The PM representation thus captures a continuous sequence of approximations M 0M n that can be quickly traversed for interac-tive level-of-detail control.Moreover,there exists a correspondence between the vertices of any two meshes M c and M f (0c f n )within this sequence,allowing for the construction of smooth vi-sual transitions (geomorphs)between them.A sequence of such geomorphs can be precomputed for smooth runtime LOD.In addi-tion,PM’s support progressive transmission,since the base mesh M 0can be quickly transmitted first,followed the vsplit sequence.Finally,the vsplit records can be encoded concisely,making the PM representation an effective scheme for mesh compression.Topological constraints Because the definitions of ecol and vsplit are such that they preserve the topological type of the mesh (i.e.all K i are homeomorphic),there is a constraint on the min-imum complexity that K 0may achieve.For instance,it is known that the minimal number of vertices for a closed genus g mesh (ori-entable 2-manifold)is (7+(48g +1)12)2if g =2(10if g =2)[16].Also,the presence of boundary components may further constrain the complexity of K 0.Most importantly,K may consist of a number of components,and each is required to appear in the base mesh.For example,the meshes in Figure 7each have 117components.As evident from the figure,the geometry of PM meshes may deteriorate severely as they approach topological lower bound.M 1;100;(1)M 10;511;(7)M 50;4656;(12)M 200;1552277;(28)M 500;3968690;(58)M 2000;14253219;(108)M 5000;029010;(176)M n =34794;0068776;(207)Figure 3:Example of a PSC representation.The image captions indicate the number of principal 012-simplices respectively and the number of connected components (in parenthesis).3PSC REPRESENTATION 3.1Triangulated modelsThe first step towards generalizing PM’s is to let the PSC repre-sentation encode more general triangulated models,instead of just meshes.We denote a triangulated model as a tuple M =(K V D A ).The abstract simplicial complex K is not restricted to 2-manifolds,but may in fact be arbitrary.To represent K in memory,we encode the incidence graph of the simplices using the following linked structures (in C++notation):struct Simplex int dim;//0=vertex,1=edge,2=triangle,...int id;Simplex*children[MAXDIM+1];//[0..dim]List<Simplex*>parents;;To render the model,we draw only the principal simplices ofK ,denoted (K )(i.e.vertices not adjacent to edges,edges not adjacent to triangles,etc.).The discrete attributes D associate amaterial identifier d s with each simplex s(K ).For the sake of simplicity,we avoid explicitly storing surface normals at “corners”(using a set S )as done in [13].Instead we let the material identifier d s contain a smoothing group field [28],and let a normal discontinuity (crease )form between any pair of adjacent triangles with different smoothing groups.Previous vertex unification schemes [21,22]render principal simplices of dimension 0and 1(denoted 01(K ))as points and lines respectively with fixed,device-dependent screen widths.To better approximate the model,we instead define a set A that associates an area a s A with each simplex s 01(K ).We think of a 0-simplex s 00(K )as approximating a sphere with area a s 0,and a 1-simplex s 1=j k 1(K )as approximating a cylinder (with axis (j k ))of area a s 1.To render a simplex s 01(K ),we determine the radius r model of the corresponding sphere or cylinder in modeling space,and project the length r model to obtain the radius r screen in screen pixels.Depending on r screen ,we render the simplex as a polygonal sphere or cylinder with radius r model ,a 2D point or line with thickness 2r screen ,or do not render it at all.This choice based on r screen can be adjusted to mitigate the overhead of introducing polygonal representations of spheres and cylinders.As an example,Figure 3shows an initial model M of 68,776triangles.One of its approximations M 500is a triangulated model with 3968690principal 012-simplices respectively.3.2Level-of-detail sequenceAs in progressive meshes,from a given triangulated model M =M n ,we define a sequence of approximations M i :M 1op 1M 2op 2M n1op n 1M nHere each model M i has exactly i vertices.The simplification op-erator M ivunify iM i +1is the vertex unification transformation,whichmerges two vertices (Section 3.3),and its inverse M igvspl iM i +1is the generalized vertex split transformation (Section 3.4).Thetuple (M 1gvspl 1gvspl n 1)forms a progressive simplicial complex (PSC)representation of M .To construct a PSC representation,we first determine a sequence of vunify transformations simplifying M down to a single vertex,as described in Section 4.After reversing these transformations,we renumber the simplices in the order that they are created,so thateach gvspl i (a i)splits the vertex a i K i into two vertices a i i +1K i +1.As vertices may have different positions in the different models,we denote the position of j in M i as i j .To better approximate a surface model M at lower complexity levels,we initially associate with each (principal)2-simplex s an area a s equal to its triangle area in M .Then,as the model is simplified,wekeep constant the sum of areas a s associated with principal simplices within each manifold component.When2-simplices are eventually reduced to principal1-simplices and0-simplices,their associated areas will provide good estimates of the original component areas.3.3Vertex unification transformationThe transformation vunify(a i b i midp i):M i M i+1takes an arbitrary pair of vertices a i b i K i+1(simplex a i b i need not be present in K i+1)and merges them into a single vertex a i K i. Model M i is created from M i+1by updating each member of the tuple(K V D A)as follows:K:References to b i in all simplices of K are replaced by refer-ences to a i.More precisely,each simplex s in star(b i)K i+1is replaced by simplex(s b i)a i,which we call the ancestor simplex of s.If this ancestor simplex already exists,s is deleted.V:Vertex b is deleted.For simplicity,the position of the re-maining(unified)vertex is set to either the midpoint or is left unchanged.That is,i a=(i+1a+i+1b)2if the boolean parameter midp i is true,or i a=i+1a otherwise.D:Materials are carried through as expected.So,if after the vertex unification an ancestor simplex(s b i)a i K i is a new principal simplex,it receives its material from s K i+1if s is a principal simplex,or else from the single parent s a i K i+1 of s.A:To maintain the initial areas of manifold components,the areasa s of deleted principal simplices are redistributed to manifold-adjacent neighbors.More concretely,the area of each princi-pal d-simplex s deleted during the K update is distributed toa manifold-adjacent d-simplex not in star(a ib i).If no suchneighbor exists and the ancestor of s is a principal simplex,the area a s is distributed to that ancestor simplex.Otherwise,the manifold component(star(a i b i))of s is being squashed be-tween two other manifold components,and a s is discarded. 3.4Generalized vertex split transformation Constructing the PSC representation involves recording the infor-mation necessary to perform the inverse of each vunify i.This inverse is the generalized vertex split gvspl i,which splits a0-simplex a i to introduce an additional0-simplex b i.(As mentioned previously, renumbering of simplices implies b i i+1,so index b i need not be stored explicitly.)Each gvspl i record has the formgvspl i(a i C K i midp i()i C D i C A i)and constructs model M i+1from M i by updating the tuple (K V D A)as follows:K:As illustrated in Figure4,any simplex adjacent to a i in K i can be the vunify result of one of four configurations in K i+1.To construct K i+1,we therefore replace each ancestor simplex s star(a i)in K i by either(1)s,(2)(s a i)i+1,(3)s and(s a i)i+1,or(4)s,(s a i)i+1and s i+1.The choice is determined by a split code associated with s.Thesesplit codes are stored as a code string C Ki ,in which the simplicesstar(a i)are sortedfirst in order of increasing dimension,and then in order of increasing simplex id,as shown in Figure5. V:The new vertex is assigned position i+1i+1=i ai+()i.Theother vertex is given position i+1ai =i ai()i if the boolean pa-rameter midp i is true;otherwise its position remains unchanged.D:The string C Di is used to assign materials d s for each newprincipal simplex.Simplices in C Di ,as well as in C Aibelow,are sorted by simplex dimension and simplex id as in C Ki. A:During reconstruction,we are only interested in the areas a s fors01(K).The string C Ai tracks changes in these areas.Figure4:Effects of split codes on simplices of various dimensions.code string:41422312{}Figure5:Example of split code encoding.3.5PropertiesLevels of detail A graphics application can efficiently transitionbetween models M1M n at runtime by performing a sequence ofvunify or gvspl transformations.Our current research prototype wasnot designed for efficiency;it attains simplification rates of about6000vunify/sec and refinement rates of about5000gvspl/sec.Weexpect that a careful redesign using more efficient data structureswould significantly improve these rates.Geomorphs As in the PM representation,there exists a corre-spondence between the vertices of the models M1M n.Given acoarser model M c and afiner model M f,1c f n,each vertexj K f corresponds to a unique ancestor vertex f c(j)K cfound by recursively traversing the ancestor simplex relations:f c(j)=j j cf c(a j1)j cThis correspondence allows the creation of a smooth visual transi-tion(geomorph)M G()such that M G(1)equals M f and M G(0)looksidentical to M c.The geomorph is defined as the modelM G()=(K f V G()D f A G())in which each vertex position is interpolated between its originalposition in V f and the position of its ancestor in V c:Gj()=()fj+(1)c f c(j)However,we must account for the special rendering of principalsimplices of dimension0and1(Section3.1).For each simplexs01(K f),we interpolate its area usinga G s()=()a f s+(1)a c swhere a c s=0if s01(K c).In addition,we render each simplexs01(K c)01(K f)using area a G s()=(1)a c s.The resultinggeomorph is visually smooth even as principal simplices are intro-duced,removed,or change dimension.The accompanying video demonstrates a sequence of such geomorphs.Progressive transmission As with PM’s,the PSC representa-tion can be progressively transmitted by first sending M 1,followed by the gvspl records.Unlike the base mesh of the PM,M 1always consists of a single vertex,and can therefore be sent in a fixed-size record.The rendering of lower-dimensional simplices as spheres and cylinders helps to quickly convey the overall shape of the model in the early stages of transmission.Model compression Although PSC gvspl are more general than PM vsplit transformations,they offer a surprisingly concise representation of M .Table 1lists the average number of bits re-quired to encode each field of the gvspl records.Using arithmetic coding [30],the vertex id field a i requires log 2i bits,and the boolean parameter midp i requires 0.6–0.9bits for our models.The ()i delta vector is quantized to 16bitsper coordinate (48bits per),and stored as a variable-length field [7,13],requiring about 31bits on average.At first glance,each split code in the code string C K i seems to have 4possible outcomes (except for the split code for 0-simplex a i which has only 2possible outcomes).However,there exist constraints between these split codes.For example,in Figure 5,the code 1for 1-simplex id 1implies that 2-simplex id 1also has code 1.This in turn implies that 1-simplex id 2cannot have code 2.Similarly,code 2for 1-simplex id 3implies a code 2for 2-simplex id 2,which in turn implies that 1-simplex id 4cannot have code 1.These constraints,illustrated in the “scoreboard”of Figure 6,can be summarized using the following two rules:(1)If a simplex has split code c12,all of its parents havesplit code c .(2)If a simplex has split code 3,none of its parents have splitcode 4.As we encode split codes in C K i left to right,we apply these two rules (and their contrapositives)transitively to constrain the possible outcomes for split codes yet to be ing arithmetic coding with uniform outcome probabilities,these constraints reduce the code string length in Figure 6from 15bits to 102bits.In our models,the constraints reduce the code string from 30bits to 14bits on average.The code string is further reduced using a non-uniform probability model.We create an array T [0dim ][015]of encoding tables,indexed by simplex dimension (0..dim)and by the set of possible (constrained)split codes (a 4-bit mask).For each simplex s ,we encode its split code c using the probability distribution found in T [s dim ][s codes mask ].For 2-dimensional models,only 10of the 48tables are non-trivial,and each table contains at most 4probabilities,so the total size of the probability model is small.These encoding tables reduce the code strings to approximately 8bits as shown in Table 1.By comparison,the PM representation requires approximately 5bits for the same information,but of course it disallows topological changes.To provide more intuition for the efficiency of the PSC repre-sentation,we note that capturing the connectivity of an average 2-manifold simplicial complex (n vertices,3n edges,and 2n trian-gles)requires ni =1(log 2i +8)n (log 2n +7)bits with PSC encoding,versus n (12log 2n +95)bits with a traditional one-way incidence graph representation.For improved compression,it would be best to use a hybrid PM +PSC representation,in which the more concise PM vertex split encoding is used when the local neighborhood is an orientableFigure 6:Constraints on the split codes for the simplices in the example of Figure 5.Table 1:Compression results and construction times.Object#verts Space required (bits/n )Trad.Con.n K V D Arepr.time a i C K i midp i (v )i C D i C Ai bits/n hrs.drumset 34,79412.28.20.928.1 4.10.453.9146.1 4.3destroyer 83,79913.38.30.723.1 2.10.347.8154.114.1chandelier 36,62712.47.60.828.6 3.40.853.6143.6 3.6schooner 119,73413.48.60.727.2 2.5 1.353.7148.722.2sandal 4,6289.28.00.733.4 1.50.052.8123.20.4castle 15,08211.0 1.20.630.70.0-43.5-0.5cessna 6,7959.67.60.632.2 2.50.152.6132.10.5harley 28,84711.97.90.930.5 1.40.453.0135.7 3.52-dimensional manifold (this occurs on average 93%of the time in our examples).To compress C D i ,we predict the material for each new principalsimplex sstar(a i )star(b i )K i +1by constructing an ordered set D s of materials found in star(a i )K i .To improve the coding model,the first materials in D s are those of principal simplices in star(s )K i where s is the ancestor of s ;the remainingmaterials in star(a i )K i are appended to D s .The entry in C D i associated with s is the index of its material in D s ,encoded arithmetically.If the material of s is not present in D s ,it is specified explicitly as a global index in D .We encode C A i by specifying the area a s for each new principalsimplex s 01(star(a i )star(b i ))K i +1.To account for this redistribution of area,we identify the principal simplex from which s receives its area by specifying its index in 01(star(a i ))K i .The column labeled in Table 1sums the bits of each field of the gvspl records.Multiplying by the number n of vertices in M gives the total number of bits for the PSC representation of the model (e.g.500KB for the destroyer).By way of compari-son,the next column shows the number of bits per vertex required in a traditional “IndexedFaceSet”representation,with quantization of 16bits per coordinate and arithmetic coding of face materials (3n 16+2n 3log 2n +materials).4PSC CONSTRUCTIONIn this section,we describe a scheme for iteratively choosing pairs of vertices to unify,in order to construct a PSC representation.Our algorithm,a generalization of [13],is time-intensive,seeking high quality approximations.It should be emphasized that many quality metrics are possible.For instance,the quadric error metric recently introduced by Garland and Heckbert [9]provides a different trade-off of execution speed and visual quality.As in [13,20],we first compute a cost E for each candidate vunify transformation,and enter the candidates into a priority queueordered by ascending cost.Then,in each iteration i =n 11,we perform the vunify at the front of the queue and update the costs of affected candidates.4.1Forming set of candidate vertex pairs In principle,we could enter all possible pairs of vertices from M into the priority queue,but this would be prohibitively expensive since simplification would then require at least O(n2log n)time.Instead, we would like to consider only a smaller set of candidate vertex pairs.Naturally,should include the1-simplices of K.Additional pairs should also be included in to allow distinct connected com-ponents of M to merge and to facilitate topological changes.We considered several schemes for forming these additional pairs,in-cluding binning,octrees,and k-closest neighbor graphs,but opted for the Delaunay triangulation because of its adaptability on models containing components at different scales.We compute the Delaunay triangulation of the vertices of M, represented as a3-dimensional simplicial complex K DT.We define the initial set to contain both the1-simplices of K and the subset of1-simplices of K DT that connect vertices in different connected components of K.During the simplification process,we apply each vertex unification performed on M to as well in order to keep consistent the set of candidate pairs.For models in3,star(a i)has constant size in the average case,and the overall simplification algorithm requires O(n log n) time.(In the worst case,it could require O(n2log n)time.)4.2Selecting vertex unifications fromFor each candidate vertex pair(a b),the associated vunify(a b):M i M i+1is assigned the costE=E dist+E disc+E area+E foldAs in[13],thefirst term is E dist=E dist(M i)E dist(M i+1),where E dist(M)measures the geometric accuracy of the approximate model M.Conceptually,E dist(M)approximates the continuous integralMd2(M)where d(M)is the Euclidean distance of the point to the closest point on M.We discretize this integral by defining E dist(M)as the sum of squared distances to M from a dense set of points X sampled from the original model M.We sample X from the set of principal simplices in K—a strategy that generalizes to arbitrary triangulated models.In[13],E disc(M)measures the geometric accuracy of disconti-nuity curves formed by a set of sharp edges in the mesh.For the PSC representation,we generalize the concept of sharp edges to that of sharp simplices in K—a simplex is sharp either if it is a boundary simplex or if two of its parents are principal simplices with different material identifiers.The energy E disc is defined as the sum of squared distances from a set X disc of points sampled from sharp simplices to the discontinuity components from which they were sampled.Minimization of E disc therefore preserves the geom-etry of material boundaries,normal discontinuities(creases),and triangulation boundaries(including boundary curves of a surface and endpoints of a curve).We have found it useful to introduce a term E area that penalizes surface stretching(a more sophisticated version of the regularizing E spring term of[13]).Let A i+1N be the sum of triangle areas in the neighborhood star(a i)star(b i)K i+1,and A i N the sum of triangle areas in star(a i)K i.The mean squared displacement over the neighborhood N due to the change in area can be approx-imated as disp2=12(A i+1NA iN)2.We let E area=X N disp2,where X N is the number of points X projecting in the neighborhood. To prevent model self-intersections,the last term E fold penalizes surface folding.We compute the rotation of each oriented triangle in the neighborhood due to the vertex unification(as in[10,20]).If any rotation exceeds a threshold angle value,we set E fold to a large constant.Unlike[13],we do not optimize over the vertex position i a, but simply evaluate E for i a i+1a i+1b(i+1a+i+1b)2and choose the best one.This speeds up the optimization,improves model compression,and allows us to introduce non-quadratic energy terms like E area.5RESULTSTable1gives quantitative results for the examples in thefigures and in the video.Simplification times for our prototype are measured on an SGI Indigo2Extreme(150MHz R4400).Although these times may appear prohibitive,PSC construction is an off-line task that only needs to be performed once per model.Figure9highlights some of the benefits of the PSC representa-tion.The pearls in the chandelier model are initially disconnected tetrahedra;these tetrahedra merge and collapse into1-d curves in lower-complexity approximations.Similarly,the numerous polyg-onal ropes in the schooner model are simplified into curves which can be rendered as line segments.The straps of the sandal model initially have some thickness;the top and bottom sides of these straps merge in the simplification.Also note the disappearance of the holes on the sandal straps.The castle example demonstrates that the original model need not be a mesh;here M is a1-dimensional non-manifold obtained by extracting edges from an image.6RELATED WORKThere are numerous schemes for representing and simplifying tri-angulations in computer graphics.A common special case is that of subdivided2-manifolds(meshes).Garland and Heckbert[12] provide a recent survey of mesh simplification techniques.Several methods simplify a given model through a sequence of edge col-lapse transformations[10,13,14,20].With the exception of[20], these methods constrain edge collapses to preserve the topological type of the model(e.g.disallow the collapse of a tetrahedron into a triangle).Our work is closely related to several schemes that generalize the notion of edge collapse to that of vertex unification,whereby separate connected components of the model are allowed to merge and triangles may be collapsed into lower dimensional simplices. Rossignac and Borrel[21]overlay a uniform cubical lattice on the object,and merge together vertices that lie in the same cubes. Schaufler and St¨u rzlinger[22]develop a similar scheme in which vertices are merged using a hierarchical clustering algorithm.Lue-bke[18]introduces a scheme for locally adapting the complexity of a scene at runtime using a clustering octree.In these schemes, the approximating models correspond to simplicial complexes that would result from a set of vunify transformations(Section3.3).Our approach differs in that we order the vunify in a carefully optimized sequence.More importantly,we define not only a simplification process,but also a new representation for the model using an en-coding of gvspl=vunify1transformations.Recent,independent work by Schmalstieg and Schaufler[23]de-velops a similar strategy of encoding a model using a sequence of vertex split transformations.Their scheme differs in that it tracks only triangles,and therefore requires regular,2-dimensional trian-gulations.Hence,it does not allow lower-dimensional simplices in the model approximations,and does not generalize to higher dimensions.Some simplification schemes make use of an intermediate vol-umetric representation to allow topological changes to the model. He et al.[11]convert a mesh into a binary inside/outside function discretized on a three-dimensional grid,low-passfilter this function,。

笛卡尔积图的线性荫度陶昉昀;林文松【摘要】线性森林是指所有分支都是路的森林.图G的线性荫度la(G)是划分G的边集E(G)所需的线性森林的最小数目.图G和H的笛卡尔积图G□□H定义为:顶点集V(G□□H)={(u,v)|u∈V(G),v∈V(H)}.边集E(G□□H)={(u,x)(v,y)|u=v且xy∈E(H),或uv∈E(G)且x=y}.令Pm与Gm分别表示m个顶点的路和圈,Kn表示n个顶点的完全图.证明了la(Kn□□Pm)=[n+1/2](m≥2),la(Kn□□Cm)=[n+2/2]以及la(Kn□Km)=[n+m-1/2].证明过程给出了将这些图分解成线性森林的方法.进一步的线性荫度猜想对这些图类是成立的.【期刊名称】《东南大学学报（英文版）》【年(卷),期】2013(029)002【总页数】4页(P222-225)【关键词】线性森林;线性荫度;笛卡尔积【作者】陶昉昀;林文松【作者单位】东南大学数学系,南京211189;南京林业大学数学系,南京210037;东南大学数学系,南京211189【正文语种】中文【中图分类】O157.5In this paper, all the graphs are simple, finite and undirected. For a realnumber x, 「x⎤ is the least integer not less than x and ⎤x」 is the largest integer not larger than x. Let G be a graph. We use V(G), E(G) and Δ(G) to denote the vertex set, the edge set and the maximum degree of G, respectively.A linear forest is a forest whose components are paths. The linear arboricity la(G) of G defined by Harary[1] is the minimum number of linear forests needed to partition the edge set E(G) of G.Akiyama et al.[2] conjectured that la(G)=「(Δ(G)+1)/2⎤ for any regular graph G. They proved that the conjecture is true for complete graphs and graphs with Δ=3,4[2-3]. Enomoto and Péroche[4] proved that the conjecture is true for graphs with Δ=5,6,8. Guldan[5] proved that the conjecture is true for graphs with Δ=10. It is obvious that la(G)≥「Δ(G)/2⎤for every graph G and la(G)≥「(Δ(G)+1)/2⎤ for every regular graph G. So the conjecture is equivalent to the following linear arboricity conjecture (LAC)[2]. For any graph G, 「Δ(G)/2⎤≤la(G)≤「(Δ(G)+1)/2⎤.Akiyama et al.[2] determined the linear arboricity of complete bipartite graphs and trees. Martinova[6] determined the linear arboricity of the maximal outerplanar graphs. Wu et al.[7-8] proved that the LAC is true for all the planar graphs. Wu[9] also determined the linear arboricity of the series-parallel graphs. Some other researches on linear arboricity can be found in Refs.[10-12].The Cartesian product of two graphs G and H (or simply product), denoted by G□H, is defined as the graph with vertex set V(G□H)={(u,v)|u∈V(G),v∈V(H)} and edge set E(G□H)={(u,x)(v,y)|u=v and xy∈E(H), or uv∈E(G) andx=y}. Let Pm and Cm respectively, denote the path and cycle on m vertices and Kn denote the complete graph on n vertices. In this paper, we determine the linear arboricity of Kn□Pm, Kn□Cm and Kn□Km.The following lemmas are useful in our proofs.Lemma1 If H is a subgraph of G, then la(H)≤la(G).Lemma2 la(G□H)≤la(G)+la(H).Lemma 2 holds by the definition of the linear arboricity and the Cartesian product of graphs.Lemma3[2] la(Kn)=「n/2⎤.Lemma4[13] For n≥3, the complete graph Kn is decomposable into edge disjoint Hamilton cycles if and only if n is odd. For n≥2, the complete graph Kn is decomposable into edge disjoint Hamilton paths if and only if n is even.Lemma5[14] Let V(K2n)={v0,v1,…,v2n-1}. For 0≤i≤n-1, putFi=v0+iv1+iv2n-1+iv2+iv2n-2+i…vn+1+ivn+iwhere the indices of vj’s are taken modulo 2n. Then F0,F1,…,Fn-1 are disjoint Hamilton paths of K2n; i.e., K2n is decomposed into edge disjoint Hamilton paths F0,F1,…,Fn-1.1 la(Kn□Pm)Let V(Kn)={u,v0,v1,…,vn-2} and V(Pm)={y0,y1,…,ym-1}. For convenience, we denote any vertex (x,yj)∈V(Kn□Pm) by x(j). For a fixed j (j=0,1,…,m-1), we use to denote the complete graph induced by {u(j),,,…,}.The following lemma deals with the decomposition of the complete graph K2n+1.Lemma6 E(K2n+1)=nP2n+1∪Mn, where Mn is a matching of order n. Proof Let V(K2n+1)={u,v0,v1,…,v2n-1}. For 0≤i≤n-1, putFi=v0+iv1+iv2n-1+iv2+iv2n-2+i…vn+1+ivn+iwhere the indices of vj’s are taken modulo 2n. Then, by Lemma 5, the complete graph K2n+1\{u} is decomposed into n disjoint Hamilton paths: F0,F1,…,Fn-1. For 0≤i≤n-1, let ei be the n-th edge of Fi andMn={e0,e1,…,en-1}. Then ei=vi+「n/2⎤vi-「n/2⎤ for i=0,1,…,n-1 andMn={v0vn,v1vn+1,…,vn-1v2n-1}. Clearly, Mn is a matching of order n. For each 0≤i≤n-1, by deleting ei from Fi and adding two edges uvi, uvn+i to Fi, we obtain a path on 2n+1 vertices. The n paths obtained in this way together with Mn form a decomposition of K2n+1 as claimed in the lemma. Theorem1 la(Kn□Pm)= for m≥2.Proof If m=2, then la(Kn□Pm)≥ since Kn□Pm is n-regular. If m≥3, thenla(Kn□Pm)≥=, where Δ=Δ(Kn□Pm). We now prove the reverse inequality. If n is even, then la(Kn□Pm)≤la(Kn)+la(Pm)=+1= by Lemmas 2 and 3. Thus Theorem 1 holds for even n.Now suppose that n is odd. Let n=2k+1, where k≥1. For 0≤i≤k-1 and0≤j≤m-1, putwhere the indices of ’s are taken modulo 2k. Then by Lemmas 4 and 5, for 0≤j≤m-1, is decomposed into k edge disjoint Hamilton cycles=u(j)(i=0,1,…,k-1).Let be the k-th edge of and = \{} for 0≤i≤k-1 and 0≤j≤m-1. From the proof of Lemma 6, each complete graph can be decomposed into k edgedisjoint Hamilton paths ,,…, and a matching ={,,…,}.Let Nxi={j=1,3,…,s}, where s=m-2 if m is odd and s=m-3 if m is even; and Nyi={j=0,2,…,t}, where t=m-3 if m is odd and t=m-2 if m is even.Let Li=()∪Nxi∪Nyi for 0≤i≤k-1. Then L0,L1,…,Lk-1 are k edge disjoint Hamilton paths of Kn□Pm. After we take away these Hamilton paths from Kn□Pm, the remaining edges form a linear forest. Thus,la(Kn□Pm)≤k+1=+1=. This com pletes the proof.2 la(Kn□Cm)Theorem2 la(Kn□Cm)=.Proof Since Kn□Cm can be decomposed into a Kn□Pm and a matching of size n, we have la(Kn□Cm)≤la(Kn□Pm)+1=+1 by Theorem 1. On the other hand, since Kn□Cm is (n+1)-regular, la(Kn□Cm)≥=. If n is odd, thenla(Kn□Cm)≤=. Therefore the theorem holds for odd n.Now we consider the case that n is even. Note that , we only need to show that Kn□Cm can be decomposed into linear forests. Let n=2k, where k≥1. Let V(Kn)={v0,v1,…,v2k-1} and V(Cm)={y0,y1,…,ym-1}. For convenience, we denote any vertex (vi,yj)∈V(Kn□Cm) by . For a fixed j (j=0,1,…,m-1), we use to denote the complete graph induced by {,,…,}. By Lemma 5, for 0≤j≤m-1, each can be decomposed into k edge disjoint Hamilton paths (i=0,1,…,k-1), whereand the subscripts are taken modulo 2k.For i=0,1,…,k-1, let Li=()∪{}∪{}. It is easy to see that L0,L1,…,Lk-1 are k edge disjoint linear forests and the remaining edges in Kn□Cm form onelinear forest. Thus, la(Kn□Cm)≤k+1=, which completes the proof.3 la(Kn□Km)Theor em3 la(Kn□Km)= if n and m are both even.Proof By Lemmas 2 and 3, la(Kn□Km)≤la(Kn)+la(Km)=+=. Since Kn□Km is (n+m-2)-regular, la(Kn□Km)≥=.Now, we consider the case that at least one of n,m is odd.Theorem 4 la(Kn□Km)= if n is even and m is odd.Proof Let n=2k, k≥1. Let V(Kn)={v0,v1,…,vn-1} and V(Km)={y0,y1,…,ym-1}. For convenience, we denote any vertex (vi,yj)∈V(Kn□Km) by . For a fixed j (j=0,1,…,m-1), we use to denote the complete graph induced by {,,…,}. For a fixed i (i=0,1,…,n-1), we use to denote the complete graph induced by {,,…,}. By Lemma 5, for 0≤j≤m-1, each can be decomposed into k edge disjoint Hamilton paths (i=0,1,…,k-1), whereand the subscripts are taken modulo 2k.For i=0,1,…,k-1, let Ni={j=0,2,…,m-3} and Ni+k={j=1,3,…,m-2}. It is easy to see that each Ni(i=0,1,…,2k-1) is a matching of and |Ni|=. By Lemma 6, the edges in each Ni(i=0,1,…,2k-1) can be partitioned into Hamilton paths. So the edges in E()\Ni(i=0,1,…,2k-1) form linear forests together. Furthermore, for 0≤i≤k-1, each ()∪Ni∪Ni+k forms a linear forest. So la(Kn□Km)≤+k=+=. On the other hand, la(Kn□Km)≥= since Kn□Km is (n+m-2)-regular. This completes the proof.Theorem5 la(Kn□Km)= if n and m are both odd.Proof We use the same notations in Theorem 4; i.e., letV(Kn□Km)={i=0,1,…,n-1;j=0,1,…,m-1}. For a fixed j (j=0,1,…,m-1), we use to denote the complete graph induced by {,,}. For a fixed i (i=0,1,…,n-1), we use to denote the complete graph induced by {,,…,}.Let Hi={j=0,2,…,m-3} for i=0,1,3,5,…n-2 and Hi={j=1,3,…,m-2} fori=2,4,6,…n-1. Then each Hi is a matching of with edges. By Lemma 6, the edges in each E()\Hi(i=0,1,…,n-1) can be partitioned into Hamilton paths. So the edges in E()\Hi(i=0,1,…,n-1) form linear forests together.Let Lj={,,…,} for j=0,1,…m-1. Then each Lj is a matching of with edges. Again by Lemma 6, the edges in each E()\Lj(j=0,1,…,m-1) can be partitioned into Hamilton paths. So the edges in E()\Lj(j=0,1,…,m-1) form linear forests together.It is clear that (Hi)∪(Lj) forms a linear forest. So la(Kn□Km)≤++1=. On the other hand, since Kn□Km is (n+m-2)-regular, la(Kn□Km)≥=. This completes the proof.Summarizing Theorems 3 to 5, we have the following theorem. Theorem6 la(Kn□Km)=.References[1]Harary F. Covering and packing in graphs 1 [J]. AnnalsoftheNewYorkAcademyofSciences, 1970, 175(1): 198-205.[2]Akiyama J, Exoo G, Harary F. Covering and packing in graphs 3: cyclic and acyclic invariants [J]. MathSlovaca, 1980, 30(4): 405-417.[3]Akiyama J, Exoo G, Harary F. Covering and packing in graphs 4: linear arboricity [J]. Networks, 1981, 11(1): 69-72.[4]Enomoto H, Péroche B. The linear arboricity of some regular graphs [J].JournalofGraphTheory, 1984, 8(2): 309-324.[5]Guldan F. The linear arboricity of 10-regular graphs [J]. MathSlovaca, 1986, 36(3): 225-228.[6]Martinova M K. Linear arboricity of maximal outerplanar graphs [J]. GodishnikVisshUchebnZavedPrilozhnaMath, 1987, 23: 147-155. (in Bulgarian)[7]Wu Jianliang. On the linear arboricity of planar graphs [J]. JournalofGraphTheory, 1999, 31(2): 129-134.[8]Wu Jianliang, Wu Yuwen. The linear arboricity of planar graphs of maximum degree seven are four [J]. JournalofGraphTheory, 2008, 58(3): 210-220.[9]Wu Jianliang. The linear arboricity of series-parallel graphs [J]. GraphsandCombinatorics, 2000, 16(3): 367-372.[10]Lu Xiaoxu, Xu Baogang. A note on vertex-arboricity of plane graphs [J]. JournalofNanjingUniversity: NaturalSciences, 2007, 43(1): 13-18.[11]Tan Xiang, Chen Hongyu, Wu Jianliang. The linear arboricity of planar graphs with maximum degree at least five [J]. BulletinoftheMalaysianMathematicalSciencesSociety, 2011, 34(3): 541-552.[12]Wu Jianliang, Hou Jianfeng, Liu Guizhen. The linear arboricity of planar graphs with no short cycles [J]. TheoreticalComputerScience, 2007,381(1/2/3): 230-233.[13]Bollobs B. Moderngraphtheory [M]. New York:Springer-Verlag, 1998.[14]Chen B L, Huang K C. On the linear k-arboricity of Kn and Kn,n [J].DiscreteMath, 2002, 254(1/2/3): 51-61.。

无向哈密顿图的一个充分必要条件及计算公式侯爱民;郝志峰【期刊名称】《计算机工程与应用》【年(卷),期】2011(047)014【摘要】哈密顿图的判定问题是一个NP完全问题,是图论理论中尚未解决的主要问题之一.1968年,Grinberg证明了一个必要条件,提高了判定非哈密顿可平面图的效率,由此产生了很多3-正则3-连通非哈密顿可平面图的研究成果.根据无向哈密顿图的特征,提出了基本圈的分解、合并、单条公共边连通,原子圈等概念.任何一个简单连通无向图G是哈密顿图,当且仅当,哈密顿圈要么其本身就是一个包含所有顶点的原子圈;要么总是可以分解成若干个原子圈,这些原子圈按照某种次序以单条公共边连通.根据这个充分必要条件,推导出了一个必要条件计算公式.它不仅能处理平面图,也能处理非平面图;甚至能处理某些Grinberg条件不能处理的平面图.此外,对一些实际案例的测试结果验证了充分必要条件和计算公式的有效性.%As an NP-complete problem, Hamiltonian graph problem is one of the main unresolved problems in graph theory.In 1968 Grinberg advanced a necessary condition for Hamiltonian planar graphs,which enhanced the solution of non-Hamiltonian planar graphs and led to a series of research work on 3-regular 3-connected non-Hamiltonian planar graphs. Based on the characteristic of undirected Hamiltonian graph,some new notions about decomposition,mergenea and connection in common edge of basic cycles, as well as atomic cycle are defined. Any a connected simple undirected graph G is a Hamiltonian graph if and only if either theHamiltonian cycle itseff is an atomic cycle which contains every vertex of G or the Hamiltonian cycle can always be decomposed into several atomic cycles which are connected with one another by one common edge in a certain order. A new necessary condition formula is derived from this sufficient and necessary condition which can deal with not only planar graphs but also non-planar graphs, even more those planar graphs which can not be treated by Grinberg condition. Moreover, experimental results on some real Cases demonstrate the effectiveness of this condition and its formula.【总页数】4页(P7-9,69)【作者】侯爱民;郝志峰【作者单位】华南理工大学计算机科学与工程学院,广州510006;东莞理工学院计算机科学与技术系,广东东莞523808;华南理工大学计算机科学与工程学院,广州510006【正文语种】中文【中图分类】O157.5【相关文献】1.求解哈密顿图判定问题的一个新算法 [J], 姜新文2.无割边三正则图三边着色的一个充分必要条件 [J], 翟绍辉;冯永锝3.用矩阵判断哈密顿图的一个充要条件 [J], 姚源果4.无向哈密顿图的自适应遗传算法 [J], 侯爱民;郝志峰;陈小莉;沈丹华5.无圈超图的一个充分必要条件 [J], 段广森;高继梅因版权原因，仅展示原文概要，查看原文内容请购买。

87 J.W.P.Hirschfeld,ed,Surveys in Combinatorics,2001,London Math.Soc. Lecture Note Series288,Cambridge University Press,2001,269–301.List colourings of graphsDouglas R.WoodallAbstractA list colouring of a graph is a colouring in which each vertex v re-ceives a colour from a prescribed list L(v)of colours.This paper aboutlist colourings can be thought of as being divided into two parts.Thefirst part,comprising Sections1,2and6,is about proper colourings,in which adjacent vertices must receive different colours.It is a surveyof known conjectures and results with few proofs,although Section6discusses several different methods of proof.Section1is intended as afirst introduction to the concept of list colouring,and Section2discussesconjectures and results,mainly about graphs for which“ch=χ”.Theother part of the paper,comprising Sections3,4and5,is about im-proper or defective colourings,in which a vertex is allowed to have someneighbours with the same colour as itself,but not too many.Althoughstill written mainly as a survey,this part of the paper contains a numberof new proofs and new conjectures.Section3is about subcontractions,and includes conjectures broadly similar to Hadwiger’s conjecture.Sec-tion4is about planar and related graphs.Section5is also about planarand related graphs,but this time with additional constraints imposedon the lists.1IntroductionList colourings of graphs were introduced independently by Vizing[61],byErd˝o s,Rubin and Taylor[15],and,from a slightly different perspective,byLevow[43].Two excellent articles on them are those by Alon[1]and Tuza [59],and the second of these has been updated by Kratochv´ıl,Tuza and Voigt [42].Readers who are familiar with the content of those articles may preferto skip this section,which is intended as an introduction to list colouring for readers who are unfamiliar with the concept.1.1The basic conceptA vertex-colouring,or just colouring,of afinite simple graph G is an as-signment of a colour to each vertex of G.A colouring is proper if adjacent vertices always get different colours.A graph is k-colourable if it has a proper colouring using at most k different colours.The premise in this classical situation is that we have a palette of k colours available,and any vertex can receive any one of the k colours,subject only tothe restriction that adjacent vertices must get different colours.In contrast,the premise in list-colouring is that every vertex has its own palette of colours,and a vertex may be coloured only with a colour from its own palette.These269270Douglas R.Woodall palettes are called lists—somewhat incongruously,since the term list is usually taken to imply the existence of an ordering,whereas the palettes are simply unordered sets of colours:in other words,they are unordered lists.A list-assignment L to(the vertices of)G is the assignment of a“list”(set)L(v)of colours to every vertex v of G;and a k-list-assignment is a list-assignment such that|L(v)|≥k for every vertex v.If L is a list-assignment to G,then an L-colouring of G is a colouring(not necessarily proper)in which each vertex receives a colour from its own list;we talk loosely of colouring G from its lists.The graph G is k-list-colourable,or k-choosable,if it is properly L-colourable for every k-list-assignment L to G.The chromatic numberχ(G)of G is the smallest number k such that G is k-colourable.The list chromatic number or choosability ch(G)of G,sometimes writtenχlist(G)orχl(G),is the smallest number k such that G is k-choosable. It is evident that ch(G)≥χ(G),since if k<χ(G)then G is not L-colourable when every vertex v of G is given the same list L(v)of k colours.On meeting these ideas for thefirst time,one might think that ch(G)=χ(G)always,since if one wants to colour adjacent vertices with different colours,then it might appear that having different lists on different vertices could only make the task easier.Indeed,there are many situations in which it does make the task easier.For example,if G is a circuit of odd length, or a complete graph,with maximum degree∆,then it is easy to see that χ(G)=∆+1.It follows that ch(G)≥∆+1,since,in particular,if one gives every vertex of G the same list of∆colours,then one cannot colour G properly from these lists.However,this is the only case in which the colouring is not possible:if one gives every vertex v a list L(v)of∆colours,and the lists are not all identical,then G has a proper L-colouring.To see this,choose an edge uv such that L(u)=L(v),colour u with a colour from L(u)\L(v), and then colour the remaining vertices in order round the circuit,or in an arbitrary order if G is complete,but leaving v until last;it is not difficult to see that this can be done in such a way as to form a proper L-colouring of G, as required.However,there are situations in which having different lists can make the colouring impossible.The simplest examples are the complete-bipartite graphs.1.2Complete-bipartite graphsIf one assigns lists{a,b}and{c,d}to the vertices in one partite class of K2,4,and lists{a,c},{a,d},{b,c}and{b,d}to the vertices in the other class, then the vertices cannot be coloured from these lists.In a similar way,if one assigns lists{a,b},{a,c}and{b,c}to the three vertices in each class of K3,3,then there is no colouring from these lists.It follows that these graphs are not2-choosable,despite being bipartite and hence2-colourable;that is, ch(G)>χ(G)=2for these two graphs.It is not difficult to see that ch(G)=3List colourings of graphs271 in each case.These constructions can easily be generalized to give examples of graphs G such that ch(G)>k andχ(G)=2for arbitrary integers k≥2.One such example is the graph K k,k k,where the k vertices of thefirst class are given k disjoint lists of k colours each,and the lists on the k k vertices of the second class are all the possible systems of distinct representatives of thefirst k lists.A smaller example[15]is K r,r,with r= 2k−1k ,where the lists given to the r vertices of each partite class consist of the r different k-subsets of a set of 2k−1colours.In this case,for any k−1of the colours,there is a vertex in each class that has none of those colours in its list.It follows that in any colouring from these lists,whether proper or not,at least k colours must be used on each class;and since there are fewer than2k colours in total,the colouring cannot be proper.The question of how large the choosability of a complete-bipartite graph can be,in terms of its number of vertices,wasfirst posed by Erd˝o s,Rubin and Taylor[15],who proved that ch(K r,r)=log2r+o(log r)as r→∞.They also showed that ch(K7,7)≥4,by exhibiting a list-assignment based on the Fano configuration(reproduced in[29]and in[59,Example0.3]);in contrast, Hanson,MacGillivray and Toft[29]have shown that ch(G)≤3for every bipartite graph G with up to13vertices.For further results about ch(K p,q) see[59,Section1.2].1.3The6-,5-and4-colour theorems for planar graphsIt follows from the above examples that the choosability ch(G)of a graph G is not always equal to its chromatic numberχ(G),and indeed that there is no general upper bound for ch(G)in terms ofχ(G).Thus every question that has ever been asked about graph colourings can be asked again about choosability.If one takes a theorem about colourings,and one changes“colouring”to “choosability”,there are basically three different things that can happen: (i)the theorem remains true and the proof still works,(ii)the theorem remains true but the proof does not work,and(iii)the theorem becomes false.These three possibilities are illustrated rather nicely by the6-colour theorem, the5-colour theorem and the4-colour theorem for planar graphs.Suppose one has proved,presumably by using Euler’s theorem,that every planar graph contains a vertex with degree at most5.Then the6-colour the-orem follows easily by the following argument.Given a hypothetical minimal non-6-colourable planar graph G,choose a vertex v with degree at most5; colour(properly)the vertices of G−v with six colours,which is possible by the minimality of G;and then at least one of the six colours is not present272Douglas R.Woodall on thefive or fewer neighbours of v and so can be used on v.This gives a 6-colouring of G,which is a contradiction.The same argument works equally well to prove that every planar graph is6-choosable:when the time comes to colour v,it makes no difference whether the six colours that are potentially available for v are the same as the ones that were available for the other ver-tices;all that matters is that at least one colour that is potentially available for v has not been used on any neighbour of v.In contrast,the usual proof of the5-colour theorem involves refinements to the above argument that do not extend to choosability.If the vertex v in this argument hasfive neighbours withfive different colours,then there is no colour that one can give to v.So one must ensure that at least two neighbours of v have the same colour,either by using a Kempe interchange of colours to make two colours the same,or by identifying two nonadjacent neighbours of v before colouring G−v in order to ensure that they get the same colour from the outset. Neither of these tricks will work for choosability.Kempe interchanges will not work because they might require a vertex to be recoloured with a colour that is not present in its list;and if all the neighbours of v have different lists then it is not possible to identify two of them in any helpful way.However,the result remains true.Thomassen[58]gave a remarkably simple and elegant proof of the fact that every planar graph is5-choosable.Thomassen’s proof does not use Euler’s formula or Kempe interchanges,and it is arguably shorter than the usual proof of the5-colour theorem,despite proving a much stronger result. (The proof of Theorem5.2of the present paper uses substantially the same method,which is described in Section6.1.3as the boundary method.) Finally,there is the4-colour theorem itself.Here the choosability analogue is false.Thefirst example of a non-4-choosable planar graph was given by Voigt[62],and further examples were given by Gutner[22]and Mirzakhani [45];these last two examples are even3-colourable.Further results about planar graphs are given in Sections4,5and6.1.1; Section6.1.1also discusses graphs in other surfaces.2Graphs for which ch=χAt the present time it is not at all clear for which graphs G it is true that ch(G)=χ(G).Rubin(see[15])characterized2-choosable bipartite graphs, that is,graphs G such that ch(G)=χ(G)=2.But,as Tuza[59]remarks,it seems hopeless tofind a characterization of all graphs G for which ch(G)=χ(G).However,there are certain classes of graphs for which this equation is conjectured to hold.2.1List-colouring conjecturesTo state these conjectures,we need the concepts of edge-choosability and total choosability.These are natural analogues of(vertex-)choosability,andList colourings of graphs273 we now define them.A(proper)total colouring of a multigraph H is an assignment of a colour to every vertex and every edge of H in such a way that no two adjacent vertices or adjacent edges have the same colour,and no vertex has the same colour as an edge incident with it.The total chromatic number χ (H)of H is the smallest integer k such that H has a total colouring using k colours.The total choosability or list total chromatic number ch (H)of H is the smallest integer k such that whenever every vertex and every edge of H is given a list of at least k colours,there exists a total colouring of H in which every vertex and every edge receives a colour from its own list.The edge chromatic number(or chromatic index)χ (H)and the edge choosability ch (H)are defined similarly in terms of colouring edges alone.Let T(H)denote the total graph of H,which has a vertex corresponding to every vertex and every edge of H,with an edge joining two vertices of T(H)whenever the corresponding elements of H are required to be coloured differently in a total colouring of H.The line graph L(H)of H is defined analogously with respect to edge-colourings;it is the subgraph of T(H)in-duced by the vertices representing edges of H.In view of these definitions it is possible,and it is sometimes useful,to think of edge-colourings and to-tal colourings not so much as new types of colourings,but rather as vertex-colourings of restricted classes of graphs,namely line graphs and total graphs. In particular,χ (H)=χ(L(H)),χ (H)=χ(T(H)),ch (H)=ch(L(H)),and ch (H)=ch(T(H)).The following conjecture seems to have been made independently by Vizing, by Gupta,and by Albertson and Collins(see[9,25]).It used to be known as the list-colouring conjecture,abbreviated LCC,but a more specific name now seems appropriate.The List-Edge-Colouring Conjecture(LECC)For every multigraph H, ch (H)=χ (H).An equivalent formulation of the LECC is that ch(G)=χ(G)for every graph G that is the line graph of a multigraph H.Since every line graph is claw-free(that is,it does not have K1,3as an induced subgraph),the following conjecture,due to Gravier and Maffray[20],would imply the LECC.The List-Colouring Conjecture for Claw-Free Graphs For every claw-free graph G,ch(G)=χ(G).The analogous conjecture to the LECC for total colourings was made in-dependently and almost simultaneously by Borodin,Kostochka and Woodall [6],by Juvan,Mohar andˇSkrekovski[35]and by Hilton and Johnson[31]. The List-Total-Colouring Conjecture(LTCC)For every multigraph H, ch (H)=χ (H).274Douglas R.Woodall An equivalent formulation of the LTCC is that ch(G)=χ(G)for every graph G that is the total graph of a multigraph H.The square G2of a graph G is the graph with the same vertex-set as G in which two vertices are adjacent if their distance apart in G is at most2. Note that if G is obtained by placing a vertex in the middle of every edge of a multigraph H,then G2=T(H).Thus the following conjecture(the LSCC), made by Kostochka and Woodall[36],implies the LTCC;indeed,the LTCC is equivalent to the special case of the LSCC for bipartite graphs in which every vertex in one partite set has degree2.The List-Square-Colouring Conjecture(LSCC)For every graph G, ch(G2)=χ(G2).Finally,Ohba[46]proved that for every graph G there exists an integer n0 such thatch(G+K n)=χ(G+K n)for every n≥n0,(2.1) where+denotes“join”;and he made the following conjecture,which would imply that this is true with n0=max{0,|V(G)|−2χ(G)−1}.Ohba’s Conjecture[46]If|V(G)|≤2χ(G)+1,then ch(G)=χ(G).Before discussing what is known about these conjectures,we shall consider three more conjectures.2.2The(a:b)-choosability conjecturesLet F and G be(simple)graphs such that V(G)={v1,...,v n}.We say that F is an inflation of G if V(F)can be written as a disjoint union V(F)= V1∪...∪V n in such a way that if x∈V i and y∈V j then xy∈E(F)if and only if i=j or v i v j∈E(G).(So to inflate a graph is to replace each vertex by a complete graph.)If|V i|=t for all i then we write F=G(t)and call it a uniform inflation of G.(Another way of looking at G(t)is as the lexicographic product or composition G[K t]of G and K t,also called the wreath product G∗K t.)Following Erd˝o s,Rubin and Taylor[15],we say that a graph is(a:b)-choosable if,whenever each vertex is assigned a list of a colours,we can give each vertex a set of b colours from its list in such a way that adjacent ver-tices get disjoint sets of colours;so(a:1)-choosable means the same as a-choosable.It is easy to see that G is(a:b)-choosable if G(b)is a-choosable, and Kostochka and Woodall[36]conjectured that the converse holds;this is the(a:b)-choosability equivalence conjecture,below.Erd˝o s,Rubin and Tay-lor[15]asked whether,for a,b,t∈N,every graph that is(a:b)-choosable is necessarily(ta:tb)-choosable.The only pair(a,b)for which this is known to be true[60]is(a,b)=(2,1).Nevertheless it is widely believed to be true for all(a,b).This is thefirst of the following conjectures,which appeared in this form in[36].List colourings of graphs275 The Weak(a:b)-Choosability Conjecture(Weak(a:b)-CC).For all a,b,t∈N,if a graph G is(a:b)-choosable,then G is(ta:tb)-choosable.The Strong(a:b)-Choosability Conjecture(Strong(a:b)-CC).For all a,b,t∈N,if a graph G is(a:b)-choosable,then G(t)is(ta:b)-choosable.The(a:b)-Choosability Equivalence Conjecture((a:b)-CEC).For all a,b∈N,a graph G is(a:b)-choosable if and only if G(b)is a-choosable.It is easy to see that the strong(a:b)-CC implies the weak(a:b)-CC,and if the(a:b)-CEC is true then the other two conjectures are equivalent.For certain families of graphs satisfying ch=χ,all three conjectures are true: Theorem2.1([36])Let G be a graph such that ch(G(t))=χ(G(t))for all t∈N.Then all three(a:b)-choosability conjectures hold for G.The classes of line graphs,claw-free graphs and squares are all closed under uniform inflations.Thus,by Theorem2.1,the truth of the(a:b)-choosability conjectures for these classes of graphs would follow from the truth of the LECC, the list-colouring conjecture for claw-free graphs,and the LSCC,respectively. In contrast,the class of total graphs is not closed under uniform inflations, and so the truth of the LTCC would not apparently imply the truth of the (a:b)-choosability conjectures for total graphs.This is why it seemed useful to us to formulate the LSCC,as a stronger version of the LTCC which does have implications for the(a:b)-choosability conjectures.2.3Theorems proving that ch=χWithin the last few years,great impetus has been given to the study of choosability by the papers of Alon and Tarsi[2]and Galvin[18],which in-troduced two new methods of proof,the Alon–Tarsi method and the kernel method(see Sections6.2.1and6.2.2).However,we start by describing results that can be proved without the use of these methods.One easy result is that ch(G)=χ(G)=ω(G)for every interval graph G, whereω(G)is the order of a largest clique in G.I do not recall seeing this result in the literature,but a proof is sketched near the start of Section6.2.Both Vizing[61]and Erd˝o s,Rubin and Taylor[15]proved that ch(G)=χ(G)=2if G is a circuit of even length,and(as already remarked)Rubin went further and characterized graphs for which ch(G)=χ(G)=2.It is easy to see that ch(G)=χ(G)=3if G is a circuit of odd length,so that ch(G)=χ(G) for all circuits.By a simple application of Hall’s theorem(Section6.1.2),Erd˝o s,Rubin and Taylor[15]proved that the complete k-partite graph K2,2,...,2is k-choosable, thereby showing that ch(G)=χ(G)if G has aχ(G)-colouring in which every colour class has at most two vertices.(This holds,in particular,if G does not276Douglas R.Woodall contain a set of three independent vertices.)Gravier and Maffray[21]extended this by showing that ch(G)=χ(G)ifχ(G)≥3and G has aχ(G)-colouring in which no colour class has more than three vertices and at most two colour classes have three vertices.They used this to prove that ch(G)=χ(G)if G is claw-free and|V(G)|≤2χ(G)+2;this shows that Ohba’s conjecture is true (and not sharp)for claw-free graphs.Enomoto,Ohba,Ota and Sakamoto[14] pointed out that the complete k-partite graph K4,2,...,2is not k-choosable if k is even,thereby showing that the upper bound on|V(G)|in Ohba’s conjecture is sharp in general.They also proved Ohba’s conjecture in the case when at most one colour class has more than two vertices.Gravier and Maffray[20]proved the list-colouring conjecture for elementary claw-free graphs containing no K4,where a graph is elementary if its edges can be coloured with two colours in such a way that every chordless path of length two has its two edges coloured differently.Ohba[46]proved that if G is a graph that has aχ(G)-colouring in which the second-largest colour class hasα2vertices,and if(α2−1)|V(G)|≤α2χ(G), then ch(G)=χ(G).From this it is easy to see that(2.1)holds(for every graph G)with n0=max{0,(α2−1)|V(G)|−α2χ(G)}.Kostochka and Woodall[36]proved that ch(G)=χ(G)if G is an inflation of a graph with at mostfive vertices or is the inflation of the square of a graph with at most seven vertices;this proves all the(a:b)-choosability conjectures for such graphs,and it proves the LSCC for every inflation of a graph with at most seven vertices.All of the proofs mentioned in the last four paragraphs use Hall’s theorem(Section6.1.2)to deal with some special cases,but some of them require a great deal of ingenuity in addition.An easy inductive argument proves the LECC,LTCC and LSCC for any multigraph whose underlying simple graph G0is a forest;indeed,if G is such a multigraph then ch (G)=χ (G)=∆(G),ch (G)=χ (G)=∆(G)+1and ch(G2)=χ(G2)=∆(G0)+1,where∆denotes maximum degree.Because T(K3)=L(K4)(the octahedron),if G is a multigraph with underlying simple graph K3then there is a multigraph H with at most four vertices such that T(G)=L(H),and so the truth of the LECC for H(proved in[47])implies the truth of the LTCC for G;it follows that the LTCC holds for multigraphs with at most three vertices.Juvan,Mohar and Thomas[34]proved the LECC for series-parallel graphs (but not for series-parallel multigraphs);specifically,they proved that ch (G)=χ (G)=∆(G)for a series-parallel simple graph G.This proves the LECC also for(simple)outerplanar graphs,since outerplanar graphs are series-parallel. The LTCC is also known to be true for outerplanar graphs[33].Thefirst of the two new methods of proof mentioned above was the method of Alon and Tarsi[2](see Section6.2.1).Almost as soon as this method became available,Fleischner and Stiebitz[16]used it to prove that if G is a4-regular graph on3n vertices whose edges can be decomposed into a hamiltonian circuit and n pairwise vertex-disjoint triangles,then ch(G)=χ(G)=3.(They statedList colourings of graphs277 only thatχ(G)=3,but their proof shows also that ch(G)=3.) Ellingham and Goddyn[13]explored the Alon–Tarsi method in greater depth and used it to prove that if G is a2-connected3-regular planar graph then ch (G)=χ (G)=3.More generally,they proved that if G is a d-regular planar multigraph then ch (G)=d if and only ifχ (G)=d.This proves all the(a:b)-choosability conjectures for line graphs of edge-d-colourable d-regular planar multigraphs.H¨a ggkvist and Janssen[26]used the Alon–Tarsi method to prove,among other results,that ch (K n)≤n for every n,which implies that ch (K n)=χ (K n)when n is odd.A very recent result of Prowse and Woodall[49]is that ch(G)=χ(G), and all the(a:b)-choosability conjectures hold,if G is a power of a circuit, G=C p n;that is,the vertices of G are v1,...,v n,and each vertex v i is adjacent to v i−p,...,v i−1,v i+1,...,v i+p,where subscripts are taken module n.The other new method of proof mentioned above is the kernel method(see Section6.2.2).This was developed by Galvin[18],who used it to prove that ch (G)=χ (G)for every bipartite multigraph G.This proves the LECC for bipartite multigraphs,and it also proves all the(a:b)-choosability conjectures for their line graphs.It also implies that ch (G)≤∆(G)+2,which proves the LTCC for any bipartite multigraph G for whichχ (G)>∆(G)+1.Quite apart from the new method that it contained,another interesting feature of Galvin’s proof is that he proved that ch (G)=χ (G)directly,without using(or even mentioning)the well-known fact thatχ (G)=∆(G)when G is bipartite.Most other theorems of this type have been proved byfinding some sort of formula forχ (G),and then proving that G is list-colourable from lists of this size.However,Plantholt and Tipnis[48]used a similar approach to Galvin’s to prove the LECC for every multigraph whose underlying simple graph is of the form“bipartite plus one edge”,and also for every multigraph containing a vertex v with degree at most6such that G−v is bipartite.Alternative presentations of Galvin’s proof have been given by Slivnik[57] and by Borodin,Kostochka and Woodall[6].These last authors extended the method to prove that if each edge uw of G is given a list of at least max{d(u),d(w)}colours,then the edges of G can be coloured from these lists.They further used this to prove the sharp result that ch (G)≤ 32∆(G) forevery multigraph G,which is the choosability analogue of the classic theorem of Shannon[53]thatχ (G)≤ 3∆(G) for every multigraph G.(The conjecturethat ch (G)≤ 32∆(G) if∆(G)≥4is stated in[6]but remains unproved.)More relevantly,in the context of the present conjectures,various results are proved in[6]about the choosability of a graph G embedded in a surface of nonnegative characteristic,of which the simplest to state is that if∆(G)≥12 then ch (G)=χ (G)=∆(G)and ch (G)=χ (G)=∆(G)+1.A multigraph is called line-perfect if its line graph is perfect.By a result of Maffray[44],a multigraph is line-perfect if and only if every block of it is bipartite or has underlying simple graph of the form K4or K1,1,p.Peterson278Douglas R.Woodall and Woodall[47]used the results of[18]and[6]to prove the LECC for line-perfect multigraphs.Woodall[66]extended this to multigraphs in which every block is line-perfect or a multicircuit,where a multicircuit is a multigraph whose underlying simple graph is a circuit(a connected2-regular graph).It follows that the(a:b)-choosability conjectures all hold for the line graphs of such multigraphs.Kostochka and Woodall[37,38]proved the LTCC for multicircuits.It may give some indication of the different levels of difficulty of the two conjectures to note that the proof of the LECC for multicircuits takes about a page,while the proof of the LTCC for multicircuits takes two20-page papers(one based on the kernel method and one based on the Alon–Tarsi method).Another difference is that while the truth of the LECC for multicircuits implies the truth of all the(a:b)-choosability conjectures for their line graphs,we have signally failed to prove the truth of the(a:b)-choosability conjectures for total graphs of multicircuits in general,although we did prove it for a fairly wide class of multicircuits of even order in[36].3Subcontractions and defective choosability;analogues of Hadwiger’s conjectureA graph H is a subcontraction or minor of a graph G if one can form an isomorphic copy of H from G by contracting edges and deleting edges and vertices.A graph G is called H-minor-free if it does not have H as a minor.Hadwiger’s conjecture[23,24]is that every K r+1-minor-free graph is r-colourable;this is now known to be true for r≤5[52].The analogous statement cannot hold for choosability,since,as we have already remarked,there are planar(hence,K5-minor-free)graphs that are not 4-choosable.However,there is some evidence that complete-bipartite graphs play a similar role in choosability to the role played by complete graphs in the theory of ordinary colourings.For example,a famous theorem of Haj´o s[27]says that every graph that is not r-colourable can be obtained from K r+1by a sequence of three types of op-erations.The analogous statement for choosability is false,the simplest coun-terexamples being the complete-bipartite graphs.However,Gravier[19]has proved that every non-r-choosable graph can be obtained from non-r-choosable complete-bipartite graphs by a sequence of essentially the same three types of operations(with one minor and natural change,namely,that nonadjacent ver-tices may only be identified if they have the same list in some r-list-assignment L for which the graph is not L-choosable).Tables1and2in Section4.1also suggest(rather superficially)that K r,s-minor-free graphs may behave better than K r-minor-free graphs with respect to defective choosability,a concept that we now define.In a vertex-coloured graph,the defect def(v)of a vertex v is the number of vertices adjacent to v that have the same colour as v;so a colouring is proper。