scientific article; zbMATH DE number 7053364
From MaRDI portal
zbMath1425.05153MaRDI QIDQ5743487
Ken-ichi Kawarabayashi, Yusuke Kobayashi
Publication date: 10 May 2019
Full work available at URL: https://dl.acm.org/citation.cfm?id=2095228
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Characterizing graphs of small carving-width, The structure of graphs not admitting a fixed immersion, The Erdős-Pósa property for edge-disjoint immersions in 4-edge-connected graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A minimum degree condition forcing complete graph immersion
- The Erdős-Pósa property for clique minors in highly connected graphs
- Topological cliques of random graphs
- On the complexity of some colorful problems parameterized by treewidth
- List colourings of planar graphs
- Graph minors. XX: Wagner's conjecture
- Lower bound of the Hadwiger number of graphs by their average degree
- Locally planar graphs are 5-choosable
- Graph minors XXIII. Nash-Williams' immersion conjecture
- Linear connectivity forces large complete bipartite minors
- Graph minors. V. Excluding a planar graph
- Grids and their minors
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- The complexity of planar graph choosability
- Disjoint paths in graphs
- 2-linked graphs
- Graph minors. X: Obstructions to tree-decomposition
- 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
- Zero knowledge and the chromatic number
- Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
- 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 minors. XVI: Excluding a non-planar graph
- Graph minors. XIX: Well-quasi-ordering on a surface.
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Excluding any graph as a minor allows a low tree-width 2-coloring
- On the conjecture of Hajos
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Graph minors. XIII: The disjoint paths problem
- On the excluded minor structure theorem for graphs of large tree-width
- Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor
- Über eine Eigenschaft der ebenen Komplexe
- Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
- Graph Coloring and the Immersion Order
- Immersing small complete graphs
- An extremal function for contractions of graphs
- Approximating List-Coloring on a Fixed Surface
- Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
- Nonconstructive tools for proving polynomial-time decidability
- On the presence of disjoint subgraphs of a specified type
- Approximate graph coloring by semidefinite programming
- Graph colorings with local constraints -- a survey
- Fast Algorithms forK4Immersion Testing
- Topological cliques in graphs II
- Hadwiger's conjecture is decidable
- AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
- A simpler algorithm and shorter proof for the graph minor decomposition
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
