Search results for "colorability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
116	Daya Ram Gaur, Ramesh Krishnamurti	Simple Approximation Algorithms for MAXNAESP and Hypergraph 2-colorability.	ISAAC	1999	DBLP DOI BibTeX RDF	hypergraph 2-colorability, set splitting, maxnaesp, approximation algorithms, max-cut
69	Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron	Comparing the strength of query types in property testing: the case of testing k-colorability.	SODA	2008	DBLP BibTeX RDF
53	Andrej Bogdanov, Kenji Obata, Luca Trevisan	A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs.	FOCS	2002	DBLP DOI BibTeX RDF
48	Florent Bouchez, Alain Darte, Fabrice Rastello	On the Complexity of Register Coalescing.	CGO	2007	DBLP DOI BibTeX RDF
48	Noga Alon, Asaf Shapira	A Characterization of the (natural) Graph Properties Testable with One-Sided Error.	FOCS	2005	DBLP DOI BibTeX RDF
48	Jinpyo Park, Soo-Mook Moon	Optimistic register coalescing.	ACM Trans. Program. Lang. Syst.	2004	DBLP DOI BibTeX RDF	Copy coalescing, noncopy coalescing, graph coloring, register allocation
47	Yi Cao, Joseph C. Culberson, Lorna Stewart	DP-Complete Problems Derived from Extremal NP-Complete Properties.	MFCS	2009	DBLP DOI BibTeX RDF	DP-complete, extremal problem, unfrozen, complexity, colorability, implicant
47	André Große, Jörg Rothe, Gerd Wechsung	Relating Partial and Complete Solutions and the Complexity of Computing Smallest Solutions.	ICTCS	2001	DBLP DOI BibTeX RDF	complexity of smallest solutions, self-reducibility, graph colorability, Hamiltonian cycles, graph isomorphisms, partial solutions
43	Jose Antonio Martin H.	A polynomial 3-colorability algorithm with automatic generation of NO 3-colorability (i.e. Co-NP) short proofs	CoRR	2011	DBLP BibTeX RDF
43	David P. Dailey	Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete.	Discret. Math.	1980	DBLP DOI BibTeX RDF
37	Corinne Lucet, Florence Mendes, Aziz Moukrim	Pre-processing and Linear-Decomposition Algorithm to Solve the k-Colorability Problem.	WEA	2004	DBLP DOI BibTeX RDF
37	Seiichi Nishihara, Kazunori Mizuno, Kohsuke Nishihara	A Composition Algorithm for Very Hard Graph 3-Colorability Instances.	CP	2003	DBLP DOI BibTeX RDF
37	Richard Nock, Pascal Jappy, Jean Sallantin	Generalized Graph Colorability and Compressibility of Boolean Formulae.	ISAAC	1998	DBLP DOI BibTeX RDF
32	David Eppstein	Testing bipartiteness of geometric intersection graphs.	ACM Trans. Algorithms	2009	DBLP DOI BibTeX RDF	Hopcroft's problem, coin graph, geometric thickness, graph coloring, minimum spanning tree, Bipartite graph, line segments, disks, intersection graph
32	Andreas Wiese, Evangelos Kranakis	Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs.	WG	2008	DBLP DOI BibTeX RDF
32	Florent Bouchez, Alain Darte, Fabrice Rastello	Advanced conservative and optimistic register coalescing.	CASES	2008	DBLP DOI BibTeX RDF	coloring number, greedy-k-colorable graph, register allocation, chordal graph, register coalescing
32	Dimitris Achlioptas, Cristopher Moore	Almost all graphs with average degree 4 are 3-colorable.	STOC	2002	DBLP DOI BibTeX RDF	threshold phenomena, graph coloring, random graphs
22	Zdenek Dvorák 0001, Daniel Král', Robin Thomas 0001	Three-coloring triangle-free graphs on surfaces VI. 3-colorability of quadrangulations.	J. Comb. Theory, Ser. B	2024	DBLP DOI BibTeX RDF
22	Evan Chang, Neel Kolhe, Youngtak Sohn	Upper bounds on the 2-colorability threshold of random d-regular k-uniform hypergraphs for k≥3.	CoRR	2023	DBLP DOI BibTeX RDF
22	Yuhao Liu 0003, Mingyu Xiao 0001	The (3,3)-colorability of planar graphs without 4-cycles and 5-cycles.	Discret. Math.	2023	DBLP DOI BibTeX RDF
22	Xiangwen Li, Jian-Bo Lv, Mao Zhang	DP-4-colorability of planar graphs without intersecting 5-cycles.	Discret. Math.	2022	DBLP DOI BibTeX RDF
22	Yingli Kang, Ligang Jin, Peipei Liu, Yingqian Wang 0001	(1, 0, 0)-colorability of planar graphs without cycles of length 4 or 6.	Discret. Math.	2022	DBLP DOI BibTeX RDF
22	Robert D. Barish, Tetsuo Shibuya	Proper Colorability of Segment Intersection Graphs.	COCOON	2022	DBLP DOI BibTeX RDF
22	Arnfried Kemnitz, Margit Voigt	A Note on Complex-4-Colorability of Signed Planar Graphs.	Electron. J. Comb.	2021	DBLP DOI BibTeX RDF
22	Leonid Plachta	Coverings of cubic graphs and 3-edge colorability.	Discuss. Math. Graph Theory	2021	DBLP DOI BibTeX RDF
22	Nicholas Crawford, Sogol Jahanbekam, Katerina Potika	Improved algorithm to determine 3-colorability of graphs with minimum degree at least 7.	Discret. Appl. Math.	2021	DBLP DOI BibTeX RDF
22	Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein	Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs.	COLT	2021	DBLP BibTeX RDF
22	Varsha Dani, Diksha Gupta, Thomas P. Hayes	On the Power of Choice for k-Colorability of Random Graphs.	APPROX-RANDOM	2021	DBLP DOI BibTeX RDF
22	Zdenek Dvorák 0001, Xiaolan Hu	(3a: a)-List-Colorability of Embedded Graphs of Girth at Least Five.	SIAM J. Discret. Math.	2020	DBLP DOI BibTeX RDF
22	Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein	Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs.	CoRR	2020	DBLP BibTeX RDF
22	Ruzayn Quaddoura	On 2-colorability problem for hypergraphs with P_8-free incidence graphs.	Int. Arab J. Inf. Technol.	2020	DBLP DOI BibTeX RDF
22	Dmitry A. Shabanov	Estimating the r-colorability threshold for a random hypergraph.	Discret. Appl. Math.	2020	DBLP DOI BibTeX RDF
22	Runrun Liu, Xiangwen Li, Kittikorn Nakprasit, Pongpat Sittitrai, Gexin Yu	DP-4-colorability of planar graphs without adjacent cycles of given length.	Discret. Appl. Math.	2020	DBLP DOI BibTeX RDF
22	Michael Krul, Lubos Thoma	2-Colorability of r-Uniform Hypergraphs.	Electron. J. Comb.	2019	DBLP DOI BibTeX RDF
22	Lily Chen, Runrun Liu, Gexin Yu, Ren Zhao, Xiangqian Zhou	DP-4-colorability of two classes of planar graphs.	Discret. Math.	2019	DBLP DOI BibTeX RDF
22	Martin Kochol	Three colorability characterized by shrinking of locally connected subgraphs into triangles.	Inf. Process. Lett.	2018	DBLP DOI BibTeX RDF
22	Zdenek Dvorák 0001, Bernard Lidický	Fine Structure of 4-Critical Triangle-Free Graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains.	SIAM J. Discret. Math.	2018	DBLP DOI BibTeX RDF
22	Selma Djelloul, Odile Favaron, Mekkia Kouider	Edge k-q-Colorability of Graphs.	J. Graph Algorithms Appl.	2018	DBLP DOI BibTeX RDF
22	Lech Duraj, Grzegorz Gutowski, Jakub Kozik	A note on two-colorability of nonuniform hypergraphs.	CoRR	2018	DBLP BibTeX RDF
22	Seog-Jin Kim, Kenta Ozeki	A sufficient condition for DP-4-colorability.	Discret. Math.	2018	DBLP DOI BibTeX RDF
22	Eli Berger, Yanay Soker	A condition for assured 3-face-colorability of infinite plane graphs with a given spanning tree.	Discret. Math.	2018	DBLP DOI BibTeX RDF
22	Mirko Petrusevski	Odd 4-edge-colorability of graphs.	J. Graph Theory	2018	DBLP DOI BibTeX RDF
22	Lech Duraj, Grzegorz Gutowski, Jakub Kozik	A Note on Two-Colorability of Nonuniform Hypergraphs.	ICALP	2018	DBLP DOI BibTeX RDF
22	Alexey Lvov, Gustavo E. Téllez, Gi-Joon Nam	On Coloring and Colorability Analysis of Integrated Circuits with Triple and Quadruple Patterning Techniques.	ISPD	2018	DBLP DOI BibTeX RDF
22	Dmitriy S. Malyshev	The Complexity of the Vertex 3-Colorability Problem for Some Hereditary Classes Defined By 5-Vertex Forbidden Induced Subgraphs.	Graphs Comb.	2017	DBLP DOI BibTeX RDF
22	Matthias Kriesell	Unique Colorability and Clique Minors.	J. Graph Theory	2017	DBLP DOI BibTeX RDF
22	Nirman Kumar	On the minimum edge size for 2-colorability and realizability of hypergraphs by axis-parallel rectangles.	CCCG	2017	DBLP BibTeX RDF
22	Bo Li, Benjamin Lowenstein, Mohamed Omar	Low Degree Nullstellensatz Certificates for 3-Colorability.	Electron. J. Comb.	2016	DBLP DOI BibTeX RDF
22	Stephane Durocher, Ellen Gethner, Debajyoti Mondal	Thickness and colorability of geometric graphs.	Comput. Geom.	2016	DBLP DOI BibTeX RDF
22	George B. Mertzios, Paul G. Spirakis	Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs.	Algorithmica	2016	DBLP DOI BibTeX RDF
22	Ralph Keusch	Colorability Saturation Games.	CoRR	2016	DBLP BibTeX RDF
22	Noga Alon, Omri Ben-Eliezer	Local and global colorability of graphs.	Discret. Math.	2016	DBLP DOI BibTeX RDF
22	Ying-li Kang, Ligang Jin, Yingqian Wang 0001	The 3-colorability of planar graphs without cycles of length 4, 6 and 9.	Discret. Math.	2016	DBLP DOI BibTeX RDF
22	Dan Hefetz, Michael Krivelevich, Wei En Tan	Waiter-Client and Client-Waiter planarity, colorability and minor games.	Discret. Math.	2016	DBLP DOI BibTeX RDF
22	Risto Atanasov, Mirko Petrusevski, Riste Skrekovski	Odd edge-colorability of subcubic graphs.	Ars Math. Contemp.	2016	DBLP DOI BibTeX RDF
22	Christoph Brause, Ingo Schiermeyer, Premysl Holub, Zdenek Ryjácek, Petr Vrána, Rastislav Krivos-Bellus	4-colorability of P6-free graphs.	Electron. Notes Discret. Math.	2015	DBLP DOI BibTeX RDF
22	Alan M. Frieze, Wesley Pegden	Between 2- and 3-Colorability.	Electron. J. Comb.	2015	DBLP DOI BibTeX RDF
22	Cristina Costoya, Antonio Viruel	Rational homotopy theory for computing colorability of simplicial complexes.	Appl. Algebra Eng. Commun. Comput.	2015	DBLP DOI BibTeX RDF
22	Ying-li Kang, Yingqian Wang 0001	Distance Constraints on Short Cycles for 3-Colorability of Planar graphs.	Graphs Comb.	2015	DBLP DOI BibTeX RDF
22	Zdenek Dvorák 0001, Daniel Král, Robin Thomas 0001	Three-coloring triangle-free graphs on surfaces VI. 3-colorability of quadrangulations.	CoRR	2015	DBLP BibTeX RDF
22		Deciding 4-colorability of planar triangulations.	CoRR	2015	DBLP BibTeX RDF
22	Dmitriy S. Malyshev	The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs.	Discret. Math.	2015	DBLP DOI BibTeX RDF
22	Oswin Aichholzer, Franz Aurenhammer, Thomas Hackl, Clemens Huemer, Alexander Pilz, Birgit Vogtenhuber	3-Colorability of Pseudo-Triangulations.	Int. J. Comput. Geom. Appl.	2015	DBLP DOI BibTeX RDF
22	Yuehua Bu, Jinghan Xu, Yingqian Wang 0001	(1, 0, 0)-Colorability of planar graphs without prescribed short cycles.	J. Comb. Optim.	2015	DBLP DOI BibTeX RDF
22	Uwe Schauz	Some New Characterizations of Graph Colorability and of Blocking Sets of Projective Spaces.	Electron. J. Comb.	2014	DBLP DOI BibTeX RDF
22	Yingqian Wang 0001	Entire (Δ+2)-colorability of plane graphs.	Eur. J. Comb.	2014	DBLP DOI BibTeX RDF
22	Antonios Kalampakas	k-Colorability is Graph Automaton Recognizable.	CoRR	2014	DBLP BibTeX RDF
22	Yingqian Wang 0001, Jinghan Xu	Improper colorability of planar graphs without prescribed short cycles.	Discret. Math.	2014	DBLP DOI BibTeX RDF
22	Yingqian Wang 0001, Yaochou Yang	(1, 0, 0)-colorability of planar graphs without cycles of length 4, 5 or 9.	Discret. Math.	2014	DBLP DOI BibTeX RDF
22	Nicolas Gastineau	Partitionnement, recouvrement et colorabilité dans les graphes. (Partitionability, coverability and colorability in graphs).		2014	RDF
22	Amin Coja-Oghlan	Upper-Bounding the k-Colorability Threshold by Counting Covers.	Electron. J. Comb.	2013	DBLP DOI BibTeX RDF
22	Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron	Comparing the strength of query types in property testing: The case of k-colorability.	Comput. Complex.	2013	DBLP DOI BibTeX RDF
22	Amin Coja-Oghlan	Upper-bounding the k-colorability threshold by counting covers	CoRR	2013	DBLP BibTeX RDF
22	Amin Coja-Oghlan, Dan Vilenchik	Chasing the k-colorability threshold	CoRR	2013	DBLP BibTeX RDF
22	Oleg Verbitsky 0001	On the dynamic width of the 3-colorability problem.	CoRR	2013	DBLP BibTeX RDF
22	Hao Li, Hong-Jian Lai	Group colorability of multigraphs.	Discret. Math.	2013	DBLP DOI BibTeX RDF
22	Máté Hegyháti, Zsolt Tuza	Colorability of mixed hypergraphs and their chromatic inversions.	J. Comb. Optim.	2013	DBLP DOI BibTeX RDF
22	Amin Coja-Oghlan, Dan Vilenchik	Chasing the K-Colorability Threshold.	FOCS	2013	DBLP DOI BibTeX RDF
22	Stephane Durocher, Ellen Gethner, Debajyoti Mondal	Thickness and Colorability of Geometric Graphs.	WG	2013	DBLP DOI BibTeX RDF
22	George B. Mertzios, Paul G. Spirakis	Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs.	SOFSEM	2013	DBLP DOI BibTeX RDF
22	Oleg V. Borodin, Anna O. Ivanova	2-distance 4-colorability of planar subcubic graphs with girth at least 22.	Discuss. Math. Graph Theory	2012	DBLP DOI BibTeX RDF
22	George B. Mertzios, Paul G. Spirakis	Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs	CoRR	2012	DBLP BibTeX RDF
22	Oleg V. Borodin, Anna O. Ivanova	List 2-facial 5-colorability of plane graphs with girth at least 12.	Discret. Math.	2012	DBLP DOI BibTeX RDF
22	Varsha Dani, Cristopher Moore, Anna Olson	Tight Bounds on the Threshold for Permuted k-Colorability.	APPROX-RANDOM	2012	DBLP DOI BibTeX RDF
22	Qian Wu, Qiuli Lu, Yingqian Wang 0001	(Δ+1)-total-colorability of plane graphs of maximum degree Δ≥6 with neither chordal 5-cycle nor chordal 6-cycle.	Inf. Process. Lett.	2011	DBLP DOI BibTeX RDF
22	Andrei Kupavskii, Dmitry A. Shabanov	On r-colorability of random hypergraphs.	CoRR	2011	DBLP BibTeX RDF
22	Varsha Dani, Cristopher Moore, Anna Olson	Tight bounds on the threshold for permuted k-colorability	CoRR	2011	DBLP BibTeX RDF
22	Elad Horev	On colorability of graphs with forbidden minors along paths and circuits.	Discret. Math.	2011	DBLP DOI BibTeX RDF
22	Mu-Tsun Tsai, Douglas B. West	A new proof of 3-colorability of Eulerian triangulations.	Ars Math. Contemp.	2011	DBLP DOI BibTeX RDF
22	Jingwen Zhang, Yingqian Wang 0001	(Delta+1)-total-colorability of plane graphs with maximum degree Delta at least 6 and without adjacent short cycles.	Inf. Process. Lett.	2010	DBLP DOI BibTeX RDF
22	Chính T. Hoàng, Marcin Kaminski 0001, Vadim V. Lozin, Joe Sawada, Xiao Shu	Deciding k-Colorability of P5-Free Graphs in Polynomial Time.	Algorithmica	2010	DBLP DOI BibTeX RDF
22	Sama Goliaei, Saeed Jalili	Optical Graph 3-Colorability.	OSC	2010	DBLP DOI BibTeX RDF
22	Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron	Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability.	Property Testing	2010	DBLP DOI BibTeX RDF
22	Lan Shen, Yingqian Wang 0001	On the 7 Total Colorability of Planar Graphs with Maximum Degree 6 and without 4-cycles.	Graphs Comb.	2009	DBLP DOI BibTeX RDF
22	Daniel Bruce, Chính T. Hoàng, Joe Sawada	A certifying algorithm for 3-colorability of P5-free graphs	CoRR	2009	DBLP BibTeX RDF
22	Lan Shen, Yingqian Wang 0001, Wei-Fan Wang 0001, Ko-Wei Lih	On the 9-total-colorability of planar graphs with maximum degree 8 and without intersecting triangles.	Appl. Math. Lett.	2009	DBLP DOI BibTeX RDF
22	Xueliang Li 0001, Xiangmei Yao, Wenli Zhou, Hajo Broersma	Complexity of conditional colorability of graphs.	Appl. Math. Lett.	2009	DBLP DOI BibTeX RDF
22	Huajing Lu, Yingqian Wang 0001, Weifan Wang 0001, Yuehua Bu, Mickaël Montassier, André Raspaud	On the 3-colorability of planar graphs without 4-, 7- and 9-cycles.	Discret. Math.	2009	DBLP DOI BibTeX RDF
22	Daniel Bruce, Chính T. Hoàng, Joe Sawada	A Certifying Algorithm for 3-Colorability of P5-Free Graphs.	ISAAC	2009	DBLP DOI BibTeX RDF
22	Dan Hefetz, Michael Krivelevich, Milos Stojakovic, Tibor Szabó	Planarity, Colorability, and Minor Games.	SIAM J. Discret. Math.	2008	DBLP DOI BibTeX RDF