具有较大四独立集的色唯一的三部图
|
摘要
设G是简单图,■表示图G的补图,用P(G,λ)表示图G的色多项式.若P(G,λ)=P(H,λ),则称G与H是色等价的,简记为H～G.令[G]={H|H～G}.若[G]={G},称G是色唯一的.设K_(n,n,n)是一个完全三部图且各部分顶点数均为n.图G=K_(n,n,n)-S表示从完全三部图K_(n,n,n)中删去边集S所得的图.本文证明了一些具有较大四独立集的三部图是色唯一的.
For any graph G,we denote by ■ the complement and by P(G,λ)the chromatic polynomial of G.Two graphs Gand Hare said to be equivalent,simply denoted by G～H,if P(G,λ)=P(H,λ).Let[G]={H|H～G}.Gis said to be chromatically unique if[G]={G}.Let K_(n,n,n) be a complete tripartite graph and S be a set of some s edges in Kn_(n,n,n).Denote by G=K_(n,n,n)-Sthe graph obtained fromKn,n,nby deleting all edges in S.In this paper,we give some chromatically unique tripartite graphds with large 4-independent number.
For any graph G,we denote by ■ the complement and by P(G,λ)the chromatic polynomial of G.Two graphs Gand Hare said to be equivalent,simply denoted by G～H,if P(G,λ)=P(H,λ).Let[G]={H|H～G}.Gis said to be chromatically unique if[G]={G}.Let K_(n,n,n) be a complete tripartite graph and S be a set of some s edges in Kn_(n,n,n).Denote by G=K_(n,n,n)-Sthe graph obtained fromKn,n,nby deleting all edges in S.In this paper,we give some chromatically unique tripartite graphds with large 4-independent number.
引文
[1]Bondy J A,Murty U S R.Graph Theory with Application[M].New York:American Elsevier,1976.
[2]Dong F M,Koh K M,Teo K L,et al.Sharp bounds for the number of 3-independent partition and chromaticity of bipartite graphs[J].Graph Theory,2001,37:48-77.
[3]Koh K M,Teo K L.The search for chromatically unique graphs[J].Graphs and Combin.,1990,6:259-285.
[4]Read R C,Tutte W T.“Chromatic polynomials”,Selected Topics in Graph TheoryIII[M].New York:Academic Press,1998:15-42.
[5]Teo P C,Koh K M.The chromaticity of complete bipartite graphs with at most one edge deleted[J].Graph Theory,1990,14:89-99.
[6]Zhao H X.Chromaticity and adjoint polynomials of graphs[D].The Netherlands,Wohrmann Print Service.2005.
[7]Liu R Y.Adjoint polynomials and chromatically unique graphs[J].Discrete Math.,1997,172:85-92.
[8]Chen X.Some families of chromatically unique bipartite graphs[J].Discrete Math.,1998,184:245-253.
[9]Peng Y H.Chromatic uniqueness of certain bipartite graphs[J].Discrete Math.,1991,94:129-140.
[10]Roslan H,Peng Y H.Chromaticity of bipartite graphs with seven edges deleted[J].Ars Combinatoria,2011,99:257-277.
[11]Chia C L,Ho C K.Chromatic equivalence classes of complete tripartite graphs[J].Discrete Math.,2009,309(1):134-143.
[12]Lau G C,Peng Y H,Chu H H.Chromatic uniqueness of certain complete 4-partite graphs[J].Ars Combinatoria.,2011,99:377-382.
[2]Dong F M,Koh K M,Teo K L,et al.Sharp bounds for the number of 3-independent partition and chromaticity of bipartite graphs[J].Graph Theory,2001,37:48-77.
[3]Koh K M,Teo K L.The search for chromatically unique graphs[J].Graphs and Combin.,1990,6:259-285.
[4]Read R C,Tutte W T.“Chromatic polynomials”,Selected Topics in Graph TheoryIII[M].New York:Academic Press,1998:15-42.
[5]Teo P C,Koh K M.The chromaticity of complete bipartite graphs with at most one edge deleted[J].Graph Theory,1990,14:89-99.
[6]Zhao H X.Chromaticity and adjoint polynomials of graphs[D].The Netherlands,Wohrmann Print Service.2005.
[7]Liu R Y.Adjoint polynomials and chromatically unique graphs[J].Discrete Math.,1997,172:85-92.
[8]Chen X.Some families of chromatically unique bipartite graphs[J].Discrete Math.,1998,184:245-253.
[9]Peng Y H.Chromatic uniqueness of certain bipartite graphs[J].Discrete Math.,1991,94:129-140.
[10]Roslan H,Peng Y H.Chromaticity of bipartite graphs with seven edges deleted[J].Ars Combinatoria,2011,99:257-277.
[11]Chia C L,Ho C K.Chromatic equivalence classes of complete tripartite graphs[J].Discrete Math.,2009,309(1):134-143.
[12]Lau G C,Peng Y H,Chu H H.Chromatic uniqueness of certain complete 4-partite graphs[J].Ars Combinatoria.,2011,99:377-382.