Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
From MaRDI portal
Publication:684119
DOI10.1016/J.JCTB.2017.09.001zbMATH Open1379.05034arXiv1508.03437OpenAlexW2963609862MaRDI QIDQ684119FDOQ684119
Authors: Zdeněk Dvořák, Luke Postle 
Publication date: 9 February 2018
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Abstract: We introduce a new variant of graph coloring called correspondence coloring which generalizes list coloring and allows for reductions previously only possible for ordinary coloring. Using this tool, we prove that excluding cycles of lengths 4 to 8 is sufficient to guarantee 3-choosability of a planar graph, thus answering a question of Borodin.
Full work available at URL: https://arxiv.org/abs/1508.03437
Recommendations
- List coloring of planar graphs with forbidden cycles
- Every planar graph without adjacent cycles of length at most 8 is 3-choosable
- DP-4-colorability of two classes of planar graphs
- Planar graphs without normally adjacent short cycles
- Planar graphs without cycles of length from 4 to 7 and intersecting triangles are DP-3-colorable
Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Every planar map is four colorable. I: Discharging
- Colorings of plane graphs: a survey
- Every planar graph is 5-choosable
- Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
- 3-list-coloring planar graphs of girth 5
- Title not available (Why is that?)
- Title not available (Why is that?)
- List colourings of planar graphs
- Planar graphs without cycles of length from 4 to 7 are 3-colorable
- Steinberg's conjecture is false
- Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
- A non-3-choosable planar graph without cycles of length 4 and 5
- A not 3-choosable planar graph without 3-cycles
- On DP-coloring of graphs and multigraphs
- The asymptotic behavior of the correspondence chromatic number
- Sharp Dirac's theorem for DP-critical graphs
Cited In (only showing first 100 items - show all)
- Every planar graph without adjacent cycles of length at most 8 is 3-choosable
- Every planar graph without pairwise adjacent 3-, 4-, and 5-cycle is DP-4-colorable
- Single‐conflict colouring
- Weak degeneracy of graphs
- Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable
- An extension of Thomassen's result on choosability
- A sufficient condition for planar graphs to be DP-4-colorable
- Relaxed DP-coloring and another generalization of DP-coloring on planar graphs without 4-cycles and 7-cycles
- DP-3-coloring of planar graphs without 4, 9-cycles and cycles of two lengths from \(\{6,7,8\}\)
- 4-choosability of planar graphs with 4-cycles far apart via the Combinatorial Nullstellensatz
- DP-3-coloring of some planar graphs
- DP color functions versus chromatic polynomials (II)
- Every planar graph without 5-cycles adjacent to 6-cycles is DP-4-colorable
- Sufficient conditions on planar graphs to have a relaxed DP-3-coloring
- Combinatorial Nullstellensatz and DP-coloring of graphs
- Concepts of signed graph coloring
- Notes on the harmonic index of graphs
- Coloring squares of graphs with mad constraints
- A sufficient condition for DP-4-colorability
- Sufficient conditions for planar graphs without 4-cycles and 5-cycles to be 2-degenerate
- DP-colorings of hypergraphs
- A local epsilon version of Reed's conjecture
- DP-4-coloring of planar graphs with some restrictions on cycles
- Planar graphs without normally adjacent short cycles
- Colouring of \(S\)-labelled planar graphs
- Answers to two questions on the DP color function
- DP-coloring on planar graphs without given adjacent short cycles
- DP color functions versus chromatic polynomials
- Note on 3-choosability of planar graphs with maximum degree 4
- On 2-defective DP-colorings of sparse graphs
- On DP-coloring of graphs and multigraphs
- A deletion-contraction relation for the DP color function
- DP-4-colorability of two classes of planar graphs
- On the chromatic polynomial and counting DP-colorings of graphs
- Differences between the list-coloring and DP-coloring for planar graphs
- Exponentially many \(\mathbb{Z}_5\)-colorings in simple planar graphs
- Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques
- A note on the DP-chromatic number of complete bipartite graphs
- Proper distinguishing colorings with few colors for graphs with girth at least 5
- Planar graphs without \(\{4, 6, 8\}\)-cycles are 3-choosable
- Non-chromatic-adherence of the DP color function via generalized theta graphs
- Group colorings and DP-colorings of multigraphs using edge-disjoint decompositions
- On-line DP-coloring of graphs
- Generalized DP-colorings of graphs
- A refinement of choosability of graphs
- An analogue of DP-coloring for variable degeneracy and its applications
- The harmonic index of a graph and its DP-chromatic number
- A \((2, 1)\)-decomposition of planar graphs without intersecting 3-cycles and adjacent \(4^-\)-cycles
- Weak degeneracy of planar graphs without 4- and 6-cycles
- Colouring graphs with sparse neighbourhoods: bounds and applications
- On colorings and orientations of signed graphs
- The DP color function of joins and vertex-gluings of graphs
- Counting colorings of triangle-free graphs
- Cover and variable degeneracy
- DP-\(4\)-colorability of planar graphs without intersecting \(5\)-cycles
- Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable
- Independent transversals in bipartite correspondence-covers
- Planar graphs without cycles of length from 4 to 7 and intersecting triangles are DP-3-colorable
- Planar graphs without 7-cycles and butterflies are DP-4-colorable
- A generalization of some results on list coloring and DP-coloring
- Complexity of correspondence \(H\)-colourings
- Relaxed DP-3-coloring of planar graphs without some cycles
- List coloring of planar graphs with forbidden cycles
- DP-degree colorable hypergraphs
- Defective DP-colorings of sparse multigraphs
- Defective DP-colorings of sparse simple graphs
- Multiple DP-coloring of planar graphs without 3-cycles and normally adjacent 4-cycles
- Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable
- DP-3-coloring of planar graphs without certain cycles
- Planar graphs without specific cycles are 2-degenerate
- Decompositions of graphs of nonnegative characteristic with some forbidden subgraphs
- Toroidal graphs without \(K_5^-\) and 6-cycles
- Planar graphs without chordal 6-cycles and necklaces are DP-4-colorable
- A note on fractional DP-coloring of graphs
- DP‐coloring Cartesian products of graphs
- Variable degeneracy on toroidal graphs
- On the list color function threshold
- Planar graphs without intersecting 5-cycles are signed-4-choosable
- 3-paintability of planar graphs
- Coloring permutation-gain graphs
- Adaptable and conflict colouring multigraphs with no cycles of length three or four
- ZDP(n) ${Z}_{DP}(n)$ is bounded above by n2−(n+3)∕2 ${n}^{2}-(n+3)\unicode{x02215}2$
- A weak DP-partitioning of planar graphs without 4-cycles and 6-cycles
- Colouring graphs with forbidden bipartite subgraphs
- Planar graphs having no cycle of length 4, 7, or 9 are DP-3-colorable
- Upper bound for DP-chromatic number of a graph
- Generalized signed graphs of large girth and large chromatic number
- Concepts on coloring of cluster hypergraphs with application
- Signed colouring and list colouring of k‐chromatic graphs
- Fractional DP-chromatic number of planar graphs of large girth
- A weak DP-coloring of planar graphs without 4- and 9-cycles
- On triangle-free list assignments
- Packing list‐colorings
- Asymptotically good edge correspondence colourings
- Edge DP-coloring in planar graphs
- 5‐Coloring reconfiguration of planar graphs with no short odd cycles
- Light 3-faces in 3-polytopes without adjacent triangles
- Symmetric set coloring of signed graphs
- An algebraic approach for counting DP-3-colorings of sparse graphs
- Light 3-paths in 3-polytopes without adjacent triangles
This page was built for publication: Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q684119)
