A Matrix Approach to List Coloring problems
详细信息 查看官网全文
- 英文论文题名：A Matrix Approach to List Coloring problems
- 论文作者：Meirong Xu ; Yige Zhao
- 英文论文作者：Meirong Xu ; Yige Zhao ; School of Mathematical Sciences ; University of Jinan
- 年：2017
- 作者机构：School of Mathematical Sciences,University of Jinan;
- 英文论文关键词：List coloring ; Algorithm ; Semi-tensor product
- 会议召开时间：2017-07-26
- 会议录名称：第36届中国控制会议论文集（A）
- 英文会议录名称：Proceedings of the 36th Chinese Control Conference（A）
- 语种：英文
- 分类号：O157.5
- 学会代码：KZLL
- 会议名称：第36届中国控制会议
- 会议地点：中国辽宁大连
- 主办单位：中国自动化学会控制理论专业委员会
- 学会名称：中国自动化学会控制理论专业委员会
- 页数：5
- 文件大小：215k
- 原文格式：D
- 会议级别：全国
摘要
This paper investigates the list coloring problem, and presents a number of new results and algorithms. By using the matrix semi-tensor product, the list coloring problem is studied, and three necessary and sufficient conditions are proposed, based on which an algorithm is designed to find all the list coloring schemes for any simple graph. In addition, the effectiveness of the results/algorithms presented in this paper is shown by one illustrative example.
This paper investigates the list coloring problem, and presents a number of new results and algorithms. By using the matrix semi-tensor product, the list coloring problem is studied, and three necessary and sufficient conditions are proposed, based on which an algorithm is designed to find all the list coloring schemes for any simple graph. In addition, the effectiveness of the results/algorithms presented in this paper is shown by one illustrative example.
This paper investigates the list coloring problem, and presents a number of new results and algorithms. By using the matrix semi-tensor product, the list coloring problem is studied, and three necessary and sufficient conditions are proposed, based on which an algorithm is designed to find all the list coloring schemes for any simple graph. In addition, the effectiveness of the results/algorithms presented in this paper is shown by one illustrative example.
引文
[1]N.Barnier,P.Brisset,Graph coloring for air traffic flow management,Annals of Operations Research,130(1-4):163-178,2004.
[2]K.Giaro,M.Kubale,and P.Obszarski,A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints,Discrete Applied Mathematics,157(17):3625-3630,2009.
[3]A.Gamst,Some lower bounds for a class of frequency assignment problems,IEEE Trans.of Vehicular Technology,35(1):8-14,1986.
[4]V.Vizing,Coloring the vertices of a graph in prescribed colors,Diskret.Analiz.,29:3-10,1976.(in Russian.)
[5]P.Erdo¨s,A.Rubin,H.Taylor,Choosability in graphs,Congr.Numer.,26:125-157,1980.
[6]T.Zeitlhofer,B.Wess.List-coloring of interval graphs with application to register assignment for heterogenous register-set architectures.Signal Processing,83:1411-1425,2003.
[7]K.Ramachandran,E.Belding,K.Almeroth,M.Buddhikot.Interference-aware channel assignment in multi-radio wireless mesh networks.25th IEEE International Conference on Computer Communications,Proceedings,1-12,2006.
[8]F.Galvin.The list chromatic index of a bipartite multigraph.Journal of Combinatorial Theory,Series B,63:153-158,1995.
[9]T.Jensen,B.Toft.Graph coloring problems.New York:Wiley,1995.
[10]M.Voigt.List colorings of planar graphs.Discrete Mathematics,120:215-219,1993.
[11]R.Ha¨gkvist,A.Chetwynd.Some upper bounds on the total and list chromatic numbers of multigraphs.Journal of Graph Theory,16:503-516,1992.
[12]R.Ha¨gkvist,J.Janssen.New bounds on the list-chromatic index of the complete graph and other simple graphs.Combinatorics,Probability and Computing,6:295-313,1997.
[13]A.Chetwynd,R.Haggkvist.A note on list-colorings.Journal of Graph Theory,13:87-95,1989.
[14]A.Kostochka.List edge chromatic number of graphs with,large girth.Discrete Mathematics,101:189-201,1992.
[15]D.Cheng,H.Qi,Semi-tensor product of matrices theory and applications,Science Press,Beijing,2007(in Chinese).
[16]D.Cheng,H.Qi,Z.Li,Analysis and Control of Boolean Networks:A Semi-tensor Product Approach,Springer,2011.
[17]D.Cheng,H.Qi,A linear representation of dynamics of Boolean networks,IEEE Trans.Aut.Contr.,55(10):2251-2258,2010.
[18]D.Cheng,H.Qi,Controllability and observability of Boolean control networks,Automatica,45(7):1659-1667,2009.
[19]D.Cheng,Z.Li,H.Qi,Realization of Boolean control networks,Automatica,46(1):62-69,2010.
[20]D.Cheng,Disturbance decoupling of Boolean control networks,IEEE Trans.Aut.Contr.,56(1):2-10,2011.
[21]D.Cheng,H.Qi,Z.Li,J.Liu,Stability and stabilization of Boolean networks,Int.J.Robust Nonlinear Contr.,21(2):134-156,2011.
[22]F.Li,J.Sun,Boolean derivative calculation with application to fault detection of combinational circuits via the semi-tensor product method,Automatica,48(4):688-693,2012.
[23]H.Li,Y.Wang,Controllability of Boolean control networks with time delays in state,Automatica,47(3):603-607,2011.
[24]P.Guo,Y.Wang,H.Li.Algebraic formulation and strategy optimization for a class of evolutionary networked games via semi-tensor product method.Automatica,49(11):3384-3389,2013.
[25]Y.Wang,C.Zhang,Z.Liu,A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems,Automatica,48(7):1227-1236,2012.
[26]M.Xu,Y.Wang,A.Wei.Robust graph coloring based on matrix semi-tensor product with application to examination timetabling.Control Theory and Technology,12(2):187-197,2014.
[27]M.Xu,Y.Wang.T-coloring of graphs with application to frequency assignment in cellular mobile networks,Proceedings of the 33rd Chinese control conference Nanjing,China,July,2536-2541,2014.
[28]Y.Liu,W.Zhang,Boolean Methodology,Shanghai Technology Literature Press,1993(in Chinese).
[2]K.Giaro,M.Kubale,and P.Obszarski,A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints,Discrete Applied Mathematics,157(17):3625-3630,2009.
[3]A.Gamst,Some lower bounds for a class of frequency assignment problems,IEEE Trans.of Vehicular Technology,35(1):8-14,1986.
[4]V.Vizing,Coloring the vertices of a graph in prescribed colors,Diskret.Analiz.,29:3-10,1976.(in Russian.)
[5]P.Erdo¨s,A.Rubin,H.Taylor,Choosability in graphs,Congr.Numer.,26:125-157,1980.
[6]T.Zeitlhofer,B.Wess.List-coloring of interval graphs with application to register assignment for heterogenous register-set architectures.Signal Processing,83:1411-1425,2003.
[7]K.Ramachandran,E.Belding,K.Almeroth,M.Buddhikot.Interference-aware channel assignment in multi-radio wireless mesh networks.25th IEEE International Conference on Computer Communications,Proceedings,1-12,2006.
[8]F.Galvin.The list chromatic index of a bipartite multigraph.Journal of Combinatorial Theory,Series B,63:153-158,1995.
[9]T.Jensen,B.Toft.Graph coloring problems.New York:Wiley,1995.
[10]M.Voigt.List colorings of planar graphs.Discrete Mathematics,120:215-219,1993.
[11]R.Ha¨gkvist,A.Chetwynd.Some upper bounds on the total and list chromatic numbers of multigraphs.Journal of Graph Theory,16:503-516,1992.
[12]R.Ha¨gkvist,J.Janssen.New bounds on the list-chromatic index of the complete graph and other simple graphs.Combinatorics,Probability and Computing,6:295-313,1997.
[13]A.Chetwynd,R.Haggkvist.A note on list-colorings.Journal of Graph Theory,13:87-95,1989.
[14]A.Kostochka.List edge chromatic number of graphs with,large girth.Discrete Mathematics,101:189-201,1992.
[15]D.Cheng,H.Qi,Semi-tensor product of matrices theory and applications,Science Press,Beijing,2007(in Chinese).
[16]D.Cheng,H.Qi,Z.Li,Analysis and Control of Boolean Networks:A Semi-tensor Product Approach,Springer,2011.
[17]D.Cheng,H.Qi,A linear representation of dynamics of Boolean networks,IEEE Trans.Aut.Contr.,55(10):2251-2258,2010.
[18]D.Cheng,H.Qi,Controllability and observability of Boolean control networks,Automatica,45(7):1659-1667,2009.
[19]D.Cheng,Z.Li,H.Qi,Realization of Boolean control networks,Automatica,46(1):62-69,2010.
[20]D.Cheng,Disturbance decoupling of Boolean control networks,IEEE Trans.Aut.Contr.,56(1):2-10,2011.
[21]D.Cheng,H.Qi,Z.Li,J.Liu,Stability and stabilization of Boolean networks,Int.J.Robust Nonlinear Contr.,21(2):134-156,2011.
[22]F.Li,J.Sun,Boolean derivative calculation with application to fault detection of combinational circuits via the semi-tensor product method,Automatica,48(4):688-693,2012.
[23]H.Li,Y.Wang,Controllability of Boolean control networks with time delays in state,Automatica,47(3):603-607,2011.
[24]P.Guo,Y.Wang,H.Li.Algebraic formulation and strategy optimization for a class of evolutionary networked games via semi-tensor product method.Automatica,49(11):3384-3389,2013.
[25]Y.Wang,C.Zhang,Z.Liu,A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems,Automatica,48(7):1227-1236,2012.
[26]M.Xu,Y.Wang,A.Wei.Robust graph coloring based on matrix semi-tensor product with application to examination timetabling.Control Theory and Technology,12(2):187-197,2014.
[27]M.Xu,Y.Wang.T-coloring of graphs with application to frequency assignment in cellular mobile networks,Proceedings of the 33rd Chinese control conference Nanjing,China,July,2536-2541,2014.
[28]Y.Liu,W.Zhang,Boolean Methodology,Shanghai Technology Literature Press,1993(in Chinese).