Vertex arboricity and maximum degree

DOI10.1016/0012-365X(93)E0205-IzbMath0827.05024OpenAlexW2013436809MaRDI QIDQ1894756

Hong-Jian Lai, Paul A. Catlin

Publication date: 24 July 1995

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(93)e0205-i

zbMATH Keywords

chromatic numbercoloringcolorsmaximum degreearboricityforests

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (18)

Unnamed Item ⋮ A Catlin-type theorem for graph partitioning avoiding prescribed subgraphs ⋮ On the vertex arboricity of planar graphs of diameter two ⋮ Independent feedback vertex sets for graphs of bounded diameter ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ On the vertex-arboricity of planar graphs ⋮ Partitioning of a graph into induced subgraphs not containing prescribed cliques ⋮ On the vertex-arboricity of \(K_5\)-minor-free graphs of diameter 2 ⋮ On the vertex-arboricity of planar graphs without 7-cycles ⋮ Sparse Graphs Are Near-Bipartite ⋮ A unified proof of Brooks' theorem and Catlin's theorem ⋮ Tree coloring of distance graphs with a real interval set ⋮ Partitioning a graph into degenerate subgraphs ⋮ Circular vertex arboricity ⋮ Vertex partition of hypergraphs and maximum degenerate subhypergraphs ⋮ Vertex arboricity of integer distance graph \(G(D_{m,k})\) ⋮ Recognizing Graphs Close to Bipartite Graphs ⋮ Vertex arboricity of planar graphs without chordal 6-cycles

Cites Work

• Brooks' graph-coloring theorem and the independence number
• A short proof of Catlin's extension of Brooks' theorem
• The point-arboricity of a graph
• Bounds for the vertex linear arboricity
• Critical Point-Arboritic Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Vertex arboricity and maximum degree