List-coloring graphs without subdivisions and without immersions
From MaRDI portal
Publication:5743487
zbMATH Open1425.05153MaRDI QIDQ5743487FDOQ5743487
Authors: Ken-ichi Kawarabayashi, Yusuke Kobayashi 
Publication date: 10 May 2019
Full work available at URL: https://dl.acm.org/citation.cfm?id=2095228
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
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Graph minors. X: Obstructions to tree-decomposition
- Approximate graph coloring by semidefinite programming
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Graph minors. XX: Wagner's conjecture
- A bound on the chromatic number of a graph
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Graph minors. XIII: The disjoint paths problem
- Über eine Eigenschaft der ebenen Komplexe
- Graphs on surfaces
- An extremal function for contractions of graphs
- Nonconstructive tools for proving polynomial-time decidability
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lower bound of the Hadwiger number of graphs by their average degree
- Graph minors. V. Excluding a planar graph
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Disjoint paths in graphs
- 2-linked graphs
- Highly connected sets and the excluded grid theorem
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- Five-coloring maps on surfaces
- Every planar graph is 5-choosable
- Quickly excluding a planar graph
- The four-colour theorem
- Color-critical graphs on a fixed surface
- Graph colorings with local constraints -- a survey
- Title not available (Why is that?)
- Title not available (Why is that?)
- Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
- Topological cliques in graphs II
- Title not available (Why is that?)
- Inapproximability of vertex cover and independent set in bounded degree graphs
- Zero knowledge and the chromatic number
- On the conjecture of Hajos
- Graph coloring and the immersion order
- Immersing small complete graphs
- Title not available (Why is that?)
- A minimum degree condition forcing complete graph immersion
- Fast Algorithms forK4Immersion Testing
- An improved algorithm for finding tree decompositions of small width
- Topological cliques of random graphs
- List colourings of planar graphs
- Graph minors XXIII. Nash-Williams' immersion conjecture
- The complexity of planar graph choosability
- Graph minors. XVI: Excluding a non-planar graph
- On the complexity of some colorful problems parameterized by treewidth
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
- Linear connectivity forces large complete bipartite minors
- On the excluded minor structure theorem for graphs of large tree-width
- The Erdős-Pósa property for clique minors in highly connected graphs
- Locally planar graphs are 5-choosable
- A simpler algorithm and shorter proof for the graph minor decomposition
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- On the presence of disjoint subgraphs of a specified type
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Hadwiger's conjecture is decidable
- Graph minors. XIX: Well-quasi-ordering on a surface.
- Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
- Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
- Grids and their minors
- Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
- Approximating List-Coloring on a Fixed Surface
Cited In (6)
- Immersion and clustered coloring
- Characterizing graphs of small carving-width
- Coloring immersion-free graphs
- The structure of graphs not admitting a fixed immersion
- The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
- 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)
