Colouring graphs with bounded generalized colouring number
From MaRDI portal
Publication:1045038
DOI10.1016/j.disc.2008.03.024zbMath1216.05043OpenAlexW2149573503MaRDI QIDQ1045038
Publication date: 15 December 2009
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2008.03.024
Related Items
Improved bounds for weak coloring numbers ⋮ Characterising bounded expansion by neighbourhood complexity ⋮ Rainbow independent sets on dense graph classes ⋮ Chromatic numbers of exact distance graphs ⋮ Coloring and Covering Nowhere Dense Graphs ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ On coloring numbers of graph powers ⋮ Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth ⋮ Adapted game colouring of graphs ⋮ On low tree-depth decompositions ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes ⋮ Graph product structure for non-minor-closed classes ⋮ A color-avoiding approach to subgraph counting in bounded expansion classes ⋮ Dimension is polynomial in height for posets with planar cover graphs ⋮ Bounding generalized coloring numbers of planar graphs using coin models ⋮ On nowhere dense graphs ⋮ Many Facets of Dualities ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Clustering powers of sparse graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Colouring edges with many colours in cycles ⋮ Polynomial treedepth bounds in linear colorings ⋮ Uniform orderings for generalized coloring numbers ⋮ Characterisations and examples of graph classes with bounded expansion ⋮ On the weak 2-coloring number of planar graphs ⋮ Polynomial bounds for centered colorings on proper minor-closed graph classes ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Rank-width and tree-width of \(H\)-minor-free graphs ⋮ Unnamed Item ⋮ On low rank-width colorings ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ Bounds on vertex colorings with restrictions on the union of color classes ⋮ Notes on graph product structure theory ⋮ Colouring games on outerplanar graphs and trees ⋮ Colouring and Covering Nowhere Dense Graphs ⋮ Twin-width and generalized coloring numbers ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ Sublinear Separators in Intersection Graphs of Convex Shapes ⋮ Generalization of transitive fraternal augmentations for directed graphs and its applications ⋮ Digraphs of Bounded Width ⋮ Counting Homomorphisms to Sparse Graphs ⋮ 2-coloring number revisited ⋮ Erdös--Hajnal Properties for Powers of Sparse Graphs ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
Cites Work
- A simple competitive graph coloring algorithm
- Orderings on graphs and game coloring number
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Graphs with linearly bounded Ramsey numbers
- Tree-depth, subgraph coloring and homomorphism bounds
- Linear time low tree-width partitions and algorithmic consequences
- An extremal function for contractions of graphs
- Radius two trees specify χ‐bounded classes
- Unnamed Item
