Search results for "k-colorings"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
66	Irene Finocchi, Emanuele G. Fusco, Rossella Petreschi	A Note on Algebraic Hypercube Colorings.	ITNG	2008	DBLP DOI BibTeX RDF
66	Bojan Mohar	Hajós Theorem For Colorings Of Edge-Weighted Graphs.	Comb.	2004	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C15
66	Christian Anger, Kathrin Konczak, Thomas Linke	NoMoRe : Non-monotonic Reasoning with Logic Programs.	JELIA	2002	DBLP DOI BibTeX RDF
55	Joel Friedman	On the Bit Extraction Problem	FOCS	1992	DBLP DOI BibTeX RDF	almost equicolored colorings, bit extraction problem, n-dimensional Boolean cube, privacy amplification problem, XOR type colorings, coloring
53	Jesper Jansson 0001, Takeshi Tokuyama	Semi-Balanced Colorings of Graphs: Generalized 2-Colorings Based on a Relaxed Discrepancy Condition.	Graphs Comb.	2004	DBLP DOI BibTeX RDF
53	Fabian Kuhn	Weak graph colorings: distributed algorithms and applications.	SPAA	2009	DBLP DOI BibTeX RDF	deterministic symmetry breaking, distributed algorithms, locality, graph coloring
53	David Gamarnik, Dmitriy Katz	Correlation decay and deterministic FPTAS for counting list-colorings of a graph.	SODA	2007	DBLP BibTeX RDF
53	Hajo Broersma, Bert Marchal, Daniël Paulusma, A. N. M. Salman	Improved Upper Bounds for lambda -Backbone Colorings Along Matchings and Stars.	SOFSEM (1)	2007	DBLP DOI BibTeX RDF
53	Kathrin Konczak, Thomas Linke, Torsten Schaub	Graphs and Colorings for Answer Set Programming: Abridged Report.	LPNMR	2004	DBLP DOI BibTeX RDF
53	Dimitris Achlioptas, Michael S. O. Molloy, Cristopher Moore, Frank Van Bussel	Sampling Grid Colorings with Fewer Colors.	LATIN	2004	DBLP DOI BibTeX RDF
41	Maria Axenovich, Ryan R. Martin	Sub-Ramsey Numbers for Arithmetic Progressions.	Graphs Comb.	2006	DBLP DOI BibTeX RDF	Sub-Ramsey, Arithmetic progressions, Bounded colorings
40	Serguei Norine, Robin Thomas 0001	Pfaffian labelings and signs of edge colorings.	Comb.	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 05C70, 05C15, 05C75, 05C10
40	Sergey V. Avgustinovich, Ivan Yu. Mogilnykh	Perfect 2-Colorings of Johnson Graphs J(6, 3) and J(7, 3).	ICMCTA	2008	DBLP DOI BibTeX RDF
40	Martin Marciniszyn, Reto Spöhel	Online vertex colorings of random graphs without monochromatic subgraphs.	SODA	2007	DBLP BibTeX RDF
40	David J. Galvin, Dana Randall	Torpid mixing of local Markov chains on 3-colorings of the discrete torus.	SODA	2007	DBLP BibTeX RDF
40	Thomas P. Hayes, Eric Vigoda	Coupling with the stationary distribution and improved sampling for colorings and independent sets.	SODA	2005	DBLP BibTeX RDF
40	Hajo Broersma, Fedor V. Fomin, Petr A. Golovach, Gerhard J. Woeginger	Backbone Colorings for Networks.	WG	2003	DBLP DOI BibTeX RDF
40	Therese C. Biedl, Eowyn Cenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming-wei Wang	Balanced k-Colorings.	MFCS	2000	DBLP DOI BibTeX RDF
39	Dominique de Werra, Pierre Hansen	Variations on the Roy-Gallai theorem.	4OR	2005	DBLP DOI BibTeX RDF	panchromatic chains, stable sets, Graph coloring, chromatic number, longest path
39	Todd Eisworth, Saharon Shelah	Successors of singular cardinals and coloring theorems I.	Arch. Math. Log.	2005	DBLP DOI BibTeX RDF	Jonsson cardinals, coloring theorms, successors of singular cardinals
39	Alan A. Bertossi, Maria Cristina Pinotti, Romeo Rizzi	Channel Assignment on Strongly-Simplicial Graphs.	IPDPS	2003	DBLP DOI BibTeX RDF
39	András Gyárfás	Transitive Edge Coloring of Graphs and Dimension of Lattices.	Comb.	2002	DBLP DOI BibTeX RDF	AMS Subject Classification (2000) 05C15
39	Benjamin Doerr	Balanced Coloring: Equally Easy for All Numbers of Colors?	STACS	2002	DBLP DOI BibTeX RDF
39	Benjamin Doerr	Structured Randomized Rounding and Coloring.	FCT	2001	DBLP DOI BibTeX RDF	hypergraph coloring, randomized algorithms, integer linear programming, discrepancy, randomized rounding
39	Petter Kristiansen, Jan Arne Telle	Generalized H-Coloring of Graphs.	ISAAC	2000	DBLP DOI BibTeX RDF
27	James Allen Fill, Mark Huber	The Randomness Recycler: A New Technique for Perfect Sampling.	FOCS	2000	DBLP DOI BibTeX RDF	randomness recycler, perfect sampling, approximately random samples, output samples, target distribution, classical Markov chain approaches, RR-based algorithm, perfect sampling methods, restricted instances, first expected linear time algorithms, sample generation, self-organizing lists, random independent sets, random colorings, random cluster model, RR protocol, graph theory, probability, Markov chains, probability distributions, random processes, mixing time, sampling methods, Ising model, self-adjusting systems
27	Neal Madras, Dana Randall	Factoring Graphs to Bound Mixing Rates.	FOCS	1996	DBLP DOI BibTeX RDF	mixing rate bounding, state space decomposition, Monte Carlo Markov chain algorithm, random three-colorings, 2-dimensional lattice regions, 3-state Potts model, ice model, Metropolis sampling algorithm, factorization theorems, Markov chain, Markov processes, statistical mechanics
27	Noga Alon, Alan M. Frieze, Dominic Welsh	Polynomial time randomised approxmiation schemes for the Tutte polynomial of dense graphs	FOCS	1994	DBLP DOI BibTeX RDF	polynomial time randomised approximation schemes, dense graphs, Tutte-Grothendieck polynomial, combinatorial quantities, spanning forests, strongly connected orientations, k-colorings, reliability probability, P-hard, ferromagnetic Q-state Potts model, linear matroids, weight enumerator, linear codes, partition functions, Tutte polynomial
27	Peter Bradshaw	Graph colorings with restricted bicolored subgraphs: I. Acyclic, star, and treewidth colorings.	J. Graph Theory	2022	DBLP DOI BibTeX RDF
27	Hong-Jian Lai, Lucian Mazza	Group Colorings and DP-Colorings of Multigraphs Using Edge-Disjoint Decompositions.	Graphs Comb.	2021	DBLP DOI BibTeX RDF
27	Amin Bahmanian	Extending Edge-colorings of Complete Hypergraphs into Regular Colorings.	CoRR	2021	DBLP BibTeX RDF
27	Nibedita Mandal, Pratima Panigrahi	L(2, 1)-colorings and irreducible no-hole colorings of the direct product of graphs.	Discret. Appl. Math.	2020	DBLP DOI BibTeX RDF
27	Wei Wang 0052, Jianguo Qian, Zhidan Yan	Colorings versus list colorings of uniform hypergraphs.	J. Graph Theory	2020	DBLP DOI BibTeX RDF
27	M. Amin Bahmanian	Extending edge-colorings of complete hypergraphs into regular colorings.	J. Graph Theory	2019	DBLP DOI BibTeX RDF
27	Théo Pierron	Induction Schemes : From Language Separation to Graph Colorings. (Schémas d'induction : from languages separation to graph colorings).		2019	RDF
27	Nibedita Mandal, Pratima Panigrahi	L(2, 1)-colorings and Irreducible No-hole Colorings of Cartesian Product of Graphs.	Electron. Notes Discret. Math.	2017	DBLP DOI BibTeX RDF
27	Shuangliang Tian, Qian Wang	Adjacent vertex distinguishing edge-colorings and total-colorings of the lexicographic product of graphs.	Discret. Appl. Math.	2015	DBLP DOI BibTeX RDF
27	Bin Liu 0009, Jianfeng Hou, Jianliang Wu, Guizhen Liu	Total colorings and list total colorings of planar graphs without intersecting 4-cycles.	Discret. Math.	2009	DBLP DOI BibTeX RDF
27	Daniel Král	Extending partial 5-colorings and 6-colorings in planar graphs.	J. Comb. Theory, Ser. B	2006	DBLP DOI BibTeX RDF
27	Arnfried Kemnitz, Massimiliano Marangio	Edge colorings and total colorings of integer distance graphs.	Discuss. Math. Graph Theory	2002	DBLP DOI BibTeX RDF
27	Grzegorz Kubicki, Jenö Lehel, Michal Morayne	Patch Colorings and Rigid Colorings of the Rational n-Space.	J. Comb. Theory, Ser. B	2002	DBLP DOI BibTeX RDF
27	Xiao Zhou 0001, Takao Nishizeki	Simple Reduction of f-Colorings to Edge-Colorings.	COCOON	1995	DBLP DOI BibTeX RDF
26	Takehiro Ito, Marcin Kaminski 0001, Erik D. Demaine	Reconfiguration of List Edge-Colorings in a Graph.	WADS	2009	DBLP DOI BibTeX RDF
26	Flavio Chierichetti, Andrea Vattani	The Local Nature of List Colorings for Graphs of High Girth.	ICALP (1)	2008	DBLP DOI BibTeX RDF
26	Tomer Kotek, Johann A. Makowsky, Boris Zilber	On Counting Generalized Colorings.	CSL	2008	DBLP DOI BibTeX RDF
26	Balázs Keszegh	Polychromatic Colorings of n-Dimensional Guillotine-Partitions.	COCOON	2008	DBLP DOI BibTeX RDF
26	Eldar Fischer, Orly Yahalom	Testing Convexity Properties of Tree Colorings.	STACS	2007	DBLP DOI BibTeX RDF
26	Fedor V. Fomin, Serge Gaspers, Saket Saurabh 0001	Improved Exact Algorithms for Counting 3- and 4-Colorings.	COCOON	2007	DBLP DOI BibTeX RDF
26	Rong Luo, Wenan Zang, Cun-Quan Zhang	Nowhere-Zero 4-Flows, Simultaneous Edge-Colorings, And Critical Partial Latin Squares.	Comb.	2004	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C15, 05C07, 05C70, 05C38, 05B15
26	Fabio Martinelli, Alistair Sinclair, Dror Weitz	Fast mixing for independent sets, colorings and other models on trees.	SODA	2004	DBLP BibTeX RDF
26	Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos	Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings.	ESA	2004	DBLP DOI BibTeX RDF
26	Wayne Goddard, Stephen T. Hedetniemi, David Pokrass Jacobs, Pradip K. Srimani	Fault Tolerant Algorithms for Orderings and Colorings.	IPDPS	2004	DBLP DOI BibTeX RDF
26	Thomas P. Hayes, Eric Vigoda	A Non-Markovian Coupling for Randomly Sampling Colorings.	FOCS	2003	DBLP DOI BibTeX RDF
26	Benjamin Doerr, Anand Srivastav	Recursive Randomized Coloring Beats Fair Dice Random Colorings.	STACS	2001	DBLP DOI BibTeX RDF
26	Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos	Counting H-Colorings of Partial k-Trees.	COCOON	2001	DBLP DOI BibTeX RDF
26	Eric Vigoda	Improved Bounds for Sampling Colorings.	FOCS	1999	DBLP DOI BibTeX RDF
26	Klaus Jansen	A Rainbow About T-Colorings for Complete Graphs.	WG	1993	DBLP DOI BibTeX RDF
26	Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda	Adaptive simulated annealing: A near-optimal connection between sampling and counting.	J. ACM	2009	DBLP DOI BibTeX RDF	simulated annealing, Markov chain Monte Carlo, Counting
26	Ken-ichi Kawarabayashi, Bojan Mohar	List-color-critical graphs on a fixed surface.	SODA	2009	DBLP DOI BibTeX RDF	critical graphs, surface, list-coloring
26	Alexander Engström	Set Partition Complexes.	Discret. Comput. Geom.	2008	DBLP DOI BibTeX RDF	Set partition complex, Hom complex, Topological combinatorics, Ramsey theory
26	Jing Liu 0006, Weicai Zhong, Jinshu Li	Multiagent Evolutionary Algorithm for T-coloring Problem.	SEAL	2008	DBLP DOI BibTeX RDF
26	Dimitris Achlioptas, Amin Coja-Oghlan	Algorithmic Barriers from Phase Transitions.	FOCS	2008	DBLP DOI BibTeX RDF
26	Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda	Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting.	FOCS	2007	DBLP DOI BibTeX RDF
26	Antar Bandyopadhyay, David Gamarnik	Counting without sampling: new algorithms for enumeration problems using statistical physics.	SODA	2006	DBLP DOI BibTeX RDF
26	Robert Berke, Tibor Szabó	Deciding Relaxed Two-Colorability - A Hardness Jump.	ESA	2006	DBLP DOI BibTeX RDF
26	Irene Finocchi, Alessandro Panconesi, Riccardo Silvestri	An Experimental Analysis of Simple, Distributed Vertex Coloring Algorithms.	Algorithmica	2005	DBLP DOI BibTeX RDF	Distributed graph algorithms, Algorithm engineering, Vertex coloring
26	David R. Karger, Muriel Médard	Toward Using the Network as a Switch: On the Use of TDM in Linear Optical Networks.	IEEE J. Sel. Areas Commun.	2005	DBLP DOI BibTeX RDF
26	Shlomo Moran, Sagi Snir	Convex Recolorings of Strings and Trees: Definitions, Hardness Results and Algorithms.	WADS	2005	DBLP DOI BibTeX RDF
26	Nitin Ahuja, Andreas Baltz, Benjamin Doerr, Ales Prívetivý, Anand Srivastav	On the Minimum Load Coloring Problem.	WAOA	2005	DBLP DOI BibTeX RDF
26	Alan A. Bertossi, Maria Cristina Pinotti, Richard B. Tan	Channel Assignment with Separation for Interference Avoidance in Wireless Networks.	IEEE Trans. Parallel Distributed Syst.	2003	DBLP DOI BibTeX RDF	cellular grids, bidimensional grids, L(2,1,1){hbox{-}}rm coloring, L(delta_1,1,ldots,1){hbox{-}}rm coloring, Wireless networks, interferences, channel assignment, rings
26	Thomas Zeitlhofer, Bernhard Wess	Optimum register assignment for heterogeneous register-set architectures.	ISCAS (3)	2003	DBLP DOI BibTeX RDF
26	Irene Finocchi, Alessandro Panconesi, Riccardo Silvestri	Experimental analysis of simple, distributed vertex coloring algorithms.	SODA	2002	DBLP BibTeX RDF
26	Marc Andries, Luca Cabibbo, Jan Paredaens, Jan Van den Bussche	Applying an update method to a set of receivers.	ACM Trans. Database Syst.	2001	DBLP DOI BibTeX RDF	order independence, parallel update, schema coloring, relational algebra, database update
26	Christian Anger, Kathrin Konczak, Thomas Linke	NoMoRe : A System for Non-Monotonic Reasoning under Answer Set Semantics.	LPNMR	2001	DBLP DOI BibTeX RDF
26	Sriram V. Pemmaraju	Equitable Coloring Extends Chernoff-Hoeffding Bounds.	RANDOM-APPROX	2001	DBLP DOI BibTeX RDF
26	Xiao Zhou 0001, Takao Nishizeki	Edge-Coloring and f-Coloring for Various Classes of Graphs.	ISAAC	1994	DBLP DOI BibTeX RDF
13	Joshua Brakensiek, Sami Davies	Robust Factorizations and Colorings of Tensor Graphs.	SIAM J. Discret. Math.	2024	DBLP DOI BibTeX RDF
13	Daniel W. Cranston, Reem Mahmoud	Kempe Equivalent List Colorings.	Comb.	2024	DBLP DOI BibTeX RDF
13	Michal Debski	Edge colorings avoiding patterns.	Eur. J. Comb.	2024	DBLP DOI BibTeX RDF
13	Sebastian Babinski, Andrzej Grzesik	Maximal edge colorings of graphs.	Eur. J. Comb.	2024	DBLP DOI BibTeX RDF
13	Yindi Weng	Some Results on the Rainbow Vertex-Disconnection Colorings of Graphs.	Graphs Comb.	2024	DBLP DOI BibTeX RDF
13	Bryan Freyberg, Alison Marr	Neighborhood Balanced Colorings of Graphs.	Graphs Comb.	2024	DBLP DOI BibTeX RDF
13	Ran Gu, Hui Lei 0002, Yongtang Shi, Yiqiao Wang 0002	A note on rainbow-free colorings of uniform hypergraphs.	Discret. Appl. Math.	2024	DBLP DOI BibTeX RDF
13	Daniel W. Cranston	Odd-sum colorings of planar graphs.	Discret. Appl. Math.	2024	DBLP DOI BibTeX RDF
13	Tao Wang 0005, Xiaojing Yang	On odd colorings of sparse graphs.	Discret. Appl. Math.	2024	DBLP DOI BibTeX RDF
13	Zhengke Miao, Lin Sun, Zhuojie Tu, Xiaowei Yu	On odd colorings of planar graphs.	Discret. Math.	2024	DBLP DOI BibTeX RDF
13	Sergei Kiselev, Andrey Kupavskii	Trivial colors in colorings of Kneser graphs.	Discret. Math.	2024	DBLP DOI BibTeX RDF
13	Analen Malnegro, Kenta Ozeki	H-colorings for 4-regular graphs.	Discret. Math.	2024	DBLP DOI BibTeX RDF
13	Carlos Hoppen, Hanno Lefmann, Dionatan Ricardo Schmidt	Edge-colorings avoiding patterns in a triangle.	Discret. Math.	2024	DBLP DOI BibTeX RDF
13	Mirko Petrusevski, Riste Skrekovski	Proper edge-colorings with a rich neighbor requirement.	Discret. Math.	2024	DBLP DOI BibTeX RDF
13	Stijn Cambie, Wouter Cames van Batenburg, Ewan Davies, Ross J. Kang	Packing list-colorings.	Random Struct. Algorithms	2024	DBLP DOI BibTeX RDF
13	Joseph Briggs, Michael Gene Dobbins, Seunghun Lee	Transversals and Colorings of Simplicial Spheres.	Discret. Comput. Geom.	2024	DBLP DOI BibTeX RDF
13	Hamid Reza Daneshpajouh	On the number of star-shaped classes in optimal colorings of Kneser graphs.	J. Graph Theory	2024	DBLP DOI BibTeX RDF
13	Vishesh Jain, Huy Tuan Pham	Optimal thresholds for Latin squares, Steiner Triple Systems, and edge colorings.	SODA	2024	DBLP DOI BibTeX RDF
13	Carsten Thomassen	Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles.	J. Comb. Theory, Ser. B	2023	DBLP DOI BibTeX RDF
13	Anton Bernshteyn, Tyler Brazelton, Ruijia Cao, Akum Kang	Counting colorings of triangle-free graphs.	J. Comb. Theory, Ser. B	2023	DBLP DOI BibTeX RDF
13	Felix Bock, Rafal Kalinowski, Johannes Pardey, Monika Pilsniak, Dieter Rautenbach, Mariusz Wozniak	Majority Edge-Colorings of Graphs.	Electron. J. Comb.	2023	DBLP DOI BibTeX RDF
13	Denis S. Krotov	Perfect Colorings of the Infinite Square Grid: Coverings and Twin Colors.	Electron. J. Comb.	2023	DBLP DOI BibTeX RDF
13	Michael Krul, Lubos Thoma	An Algebraic Formulation of Hypergraph Colorings.	Electron. J. Comb.	2023	DBLP DOI BibTeX RDF
13	Felix Christian Clemen, Adam Zsolt Wagner	Balanced Edge-Colorings Avoiding Rainbow Cliques of Size Four.	Electron. J. Comb.	2023	DBLP DOI BibTeX RDF