Clustered coloring of graphs with bounded layered treewidth and bounded degree

DOI10.1016/J.EJC.2023.103730MaRDI QIDQ6612290zbMATH OpenFDO

Authors Chun-Hung Liu, David R. Wood

Publication date 30 September 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.EJC.2023.103730

zbMATH Keywords

colorings with bounded clustering

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35)

Recommendations

• Clustered 3-colouring graphs of bounded degree
• Clustered colouring of graph classes with bounded treedepth or pathwidth
• Clustered colouring in minor-closed classes
• Defective and clustered graph colouring

Cites work

• A partial k-arboretum of graphs with bounded treewidth
• A relaxed Hadwiger's conjecture for list colorings
• A separator theorem for string graphs and its applications
• A Weakening of the Odd Hadwiger's Conjecture
• Applications of a new separator theorem for string graphs
• Approximation algorithms for independent sets in map graphs
• Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces
• Bounded size components -- partitions and transversals.
• Clustered 3-colouring graphs of bounded degree
• Clustered colouring in minor-closed classes
• Colouring planar graphs with three colours and no large monochromatic components
• Colourings with Bounded Monochromatic Components in Graphs of Given Circumference
• Decidability of string graphs
• Defective and clustered choosability of sparse graphs
• Defective and clustered graph colouring
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• scientific article; zbMATH DE number 1944139 (Why is no real title available?)
• scientific article; zbMATH DE number 7053376 (Why is no real title available?)
• scientific article; zbMATH DE number 7788457 (Why is no real title available?)
• Immersion and clustered coloring
• Improper coloring of graphs on surfaces
• Improper colouring of graphs with no odd clique minor
• Improper colourings inspired by Hadwiger's conjecture
• Layered separators in minor-closed graph classes with applications
• Map graphs
• New bounds on the edge number of ak-map graph
• Orthogonal tree decompositions of graphs
• Parameters tied to treewidth
• Partitioning \(H\)-minor free graphs into three subgraphs with no large components
• Partitioning into graphs with only small components
• Recognizing string graphs in NP
• Recognizing string graphs is decidable
• String graphs. II: Recognizing string graphs is NP-hard
• Structure of graphs with locally restricted crossings
• The Game of Hex and the Brouwer Fixed-Point Theorem

Cited in

(5)

• Colouring strong products
• Weak diameter choosability of graphs with an excluded minor
• Clustered coloring of (path + 2K₁)-free graphs on surfaces
• Assouad-Nagata dimension of minor-closed metrics
• Defective and clustered colouring of graphs with given girth

This page was built for publication: Clustered coloring of graphs with bounded layered treewidth and bounded degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6612290)