Search results for "arboricity"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
137	Qinglin Yu, Lian-Cui Zuo	Fractional Vertex Arboricity of Graphs.	CJCDGCGT	2005	DBLP DOI BibTeX RDF	vertex arboricity, tree coloring, fractional vertex arboricity, fractional tree coloring
88	Abhik Roychoudhury, Susmita Sur-Kolay	Efficient Algorithms for Vertex Arboricity of Planar Graphs.	FSTTCS	1995	DBLP DOI BibTeX RDF	Vertex arboricity, testing of sequential circuits, graph coloring, planar graph
80	Noga Alon, Vanessa Teague, Nicholas C. Wormald	Linear Arboricity and Linear k-Arboricity of Regular Graphs.	Graphs Comb.	2001	DBLP DOI BibTeX RDF
68	Gerard J. Chang, Chiuyuan Chen, Yaping Chen	Vertex and Tree Arboricities of Graphs.	J. Comb. Optim.	2004	DBLP DOI BibTeX RDF	arboricity, block-cactus graph, tree, planar graph, hamiltonian cycle, cograph, acyclic, series-parallel graph, girth
48	Leonid Barenboim, Michael Elkin	Deterministic distributed vertex coloring in polylogarithmic time.	PODC	2010	DBLP DOI BibTeX RDF	arbdefective-coloring, arboricity, partial-orientation
40	Stefan A. Burr	An inequality involving the vertex arboricity and edge arboricity of a graph.	J. Graph Theory	1986	DBLP DOI BibTeX RDF
40	Gaurav Goel, Jens Gustedt	Bounded Arboricity to Determine the Local Structure of Sparse Graphs.	WG	2006	DBLP DOI BibTeX RDF
40	Vida Dujmovic, David R. Wood	Graph Treewidth and Geometric Thickness Parameters.	Discret. Comput. Geom.	2007	DBLP DOI BibTeX RDF
40	Gerth Stølting Brodal, Rolf Fagerberg	Dynamic Representation of Sparse Graphs.	WADS	1999	DBLP DOI BibTeX RDF
20	Zhiwei Guo	Nordhaus-Gaddum-Type Results for the Strong Equitable Vertex k-Arboricity of Graphs.	J. Interconnect. Networks	2024	DBLP DOI BibTeX RDF
20	Ronen Wdowinski	On an f-coloring generalization of linear arboricity of multigraphs.	Discret. Math.	2024	DBLP DOI BibTeX RDF
20	Guantao Chen, Yanli Hao, Guoning Yu	A decomposition method on solving the linear arboricity conjecture.	J. Graph Theory	2024	DBLP DOI BibTeX RDF
20	Jijuan Chen, Tao Wang 0005	On linear 2-arboricity of certain graphs.	Appl. Math. Comput.	2023	DBLP DOI BibTeX RDF
20	Richard Lang, Luke Postle	An Improved Bound for the Linear Arboricity Conjecture.	Comb.	2023	DBLP DOI BibTeX RDF
20	Kittikorn Nakprasit, Watcharintorn Ruksasakchai, Pongpat Sittitrai	Vertex 2-arboricity of planar graphs without 4-cycles adjacent to 6-cycles.	Theor. Comput. Sci.	2023	DBLP DOI BibTeX RDF
20	Hong-Yu Chen, Hong-Jian Lai	On the Linear Arboricity of Graphs with Treewidth at Most Four.	Graphs Comb.	2023	DBLP DOI BibTeX RDF
20	Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon	Arboricity-Dependent Algorithms for Edge Coloring.	CoRR	2023	DBLP DOI BibTeX RDF
20	Oliver Knill	Arboricity and Acyclic Chromatic Number.	CoRR	2023	DBLP DOI BibTeX RDF
20	Juan Liu, Xiaoxue Hu, Dongdong Zhang, Jiangxu Kong	The linear 2-arboricity of IC-planar graphs.	Discret. Appl. Math.	2023	DBLP DOI BibTeX RDF
20	Han Xiao 0003, Qizhi Fang	Arboricity games: the core and the nucleolus.	Math. Program.	2023	DBLP DOI BibTeX RDF
20	Hossein Jowhari	An estimator for matching size in low arboricity graphs with two applications.	J. Comb. Optim.	2023	DBLP DOI BibTeX RDF
20	Guantao Chen, Yanli Hao, Guoning Yu	Linear arboricity of degenerate graphs.	J. Graph Theory	2023	DBLP DOI BibTeX RDF
20	Ronen Wdowinski	Orientation-based edge-colorings and linear arboricity of multigraphs.	J. Graph Theory	2023	DBLP DOI BibTeX RDF
20	Janejira Laomala, Keaitsuda Maneeruk Nakprasit, Kittikorn Nakprasit, Watcharintorn Ruksasakchai	The Strong Equitable Vertex 1-Arboricity of Complete Bipartite Graphs and Balanced Complete k-Partite Graphs.	Symmetry	2022	DBLP DOI BibTeX RDF
20	Michal Dory, Mohsen Ghaffari 0001, Saeed Ilchi	Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs.	CoRR	2022	DBLP DOI BibTeX RDF
20	Aleksander B. G. Christiansen, Eva Rotenberg	Fully-dynamic α+2 Arboricity Decomposition and Implicit Colouring.	CoRR	2022	DBLP DOI BibTeX RDF
20	Fan Yang 0085, Jian-Liang Wu, Huimin Song	The linear arboricity of K5-minor free graphs.	Discret. Appl. Math.	2022	DBLP DOI BibTeX RDF
20	Aina Zhu, Dong Chen 0012, Min Chen 0012, Weifan Wang 0001	Vertex-arboricity of toroidal graphs without K5- and 6-cycles.	Discret. Appl. Math.	2022	DBLP DOI BibTeX RDF
20	Talya Eden, Saleet Mossel, Dana Ron	Approximating the Arboricity in Sublinear Time.	SODA	2022	DBLP DOI BibTeX RDF
20	Aleksander B. G. Christiansen, Eva Rotenberg	Fully-Dynamic α + 2 Arboricity Decompositions and Implicit Colouring.	ICALP	2022	DBLP DOI BibTeX RDF
20	Talya Eden, Dana Ron, Will Rosenbaum	Almost Optimal Bounds for Sublinear-Time Sampling of k-Cliques in Bounded Arboricity Graphs.	ICALP	2022	DBLP DOI BibTeX RDF
20	Aleksander B. G. Christiansen, Jacob Holm, Eva Rotenberg, Carsten Thomassen	On Dynamic α + 1 Arboricity Decomposition and Out-Orientation.	MFCS	2022	DBLP DOI BibTeX RDF
20	Michal Dory, Mohsen Ghaffari 0001, Saeed Ilchi	Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs.	PODC	2022	DBLP DOI BibTeX RDF
20	Zhiwei Guo, Yaping Mao, Nan Jia, He Li	Strong Equitable Vertex Arboricity in Cartesian Product Networks.	J. Interconnect. Networks	2021	DBLP DOI BibTeX RDF
20	Reut Levi	Testing Triangle Freeness in the General Model in Graphs with Arboricity O(√n).	CoRR	2021	DBLP BibTeX RDF
20	Adir Morgan, Shay Solomon, Nicole Wein	Simple Combinatorial Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs.	CoRR	2021	DBLP BibTeX RDF
20	Talya Eden, Saleet Mossel, Dana Ron	Approximating the Arboricity in Sublinear Time.	CoRR	2021	DBLP BibTeX RDF
20	Saeed Akhoondian Amiri	Deterministic CONGEST Algorithm for MDS on Bounded Arboricity Graphs.	CoRR	2021	DBLP BibTeX RDF
20	Mélanie Cambus, Davin Choo, Havu Miikonen, Jara Uitto	Massively Parallel Correlation Clustering in Bounded Arboricity Graphs.	CoRR	2021	DBLP BibTeX RDF
20	Nan Jia, Yaping Mao, Zhao Wang, Eddie Cheng 0001	Linear k-arboricity of Caylay Graphs on Abelian Groups with Given Degree.	Math. Comput. Sci.	2021	DBLP DOI BibTeX RDF
20	Lu Zhang, Juan Liu	The linear 2-arboricity of 1-planar graphs without 3-cycles.	Discret. Math. Algorithms Appl.	2021	DBLP DOI BibTeX RDF
20	Guantao Chen, Yanli Hao	The conjunction of the linear arboricity conjecture and Lovász's path partition theorem.	Discret. Math.	2021	DBLP DOI BibTeX RDF
20	Ringi Kim, Luke Postle	The list linear arboricity of graphs.	J. Graph Theory	2021	DBLP DOI BibTeX RDF
20	Reut Levi	Testing Triangle Freeness in the General Model in Graphs with Arboricity O(√n).	ICALP	2021	DBLP DOI BibTeX RDF
20	Adir Morgan, Shay Solomon, Nicole Wein	Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial.	DISC	2021	DBLP DOI BibTeX RDF
20	Mélanie Cambus, Davin Choo, Havu Miikonen, Jara Uitto	Massively Parallel Correlation Clustering in Bounded Arboricity Graphs.	DISC	2021	DBLP DOI BibTeX RDF
20	Hao Sun	An Improved Approximation Bound for Minimum Weight Dominating Set on Graphs of Bounded Arboricity.	WAOA	2021	DBLP DOI BibTeX RDF
20	Narek A. Hovhannisyan	On distributed forest decomposition of graphs with bounded arboricity.	CCWC	2021	DBLP DOI BibTeX RDF
20	Hossein Jowhari	An Estimator for Matching Size in Low Arboricity Graphs with Two Applications.	APPROX-RANDOM	2021	DBLP DOI BibTeX RDF
20	Asaf Ferber, Jacob Fox, Vishesh Jain	Towards the linear arboricity conjecture.	J. Comb. Theory, Ser. B	2020	DBLP DOI BibTeX RDF
20	Winfried Hochstättler, Felix Schröder, Raphael Steiner	On the Complexity of Digraph Colourings and Vertex Arboricity.	Discret. Math. Theor. Comput. Sci.	2020	DBLP DOI BibTeX RDF
20	Talya Eden, Reut Levi, Dana Ron	Testing Bounded Arboricity.	ACM Trans. Algorithms	2020	DBLP DOI BibTeX RDF
20	Niranka Banerjee, Venkatesh Raman 0001, Saket Saurabh 0001	Fully dynamic arboricity maintenance.	Theor. Comput. Sci.	2020	DBLP DOI BibTeX RDF
20	Xuyang Cui, Wenshun Teng, Xing Liu, Huijuan Wang	A note of vertex arboricity of planar graphs without 4-cycles intersecting with 6-cycles.	Theor. Comput. Sci.	2020	DBLP DOI BibTeX RDF
20	Allan Bickle	A short proof of Brooks' Theorem for vertex arboricity.	AKCE Int. J. Graphs Comb.	2020	DBLP DOI BibTeX RDF
20	Monika Henzinger, Stefan Neumann 0003, Andreas Wiese	Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity.	CoRR	2020	DBLP BibTeX RDF
20	Manu Basavaraju, Arijit Bishnu, Mathew C. Francis, Drimit Pattanayak	The linear arboricity conjecture for 3-degenerate graphs.	CoRR	2020	DBLP BibTeX RDF
20	Han Xiao 0003, Qizhi Fang	Arboricity Games: the Core and the Nucleolus.	CoRR	2020	DBLP BibTeX RDF
20	Hossein Jowhari	An Estimator for Matching Size in Low Arboricity Graphs with Two Applications.	CoRR	2020	DBLP BibTeX RDF
20	Wenshun Teng, Huijuan Wang	Vertex arboricity of graphs embedded in a surface of non-negative Euler characteristic.	Discret. Math. Algorithms Appl.	2020	DBLP DOI BibTeX RDF
20	Talya Eden, Dana Ron, C. Seshadhri 0001	Faster sublinear approximation of the number of k-cliques in low-arboricity graphs.	SODA	2020	DBLP DOI BibTeX RDF
20	Manu Basavaraju, Arijit Bishnu, Mathew C. Francis, Drimit Pattanayak	The Linear Arboricity Conjecture for 3-Degenerate Graphs.	WG	2020	DBLP DOI BibTeX RDF
20	Markus Blumenstock, Frank Fischer 0002	A Constructive Arboricity Approximation Scheme.	SOFSEM	2020	DBLP DOI BibTeX RDF
20	Renyu Xu	The list linear arboricity of planar graphs with 7-cycles containing at most two chords.	Appl. Math. Comput.	2019	DBLP DOI BibTeX RDF
20	Huijuan Wang, Lidong Wu, Miltiades P. Pardalos, Hongwei Du 0001, Bin Liu 0009	An efficient case for computing minimum linear arboricity with small maximum degree.	Optim. Lett.	2019	DBLP DOI BibTeX RDF
20	Talya Eden, Dana Ron, C. Seshadhri 0001	Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection.	SIAM J. Discret. Math.	2019	DBLP DOI BibTeX RDF
20	Xin Zhang 0017, Bei Niu, Yan Li, Bi Li 0004	Equitable vertex arboricity of $d$-degenerate graphs.	CoRR	2019	DBLP BibTeX RDF
20	Talya Eden, Dana Ron, Will Rosenbaum	The Arboricity Captures the Complexity of Sampling Edges.	CoRR	2019	DBLP BibTeX RDF
20	Sebastián González Hermosillo de la Maza, Pavol Hell, César Hernández-Cruz, Seyyed Aliasghar Hosseini, Payam Valadkhan	Vertex arboricity of cographs.	CoRR	2019	DBLP BibTeX RDF
20	Juan Liu, Xiaoxue Hu, Weifan Wang 0001, Yiqiao Wang 0002	Light structures in 1-planar graphs with an application to linear 2-arboricity.	Discret. Appl. Math.	2019	DBLP DOI BibTeX RDF
20	Tomasz Bartnicki, Bartlomiej Bosek, Sebastian Czerwinski, Michal Farnik, Jaroslaw Grytczuk, Zofia Miechowicz	Generalized arboricity of graphs with large girth.	Discret. Math.	2019	DBLP DOI BibTeX RDF
20	Martin Merker, Luke Postle	Bounded diameter arboricity.	J. Graph Theory	2019	DBLP DOI BibTeX RDF
20	Mohsen Ghaffari 0001, Ali Sayyadi	Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication.	ICALP	2019	DBLP DOI BibTeX RDF
20	Talya Eden, Dana Ron, Will Rosenbaum	The Arboricity Captures the Complexity of Sampling Edges.	ICALP	2019	DBLP DOI BibTeX RDF
20	Niranka Banerjee, Venkatesh Raman 0001, Saket Saurabh 0001	Fully Dynamic Arboricity Maintenance.	COCOON	2019	DBLP DOI BibTeX RDF
20	Shengjie He, Rong-Xia Hao, Liancui Zuo	The linear (n-1)-arboricity of some lexicographic product graphs.	Appl. Math. Comput.	2018	DBLP DOI BibTeX RDF
20	Maria Axenovich, Daniel Gonçalves 0001, Jonathan Rollin, Torsten Ueckerdt	The k-strong induced arboricity of a graph.	Eur. J. Comb.	2018	DBLP DOI BibTeX RDF
20	Markus Blumenstock	A (4/3+ε)-Approximation Algorithm for Arboricity From Pseudoforest Partitions.	CoRR	2018	DBLP BibTeX RDF
20	Asaf Ferber, Jacob Fox, Vishesh Jain	Towards the linear arboricity conjecture.	CoRR	2018	DBLP BibTeX RDF
20	Talya Eden, Dana Ron, C. Seshadhri 0001	Faster sublinear approximations of k-cliques for low arboricity graphs.	CoRR	2018	DBLP BibTeX RDF
20	Timothy Chu, Michael B. Cohen, Jakub W. Pachocki, Richard Peng	Constant Arboricity Spectral Sparsifiers.	CoRR	2018	DBLP BibTeX RDF
20	Changqing Xu, Zongzheng Zhao, Mei Yao	On the Linear 2-Arboricity of Planar Graphs without Intersecting 3-Cycles or Intersecting 4-Cycles.	Ars Comb.	2018	DBLP BibTeX RDF
20	Liancui Zuo, Chunhong Shang, Shaoqiang Zhang, Shengjie He	The linear t-arboricity of complete bipartite graphs.	Ars Comb.	2018	DBLP BibTeX RDF
20	Yiqiao Wang 0002, Min Chen 0012, Weifan Wang 0001	A note on the list vertex arboricity of toroidal graphs.	Discret. Math.	2018	DBLP DOI BibTeX RDF
20	Pu Gao, Xavier Pérez-Giménez, Cristiane M. Sato	Arboricity and spanning-tree packing in random graphs.	Random Struct. Algorithms	2018	DBLP DOI BibTeX RDF
20	Hua Cai, Jianliang Wu, Lin Sun	Vertex arboricity of planar graphs without intersecting 5-cycles.	J. Comb. Optim.	2018	DBLP DOI BibTeX RDF
20	Andrew McGregor 0001, Sofya Vorotnikova	A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs.	SOSA	2018	DBLP DOI BibTeX RDF
20	Talya Eden, Reut Levi, Dana Ron	Testing bounded arboricity.	SODA	2018	DBLP DOI BibTeX RDF
20	Henri Perret du Cray, Mourad Baïou, Laurent Beaudou, Vincent Limouzy	Bounds on Directed star arboricity in some digraph classes.	Electron. Notes Discret. Math.	2017	DBLP DOI BibTeX RDF
20	Yiqiao Wang 0002	On the linear 2-arboricity of planar graph without normally adjacent 3-cycles and 4-cycles.	Int. J. Comput. Math.	2017	DBLP DOI BibTeX RDF
20	Keaitsuda Maneeruk Nakprasit, Kittikorn Nakprasit	The strong equitable vertex 2-arboricity of complete bipartite and tripartite graphs.	Inf. Process. Lett.	2017	DBLP DOI BibTeX RDF
20	Nikhil Bansal 0001, Seeun William Umboh	Tight approximation bounds for dominating set on graphs of bounded arboricity.	Inf. Process. Lett.	2017	DBLP DOI BibTeX RDF
20	Talya Eden, Reut Levi, Dana Ron	Testing bounded arboricity.	CoRR	2017	DBLP BibTeX RDF
20	Weichan Liu, Chen Gong, Lifang Wu, Xin Zhang	A note on the vertex arboricity of signed graphs.	CoRR	2017	DBLP BibTeX RDF
20	Ling Xue	List vertex arboricity of planar graphs with 5-cycles not adjacent to 3-cycles and 4-cycles.	Ars Comb.	2017	DBLP BibTeX RDF
20	Xin Zhang	List vertex arboricity of graphs without forbidden minors.	Ars Comb.	2017	DBLP BibTeX RDF
20	Yuanchao Li, Xiaoxue Hu	The linear 2-arboricity of sparse graphs.	Discret. Math. Algorithms Appl.	2017	DBLP DOI BibTeX RDF
20	Yiqiao Wang 0002, Xiaoxue Hu, Wei-Fan Wang 0001	A note on the linear 2-arboricity of planar graphs.	Discret. Math.	2017	DBLP DOI BibTeX RDF
20	Guantao Chen, Yuping Gao, Songling Shan, Guanghui Wang 0002, Jianliang Wu	Equitable vertex arboricity of 5-degenerate graphs.	J. Comb. Optim.	2017	DBLP DOI BibTeX RDF
20	Nan Jia, Jun Yin, Chunxia Wang, Xia Wang	Linear k-Arboricity of Hypohamiltonian Graphs with Small Order.	ISPAN-FCST-ISCC	2017	DBLP DOI BibTeX RDF