List Bouble-Critical Graphs?

LI Zhonghua,WU Baoyindureng,AN Xinhui,LIU Fengxia

(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830046,China)

1 Introduction

All graphs considered in this paper are f i nite and simple.For notation and terminology not def i ned here,we refer to West[4].LetG=(V,E)be a graph.The cardinalities ofVandEare theorderandsizeofG.LetKnbe the complete graph of ordern.Letvbe a vertex ofG.The neighborhood ofv,denoted byNG(v),is the set of vertices adjacent tovinG.The degree ofv,denoted bydG(v),is the number of edges incident withvinG.SinceGis simple,dG(v)=|NG(v)|.If there is no confusion,we useN(v)andd(v)for the neighborhood and degree ofvinstead ofNG(v)anddG(v),respectively.We use δ(G)to denote the minimum degree ofG.An independent setSofGis a set such that the induced graphG[S]is edge-empty.The maximum integerkfor which there exists an independent setSofGof cardinalitykis the independence number ofGand is denoted α(G).

A proper vertex coloring ofGis an assignmentcof integers to the vertices ofGsuch thatc(u),c(v)if the verticesuandvare adjacent inG.Ak-coloring is a proper vertex coloring usingkcolors.Thechromatic numberofG,χ(G),is the smallest integerksuch thatGhas ak-coloring.A graphGwith χ(G)=kis calledk-chromatic.

A graphGis calledcriticalif χ(H)<χ(G)for every proper subgraphHofG.It is well-known that δ(G)≥χ(G)?1 for any critical graphG.A graphGis calleddouble-criticalifGis connected and χ(G?u?v)=χ(G)?2 for any two adjacent verticesu,v∈V(G).It is easy to see that every double-critical graph is critical.A long-standing conjecture,due to Erd?os and Lov′asz[1],states that the complete graphs are the only double-critical graphs.This conjecture is known as theDouble-Critical Graph Conjecture.The Double-Critical Graph Conjecture is easily seen to be true for double-criticalk-chromatic graphs withkat most 4.Stiebitz[5]proved the conjecture to hold fork=5,but it still remains open for all integerskgreater than 5.

A connected graphGis callededge double-criticalif it contains some pairs of nonadjacent edges,and χ(G?e1?e2)=χ(G)?2 for any two nonadjacent edgese1,e2∈E(G).Kawarabayashi et al.[2]and later,Lattanzio[3]proved that the complete graphs are the only edge double-critical graphs.

A list assignmentLto the vertices ofGis the assignment of a setL(v)of colors to every vertexvofG.IfGhas a proper coloringcsuch thatc(v)∈L(v)for all verticesv,then we sayGisL-colorable.We say thatGisk-list colorable ork-choosable if it isL-colorable for every list assignmentLsatisfying|L(v)|=kfor all verticesv.Thechoice numberofG,ch(G),is the smallest integerksuch thatGisk-choosable.It is obvious that χ(G)≤ ch(G).

The def i nition of list double critical graph f i rst appeared in the doctoral thesis of Pedersen[6].A graphGis calledlist double-criticalifGis connected and ch(G?u?v)=ch(G)?2 for any two adjacent verticesu,v∈V(G).He also posed the question of whether the complete graphs are the only list double-critical graphs,and proved this is true for graphs with chromatic number at most four.Now we formulate the following conjecture.

Conjecture 1A graph G is list double-critical if and only if it is a complete graph.

A short and self-contained alternative proof of Pedersen’s theorem is given in the next section.Given the difficulty in settling Conjecture 1 fork≥5 we will prove the following results in Section 2.

Theorem 1LetGbe a connected graph.If ch(G?u?v)=ch(G)?2 for any verticesu,v∈V(G),then it is a complete graph.

A connected graphGis calledlist edge double-criticalif it contains some pairs of nonadjacent edges,and ch(G?e1?e2)=ch(G)?2 for any two nonadjacent edgese1,e2∈E(G).We shall prove that

Theorem 2A graphGwith ch(G)=kis list edge double-critical if and only ifG?Kk,providedk≥4.

2 The Proofs

We begin with the following lemma.Its proof is straightforward,and so is omitted.

Lemma 1IfGis list double-critical,then the following holds:

(1)ch(G?u)=ch(G)?1 for any vertexu∈V(G),(2)δ(G)≥k?1.

ProofIt is clear that all complete graphs are list double-critical.Now suppose that the graphGis list doublecritical andch(G)=k(k≤4).Ifk∈{1,2},then it is trivial to see thatG?Kk.

Ifk=3,then δ(G)≥2 by Lemma 1.For an edgeuv∈E(G),since ch(G?u?v)=ch(G)?2=1,V(G){u,v}is an independent set ofG.Moreover,since δ(G)≥ 2,every vertex inV(G){u,v}is adjacent touandv.This implies that|V(G){u,v}|=1,and thusG?K3.Otherwise,we can take two verticesx,y∈V(G?u?v),andvyis an edge ofG?u?x.It follows that ch(G?u?x)≥2.But,sinceGis list double-critical,ch(G?u?x)=ch(G)?2=1,a contradiction.

Now let us consider the case whenk=4.We claim thatGcontainsK3as a subgraph.Suppose it is false.Letu,vbe two adjacent vertices ofG.ThenNG(u)∩NG(v)=?,NG(u)andNG(v)are independent sets ofG.LetLbe an arbitrary list-assignment ofGsuch that|L(x)|=3 for everyx∈V(G).We coloruby a color fromL(u),sayc1,and then colorvby a colorc2∈L(v){c1}.Def i ne a list assignmentL'ofG?u?vbyL'(u')=L(u'){c1}ifu'∈NG(u),L'(v')=L(v'){c2}ifv'∈NG(v),andL'(x)=L(x)if for any remaining vertexx.Clearly,|L'(x)|≥2 for all vertices ofG?u?v.Since ch(G?u?v)=ch(G)?2=2,G?u?vhas anL'-coloringc'.One easily extendc'to anL-coloring ofGby coloringuandvbyc1andc2,respectively.Thusch(G)≤3,which contradicts thatch(G)=4.This proves the claim.

