List-coloring graphs without subdivisions and without immersions
From MaRDI portal
(Redirected from Publication:5743487)
Recommendations
- Coloring immersion-free graphs
- Additive approximation algorithms for list-coloring minor-closed class of graphs
- Immersion and clustered coloring
- Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
- Clustered variants of Hajós' conjecture
Cites work
- 2-linked graphs
- A bound on the chromatic number of a graph
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A minimum degree condition forcing complete graph immersion
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
- A simpler algorithm and shorter proof for the graph minor decomposition
- An extremal function for contractions of graphs
- An improved algorithm for finding tree decompositions of small width
- Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
- Approximate graph coloring by semidefinite programming
- Approximating List-Coloring on a Fixed Surface
- Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Color-critical graphs on a fixed surface
- Disjoint paths in graphs
- Every planar graph is 5-choosable
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Fast Algorithms forK4Immersion Testing
- Five-coloring maps on surfaces
- Graph coloring and the immersion order
- Graph colorings with local constraints -- a survey
- Graph minors XXIII. Nash-Williams' immersion conjecture
- Graph minors. V. Excluding a planar graph
- Graph minors. X: Obstructions to tree-decomposition
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XIX: Well-quasi-ordering on a surface.
- Graph minors. XVI: Excluding a non-planar graph
- Graph minors. XX: Wagner's conjecture
- Graphs on surfaces
- Grids and their minors
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- Hadwiger's conjecture is decidable
- Highly connected sets and the excluded grid theorem
- scientific article; zbMATH DE number 446487 (Why is no real title available?)
- scientific article; zbMATH DE number 4104981 (Why is no real title available?)
- scientific article; zbMATH DE number 3735847 (Why is no real title available?)
- scientific article; zbMATH DE number 1057879 (Why is no real title available?)
- scientific article; zbMATH DE number 821271 (Why is no real title available?)
- scientific article; zbMATH DE number 1432797 (Why is no real title available?)
- scientific article; zbMATH DE number 3215864 (Why is no real title available?)
- scientific article; zbMATH DE number 3102312 (Why is no real title available?)
- Immersing small complete graphs
- Inapproximability of vertex cover and independent set in bounded degree graphs
- Linear connectivity forces large complete bipartite minors
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- List colourings of planar graphs
- List-color-critical graphs on a fixed surface
- Locally planar graphs are 5-choosable
- Lower bound of the Hadwiger number of graphs by their average degree
- Nonconstructive tools for proving polynomial-time decidability
- On the complexity of some colorful problems parameterized by treewidth
- On the conjecture of Hajos
- On the excluded minor structure theorem for graphs of large tree-width
- On the presence of disjoint subgraphs of a specified type
- Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
- Quickly excluding a planar graph
- The complexity of planar graph choosability
- The Erdős-Pósa property for clique minors in highly connected graphs
- The four-colour theorem
- Topological cliques in graphs II
- Topological cliques of random graphs
- Über eine Eigenschaft der ebenen Komplexe
- Zero knowledge and the chromatic number
Cited in
(7)- The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
- Immersion and clustered coloring
- Characterizing graphs of small carving-width
- Coloring immersion-free graphs
- Additive approximation algorithms for list-coloring minor-closed class of graphs
- The structure of graphs not admitting a fixed immersion
- Totally odd subdivisions and parity subdivisions: structures and coloring
This page was built for publication: List-coloring graphs without subdivisions and without immersions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743487)
