references.bib

@article{Audhya:2011:SCA:1988563.1988571,
 author = {Audhya, Goutam K. and Sinha, Koushik and Ghosh, Sasthi C. and Sinha, Bhabani P.},
 title = {A Survey on the Channel Assignment Problem in Wireless Networks},
 journal = {Wirel. Commun. Mob. Comput.},
 issue_date = {May 2011},
 volume = {11},
 number = {5},
 month = may,
 year = {2011},
 issn = {1530-8669},
 pages = {583--609},
 numpages = {27},
 url = {http://dx.doi.org/10.1002/wcm.898},
 doi = {10.1002/wcm.898},
 acmid = {1988571},
 publisher = {John Wiley and Sons Ltd.},
 address = {Chichester, UK},
 keywords = {cellular networks, channel assignment, cognitive radio networks, multimedia cellular networks, spectrum utilization},
}

@incollection{Kar72,
  year = {1972},
  isbn = {978-1-4684-2003-6},
  booktitle = {Complexity of Computer Computations},
  series = {The IBM Research Symposia Series},
  editor = {Miller, Raymond E. and Thatcher, James W. and Bohlinger, Jean D.},
  doi = {10.1007/978-1-4684-2001-2_9},
  title = {Reducibility among Combinatorial Problems},
  url = {http://dx.doi.org/10.1007/978-1-4684-2001-2_9},
  publisher = {Springer US},
  author = {Karp, Richard M.},
  pages = {85-103},
}

@INPROCEEDINGS{7248845, 
author={R. Wang and C. Zhou and A. Mazumder and A. Das and H. A. Kierstead and A. Sen}, 
booktitle={2015 IEEE International Conference on Communications (ICC)}, 
title={Upper and lower bounds of Choice Number for successful channel assignment in cellular networks}, 
year={2015}, 
pages={3370-3375}, 
keywords={cellular radio;channel allocation;graph colouring;band buffering system;cellular graph;cellular network;channel assignment;choice number lower bound;choice number upper bound;frequency channel subset;graph theory;list coloring problem;Channel allocation;Color;Interference;Mobile communication;Mobile computing;Upper bound;Wireless communication},
doi={10.1109/ICC.2015.7248845},
url={https://doi.org/10.1109/ICC.2015.7248845},
ISSN={1550-3607}, 
month={June},}


@article{1456167, 
author={W. K. Hale}, 
journal={Proceedings of the IEEE}, 
title={Frequency assignment: Theory and applications}, 
year={1980}, 
volume={68}, 
number={12}, 
pages={1497-1514}, 
keywords={Bandwidth;Constraint optimization;Electromagnetic spectrum;Frequency;Interference constraints;Interference elimination;Radio transmitters;Radiofrequency identification;Telegraphy;US Department of Commerce}, 
doi={10.1109/PROC.1980.11899},
url={https://doi.org/10.1109/PROC.1980.11899},
ISSN={0018-9219}, 
month={Dec},
}

@INPROCEEDINGS{662943, 
author={A. Sen and T. Roxborough and S. Medidi}, 
booktitle={INFOCOM '98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE}, 
title={Upper and lower bounds of a class of channel assignment problems in cellular networks}, 
year={1998}, 
volume={3}, 
pages={1284-1291 vol.3}, 
keywords={buffer storage;cellular radio;computational complexity;frequency allocation;graph colouring;land mobile radio;optimisation;radio networks;radiofrequency interference;algorithm complexity;asymptotically optimal algorithms;call originating cell;cellular graphs;cellular networks;channel assignment problems;distance-k chromatic number problem;graph coloring;hexagonal cell structures;interference;k-band buffering system;k-band chromatic bandwidth problem;lower bound;upper bound;Bandwidth;Cellular networks;Computer science;Frequency;Intelligent networks;Interference;K-band;Land mobile radio cellular systems;Mobile communication;Upper bound}, 
doi={10.1109/INFCOM.1998.662943}, 
url={https://doi.org/10.1109/INFCOM.1998.662943},
ISSN={0743-166X}, 
month={Mar},}

@article{CHROBAK1991243,
title = "Planar orientations with low out-degree and compaction of adjacency matrices",
journal = "Theoretical Computer Science",
volume = "86",
number = "2",
pages = "243 - 266",
year = "1991",
issn = "0304-3975",
doi = "https://doi.org/10.1016/0304-3975(91)90020-3",
url = "https://doi.org/10.1016/0304-3975(91)90020-3",
author = "Marek Chrobak and David Eppstein"
}

@article{Kahn:1962:TSL:368996.369025,
 author = {Kahn, A. B.},
 title = {Topological Sorting of Large Networks},
 journal = {Commun. ACM},
 issue_date = {Nov. 1962},
 volume = {5},
 number = {11},
 month = nov,
 year = {1962},
 issn = {0001-0782},
 pages = {558--562},
 numpages = {5},
 url = {http://doi.acm.org/10.1145/368996.369025},
 doi = {10.1145/368996.369025},
 acmid = {369025},
 publisher = {ACM},
 address = {New York, NY, USA},
}

@book{citeulike:395714,
  abstract = {{The third edition of this highly successful textbook has been carefully revised and updated, and includes a new chapter on infinite graphs. The book covers all major, recent developments, and can be used both as a reliable textbook for an introductory course and as a graduate text: on each topic it covers all the basic material in full detail, and adds one or two deeper results (again with detailed proofs) to illustrate the more advanced methods of that field. From the reviews of the first two editions (1997, 2000): "This outstanding book cannot be substituted with any other book on the present textbook market. It has every chance of becoming the standard textbook for graph theory." Acta Scientiarum Mathematicarum "The book has received a very enthusiastic reception, which it amply deserves. A masterly elucidation of modern graph theory." Bulletin of the Institute of Combinatorics and its Applications "A highlight of the book is what is by far the best account in print of the Seymour-Robertson theory of graph minors."  Mathematika ". . . like listening to someone explain mathematics." Bulletin of the AMS}},
  added-at = {2007-04-02T13:41:45.000+0200},
  author = {Diestel, Reinhard},
  biburl = {https://www.bibsonomy.org/bibtex/28e6027f87536254e3d0cadc76403c9b5/msn},
  citeulike-article-id = {395714},
  howpublished = {Hardcover},
  interhash = {befccfe79e0a9160bc47635a92c96b68},
  intrahash = {8e6027f87536254e3d0cadc76403c9b5},
  isbn = {3540261826},
  keywords = {info.refs.books research.conceptual.graphs science.math},
  month = {August},
  priority = {2},
  publisher = {Springer},
  timestamp = {2007-04-02T13:41:45.000+0200},
  title = {Graph Theory (Graduate Texts in Mathematics)},
  year = 2005,
  note={{ISBN:} 978-3540261827}
}

@article{richardson1946,
author = "Richardson, M.",
fjournal = "Bulletin of the American Mathematical Society",
journal = "Bull. Amer. Math. Soc.",
month = "02",
number = "2",
pages = "113--116",
publisher = "American Mathematical Society",
title = "On weakly ordered systems",
url = "https://projecteuclid.org:443/euclid.bams/1183507698",
volume = "52",
year = "1946"
}

@article{chvatal,
 author = {Chvátal, Václav},
 title = {On the computational complexity of finding a kernel},
 journal = {Report No. CRM-300, Centre de Recherches Mathematiques, Universite de Montreal},
 year = {1973},
 url = {http://users.encs.concordia.ca/~chvatal/kernel.html}
}

@article{Thomassen:1994:PG:184180.184192,
 author = {Thomassen, C.},
 title = {Every Planar Graph Is 5-Choosable},
 journal = {J. Comb. Theory Ser. B},
 issue_date = {Sept. 1994},
 volume = {62},
 number = {1},
 month = sep,
 year = {1994},
 issn = {0095-8956},
 pages = {180--181},
 numpages = {2},
 url = {http://dx.doi.org/10.1006/jctb.1994.1062},
 doi = {10.1006/jctb.1994.1062},
 acmid = {184192},
 publisher = {Academic Press, Inc.},
 address = {Orlando, FL, USA},
} 

@article{Galvin:1995:LCI:199352.199369,
 author = {Galvin, Fred},
 title = {The List Chromatic Index of a Bipartite Multigraph},
 journal = {J. Comb. Theory Ser. B},
 issue_date = {Jan. 1995},
 volume = {63},
 number = {1},
 month = jan,
 year = {1995},
 issn = {0095-8956},
 pages = {153--158},
 numpages = {6},
 url = {http://dx.doi.org/10.1006/jctb.1995.1011},
 doi = {10.1006/jctb.1995.1011},
 acmid = {199369},
 publisher = {Academic Press, Inc.},
 address = {Orlando, FL, USA},
}

@article {JGT:JGT4,
author = {Mirzakhani, M.},
title = {A small non-4-choosable planar graph},
publisher = {Sharif University of Technology},
url = {https://fu-mathe.wikispaces.com/file/view/Mirzhakhani.pdf}
}

@article{Matula:1983:SOC:2402.322385,
 author = {Matula, David W. and Beck, Leland L.},
 title = {Smallest-last Ordering and Clustering and Graph Coloring Algorithms},
 journal = {J. ACM},
 issue_date = {July 1983},
 volume = {30},
 number = {3},
 month = jul,
 year = {1983},
 issn = {0004-5411},
 pages = {417--427},
 numpages = {11},
 url = {http://doi.acm.org.focus.lib.kth.se/10.1145/2402.322385},
 doi = {10.1145/2402.322385},
 acmid = {322385},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@inproceedings{Cowen:1997:CD:314161.314387,
 author = {Cowen, L. J. and Goddard, W. and Jesurum, C. E.},
 title = {Coloring with Defect},
 booktitle = {Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms},
 series = {SODA '97},
 year = {1997},
 isbn = {0-89871-390-0},
 location = {New Orleans, Louisiana, USA},
 pages = {548--557},
 numpages = {10},
 url = {http://dl.acm.org/citation.cfm?id=314161.314387},
 acmid = {314387},
 publisher = {Society for Industrial and Applied Mathematics},
 address = {Philadelphia, PA, USA},
} 


@article{erdos-choosability,
 author = {Erdős, P. and Rubin, Arthur L. and Taylor, H.},
 title = {Choosability in graphs},
 journal = {Proceedings of the West Coast Conference on Combinatorics},
 year = {1979},
 volume = {26},
 pages = {125--157},
 url = {https://users.renyi.hu/~p_erdos/1980-07.pdf},
 acmid = {1988571},
 publisher = {Graph Theory and Computing, Arcata},
 address = {California},
}

@book{neumann,
 ISBN = {9780691130613},
 URL = {http://www.jstor.org/stable/j.ctt1r2gkx},
 abstract = {<p>This is the classic work upon which modern-day game theory is based. What began more than sixty years ago as a modest proposal that a mathematician and an economist write a short paper together blossomed, in 1944, when Princeton University Press published<em>Theory of Games and Economic Behavior</em>. In it, John von Neumann and Oskar Morgenstern conceived a groundbreaking mathematical theory of economic and social organization, based on a theory of games of strategy. Not only would this revolutionize economics, but the entirely new field of scientific inquiry it yielded--game theory--has since been widely used to analyze a host of real-world phenomena from arms races to optimal policy choices of presidential candidates, from vaccination policy to major league baseball salary negotiations. And it is today established throughout both the social sciences and a wide range of other sciences.</p><p>This sixtieth anniversary edition includes not only the original text but also an introduction by Harold Kuhn, an afterword by Ariel Rubinstein, and reviews and articles on the book that appeared at the time of its original publication in the<em>New York Times</em>, tthe<em>American Economic Review</em>, and a variety of other publications. Together, these writings provide readers a matchless opportunity to more fully appreciate a work whose influence will yet resound for generations to come.</p>},
 author = {John von Neumann and Oskar Morgenstern and Harold W. Kuhn and Ariel Rubinstein},
 publisher = {Princeton University Press},
 title = {Theory of Games and Economic Behavior (60th Anniversary Commemorative Edition)},
 year = {1944}
}

@ARTICLE{ieee80211, 
author={}, 
journal={IEEE Std 802.11-2012 (Revision of IEEE Std 802.11-2007) - Redline}, 
title={IEEE Standard for Information technology--Telecommunications and information exchange between systems Local and metropolitan area networks--Specific requirements Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications - Redline}, 
year={2012}, 
volume={}, 
number={}, 
pages={1-5229}, 
keywords={Emergency services;IEEE standards;Information exchange;Local area networks;Media Access Protocol;Metropolitan area networks;Physical layer;Throughput;2.4 GHz;3650 MHz;4.9 GHz;5 GHz;5.9 GHz;AES;CCMP;CSMA/CA;Counter mode with Cipher-block chaining Message authentication code Protocol;DFS;E911;IEEE 802.11;LAN;MAC;MIH;MIMO;MIMO-OFDM;PHY;QoS;QoS mapping;RF;SSP;SSPN;TKIP;TPC;WLAN;advanced encryption standard;carrier sense multiple access/collision avoidance;channel switching;confidentiality;direct link;dynamic frequency selection;emergency alert system;emergency services;forwarding;generic advertisement service;high throughput;interface;internationalroaming;interworking;interworking with external networks;local area network;measurement;media-independent handover;medium access control;medium access controller;mesh;multi-hop;multiple input multiple output;network advertisement;network discovery;network management;network selection;off-channel direct link;path-selection;physical layer;power saving;quality of service;radio;radio frequency;radio management;radio resource;subscriber service provider;temporal key integrity protocol;transmit power control;tunneled direct link setup;wireless LAN;wireless access in vehicular environments;wireless local area network;wireless network management;zero-knowledge proof}, 
doi={}, 
ISSN={}, 
URL={https://ieeexplore.ieee.org/document/6587723/}
month={March},}

@book{power,
  author = {Pemmaraju, Siriam and Skiena, Steven},
  month = {October},
  publisher = {Cambridge University Press},
  title = {Computational Discrete Mathematics: {Combinatorics and Graph Theory with Mathematica®}},
  year = 2009,
  note={{ISBN:} 9780521121460},
  url={https://www.cambridge.org/9780521121460}
}

@INPROCEEDINGS{marina, 
author={J. Riihijarvi and M. Petrova and P. Mahonen}, 
booktitle={Second Annual Conference on Wireless On-demand Network Systems and Services}, 
title={Frequency allocation for WLANs using graph colouring techniques}, 
year={2005}, 
volume={}, 
number={}, 
pages={216-222}, 
keywords={channel allocation;frequency allocation;graph colouring;interference suppression;protocols;wireless LAN;WLAN;access point;channel allocation;frequency allocation mechanism;graph colouring algorithm;preliminary message format;protocol architecture;wireless LAN;Access protocols;Channel allocation;Electronic mail;Frequency;Interference;Joining processes;Radio spectrum management;Wireless LAN;Wireless application protocol;Wireless networks}, 
doi={10.1109/WONS.2005.19}, 
ISSN={}, 
month={Jan},}

@article{dsatur,
 author = {Br{\'e}laz, Daniel},
 title = {New Methods to Color the Vertices of a Graph},
 journal = {Commun. ACM},
 issue_date = {April 1979},
 volume = {22},
 number = {4},
 month = apr,
 year = {1979},
 issn = {0001-0782},
 pages = {251--256},
 numpages = {6},
 url = {http://doi.acm.org/10.1145/359094.359101},
 doi = {10.1145/359094.359101},
 acmid = {359101},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {NP-complete, balancing, comparison of the methods, graph coloring, graph structure, scheduling},
} 

@article{mishra,
 author = {Mishra, Arunesh and Banerjee, Suman and Arbaugh, William},
 title = {Weighted Coloring Based Channel Assignment for WLANs},
 journal = {SIGMOBILE Mob. Comput. Commun. Rev.},
 issue_date = {July 2005},
 volume = {9},
 number = {3},
 month = jul,
 year = {2005},
 issn = {1559-1662},
 pages = {19--31},
 numpages = {13},
 url = {http://doi.acm.org.focus.lib.kth.se/10.1145/1094549.1094554},
 doi = {10.1145/1094549.1094554},
 acmid = {1094554},
 publisher = {ACM},
 address = {New York, NY, USA},
} 

@INPROCEEDINGS{khanna, 
author={S. Khanna and K. Kumaran}, 
booktitle={Proceedings. IEEE INFOCOM '98, the Conference on Computer Communications. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Gateway to the 21st Century (Cat. No.98}, 
title={On wireless spectrum estimation and generalized graph coloring}, 
year={1998}, 
volume={3}, 
number={}, 
pages={1273-1283 vol.3}, 
keywords={radio networks;radiofrequency interference;network topology;land mobile radio;cellular radio;graph colouring;frequency allocation;wireless spectrum estimation;generalized graph coloring;wireless network;interference pattern;frequency assignment;spectrum requirement;upper bounds;lower bounds;network topologies;tight bounds;hexagonal grid topology;efficient algorithms;geometric structure;subgraphs;worst-case demand patterns;performance;cellular radio;Spectral analysis;Network topology;Wireless networks;Interference;Upper bound;Algorithm design and analysis;Frequency}, 
doi={10.1109/INFCOM.1998.662942}, 
ISSN={0743-166X}, 
month={March},}

@INPROCEEDINGS{islam, 
author={M. I. Islam and A. B. M. S. Hossain}, 
booktitle={2004 IEEE Region 10 Conference TENCON 2004.}, 
title={Channel allocation of mobile cellular network based on graph theory}, 
year={2004}, 
volume={B}, 
number={}, 
pages={529-532 Vol. 2}, 
keywords={cellular radio;minimisation;cochannel interference;adjacent channel interference;interference suppression;channel allocation;graph colouring;matrix algebra;mobile cellular network;minimization;cochannel interference;adjacent channel interference;channel assignment model;graph coloring;graph equivalent matrix theorem;channel allocation problem;interference matrix;Channel allocation;Land mobile radio cellular systems;Graph theory;Interference;Matrix converters;Transmission line matrix methods;Symmetric matrices;Mobile computing;Electronic mail;Radio spectrum management}, 
doi={10.1109/TENCON.2004.1414649}, 
ISSN={}, 
month={Nov},}

@ARTICLE{leese, 
author={R. A. Leese}, 
journal={IEEE Transactions on Vehicular Technology}, 
title={A unified approach to the assignment of radio channels on a regular hexagonal grid}, 
year={1997}, 
volume={46}, 
number={4}, 
pages={968-980}, 
keywords={cellular radio;land mobile radio;radio spectrum management;telecommunication channels;planning;radio channels asignment;regular hexagonal grid;radio systems;quality of service;protection ratios;frequency-distance bounds;hexagonal cells;adjacent channel separations;cochannel separations;cochannel lattices;algorithm;broadcast systems;mobile systems;spectrum management;rhombic numbers;spectrum planning;Quality of service;Lattices;Interference;Protection;Frequency;Radio broadcasting;Libraries;Radio spectrum management;Telephony}, 
doi={10.1109/25.653071}, 
ISSN={0018-9545}, 
month={Nov},}

@article{Ghosh,
author = {Ghosh, Sasthi C. and Sinha, Bhabani P. and Das, Nabanita},
title = {A New Approach to Efficient Channel Assignment for Hexagonal Cellular Networks},
journal = {International Journal of Foundations of Computer Science},
volume = {14},
number = {03},
pages = {439-463},
year = {2003},
doi = {10.1142/S0129054103001832},

URL = { 
        https://doi.org/10.1142/S0129054103001832
    
},
eprint = { 
        https://doi.org/10.1142/S0129054103001832
    
}}

@ARTICLE{wang-rushforth, 
author={Wei Wang and C. K. Rushforth}, 
journal={IEEE Transactions on Vehicular Technology}, 
title={An adaptive local-search algorithm for the channel-assignment problem (CAP)}, 
year={1996}, 
volume={45}, 
number={3}, 
pages={459-466}, 
keywords={telecommunication channels;cellular radio;radio networks;frequency allocation;adaptive systems;search problems;planning;computational complexity;radio network planning;channel assignment problem;cellular radio networks;NP-complete problem;graph coloring algorithms;neural networks;simulated annealing;pattern based optimization;two-phase adaptive local search algorithm;structured preprocessing;Frequency;Land mobile radio cellular systems;NP-complete problem;Neural networks;Simulated annealing;Telephony;Cellular networks;Symmetric matrices;Bandwidth}, 
doi={10.1109/25.533761}, 
ISSN={0018-9545}, 
month={Aug},}

@INPROCEEDINGS{wang-liu, 
author={Wei Wang and Xin Liu}, 
booktitle={VTC-2005-Fall. 2005 IEEE 62nd Vehicular Technology Conference, 2005.}, 
title={List-coloring based channel allocation for open-spectrum wireless networks}, 
year={2005}, 
volume={1}, 
number={}, 
pages={690-694}, 
keywords={Channel allocation;Wireless networks;Availability;Space technology;Telecommunication traffic;Frequency;Time-varying channels;White spaces;FCC;Computer science}, 
doi={10.1109/VETECF.2005.1558001}, 
ISSN={1090-3038}, 
month={Sept},}


@article{orden,
author = {Orden, David and Gimenez-Guzman, Jose Manuel and Marsa-Maestre, Ivan and de la Hoz, Enrique},
title = {Spectrum Graph Coloring and Applications to Wi-Fi Channel Assignment},
journal = {Symmetry},
volume = {10},
year = {2018},
number = {3},
URL = {http://www.mdpi.com/2073-8994/10/3/65},
ISSN = {2073-8994},
ABSTRACT = {We introduce and explore a family of vertex-coloring problems, which, surprisingly enough, have not been considered before despite stemming from the problem of Wi-Fi channel assignment. Given a spectrum of colors, endowed with a matrix of interferences between each pair of colors, the Threshold Spectrum Coloring problem fixes the number of colors available and aims to minimize the interference threshold, i.e., the maximum of the interferences at the vertices. Conversely, the Chromatic Spectrum Coloring problem fixes a threshold and aims to minimize the number of colors for which respecting that threshold is possible. As the main theoretical results, we prove tight upper bounds for the solutions to each problem. Since both problems turn out to be NP-hard, we complete the scene with experimental results. We propose a DSATUR-based heuristic and study its performance to minimize the maximum vertex interference in Wi-Fi channel assignment, both for randomly-generated graphs and for a real-world scenario. Further, for all these graphs, we experimentally check the goodness of the theoretical bounds.},
doi = {10.3390/sym10030065}
}


@article{GRAVIER1996299,
title = "A Hajós-like theorem for list coloring",
journal = "Discrete Mathematics",
volume = "152",
number = "1",
pages = "299 - 302",
year = "1996",
issn = "0012-365X",
doi = "https://doi.org/10.1016/0012-365X(95)00350-6",
url = "http://www.sciencedirect.com/science/article/pii/0012365X95003506",
author = "Sylvain Gravier"
}