So,letG[{u,v,w}]?K3.By an argument similar to the one applied in the casek=3,V(G){u,v,w}is an independent set ofG,and since δ(G)≥ 4?1=3,all vertices ofV(G){u,v,w}are adjacent to each ofu,v,w.So,to showG?K4,it suffices to prove that|V(G){u,v,w}|=1.If it is not,letx,ybe two vertices inV(G){u,v,w}.Note that ch(G?w?y)≥ch(G[{u,v,x}])=ch(K3)=3.However,sinceGis list double-critical,ch(G?w?y)=ch(G)?2=2,a contradiction.Therefore,G?K4.The proof is complete.

In the proof of Theorem 1,we apply the following lemma,which is very useful in studying list coloring of graphs,see[7–9].

Lemma 2(Kierstead[10]) A graphGisk-choosable ifGisL-colorable for everyk-list assignmentLsuch thatL(v)|<|V|.

ProofofTheorem1LetGbeagraphofordernandch(G)=k.ByLemma 1,there existsa(k?1)-listassignmentLofGsuch that

Claim 1=?for any two non-adjacent verticesu,v∈V(G).

SupposeL(u)∩L(v),? for some two non-adjacent verticesuandvinG,and letcdenote an element ofL(u)∩L(v).Def i ne a list assignmentL'by lettingL'(x)=L(x){c}for any vertexx∈V(G?u?v).Since ch(G?u?v)=ch(G)?2=k?2,G?u?vhas anL'-coloringf'.By coloringuandvby the colorc,one can extendf'to anL-coloring ofG.This contradicts thatGis notL-colorable.Thus,the claim is true.

LetSbe an independent set ofGwith|S|=α(G).By Claim 1 and Lemma 2,we have

i.e.,k?1<χ(G)≤ch(G)=k,which implies that χ(G)=ch(G)=k.

Now suppose,on the contrary,thatGis not a complete graph.Letfbe ak-coloring ofG,and letxandybe two vertices with the same color underf.The existence of such a pair of vertices is guaranteed by fact thatGis not complete.It is easy to see that χ(G?x?y)≥χ(G)?1.Combining this withch(G?x?y)≥χ(G?x?y),we have

a contradiction.This proves Theorem 1.

To prove Theorem 2,we need the following lemmas.Its proof is straightforward,and so is omitted.

Lemma 3IfGis list edge double-critical andch(G)=k≥4,then the following results holds:

(1)ch(G?e)=ch(G)?1 for any edgee∈E(G),(2)δ(G)≥k?1.

Let us denote byK2?kthe completek-partite graph with each part containing exactly two vertices.Erd?os[11]et al.proved thatch(K2?k)=k= χ(K2?k).It implies the following result of Gravier and Maf f ray[12].

Lemma 4(Gravier and Maf f ray[12]) IfGis the complement of a triangle-free graph,thench(G)=χ(G).

Proof of Theorem 2LetG?Kkfor somek≥4,ande1ande2be its two nonadjacent edges.By Lemma 4,ch(G?e1?e2)=k?2.HenceGis list edge double-critical.Conversely,suppose thatGis list edge double-critical andch(G)=k(k≥4).By Lemma 3,δ(G)≥k?1≥3.It follows that for any two verticesu,v∈V(G),there exist two distinct verticesx,y∈V(G),such thatux,vy∈E(G).SinceG?u?vis a subgraph ofG?ux?vy,

Thusch(G?u?v)=ch(G)?2.By Theorem 1,GKk.

References：

[1]Erd?os P.In Theory of Graphs[M].New York:Academic Press,1968:361.

[2]Kawarabayashi K,Pedersen A S,Toft B.Double-critical graphs and complete minors[J].Electron J Combin,2010,17:1-27.

[3]Lattanzio J J.Edge double-critical graphs[J].J Math Stat,2010,6:357-358.

[4]West D B.Introduction to Graph Theory,Second Edition[M].Upper Saddle River:Prentice Hall,NJ,2001.

[5]Stiebitz M.K5is the only double-critical 5-chromatic graph[J].Discrete Math,1987,64:91-93.

[6]Pedersen A S.Contributions to the Theory of Colourings,Graph Minors,and Independent Sets[D].Odense:University of Southern Denmark,2011.

[7]He W,Zhang L,Cranston D W,et al.Choice number of complete multipartite graphsK3?3,2?(k?5),1?2andK4,3?2,2?(k?6),1?3[J].Discrete Math,2008,308:5871-5877.

[8]Ohba K.On chromatic-choosable graphs[J].J Graph Theory,2002,40:130-135.

[9]Shen Y,He W,Wang Y,et al.On choice number of some complete multipartite graphs and Ohba’s conjecture[J].Discrete Math,2008,308:136-143.

[10]Kierstead H A.On the choosability of complete multipartite graphs with part size three[J].Discrete Math,2000,211:255-259.

[11]Erd?os P,Rubin A L,Taylor H.Choosability in graphs[J].Congr Num,1979,26:125-157.

[12]Gravier S,Maf f ray F.Graphs whose choice number is equal to their chromatic number[J].J Graph Theory,1998,27:87-97.