Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
From MaRDI portal
(Redirected from Publication:684119)
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.
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
Cites work
- scientific article; zbMATH DE number 434910 (Why is no real title available?)
- scientific article; zbMATH DE number 1496580 (Why is no real title available?)
- 3-list-coloring planar graphs of girth 5
- A non-3-choosable planar graph without cycles of length 4 and 5
- A not 3-choosable planar graph without 3-cycles
- Colorings of plane graphs: a survey
- Every planar graph is 5-choosable
- Every planar map is four colorable. I: Discharging
- List colourings of planar graphs
- On DP-coloring of graphs and multigraphs
- Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
- Planar graphs without cycles of length from 4 to 7 are 3-colorable
- Sharp Dirac's theorem for DP-critical graphs
- Steinberg's conjecture is false
- Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
- The asymptotic behavior of the correspondence chromatic number
Cited in
(only showing first 100 items - show all)- 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
- Relation between the correspondence chromatic number and the Alon-Tarsi number
- Separating the online and offline DP-chromatic numbers
- Weak degeneracy of planar graphs and locally planar 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
- Partial DP-coloring of graphs
- Decompositions of graphs of nonnegative characteristic with some forbidden subgraphs
- 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
- Toroidal graphs without \(K_5^-\) and 6-cycles
- Single‐conflict colouring
- Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable
- Weak degeneracy of graphs
- An extension of Thomassen's result on choosability
- Planar graphs without chordal 6-cycles and necklaces are DP-4-colorable
- 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
- A note on fractional DP-coloring of graphs
- DP-3-coloring of planar graphs without 4, 9-cycles and cycles of two lengths from \(\{6,7,8\}\)
- DP‐coloring Cartesian products of graphs
- DP-3-coloring of some planar graphs
- Variable degeneracy on toroidal graphs
- On the list color function threshold
- Planar graphs without intersecting 5-cycles are signed-4-choosable
- 4-choosability of planar graphs with 4-cycles far apart via the Combinatorial Nullstellensatz
- Sufficient conditions on planar graphs to have a relaxed DP-3-coloring
- Combinatorial Nullstellensatz and DP-coloring of graphs
- DP color functions versus chromatic polynomials (II)
- Every planar graph without 5-cycles adjacent to 6-cycles is DP-4-colorable
- 3-paintability of planar 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
- Coloring permutation-gain graphs
- Sufficient conditions for planar graphs without 4-cycles and 5-cycles to be 2-degenerate
- DP-colorings of hypergraphs
- DP-4-coloring of planar graphs with some restrictions on cycles
- 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 local epsilon version of Reed's conjecture
- A weak DP-partitioning of planar graphs without 4-cycles and 6-cycles
- Planar graphs without normally adjacent short cycles
- Colouring graphs with forbidden bipartite subgraphs
- Colouring of \(S\)-labelled planar graphs
- Upper bound for DP-chromatic number of a graph
- Generalized signed graphs of large girth and large chromatic number
- Planar graphs having no cycle of length 4, 7, or 9 are DP-3-colorable
- Answers to two questions on the DP color function
- Concepts on coloring of cluster hypergraphs with application
- 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
- DP-coloring on planar graphs without given adjacent short cycles
- On DP-coloring of graphs and multigraphs
- A deletion-contraction relation for the DP color function
- Signed colouring and list colouring of k‐chromatic graphs
- DP-4-colorability of two classes of planar graphs
- On the chromatic polynomial and counting DP-colorings of graphs
- Fractional DP-chromatic number of planar graphs of large girth
- Differences between the list-coloring and DP-coloring for planar graphs
- Exponentially many \(\mathbb{Z}_5\)-colorings in simple planar graphs
- A weak DP-coloring of planar graphs without 4- and 9-cycles
- On triangle-free list assignments
- Packing list‐colorings
- Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques
- Asymptotically good edge correspondence colourings
- Edge DP-coloring in planar graphs
- 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
- 5‐Coloring reconfiguration of planar graphs with no short odd cycles
- Light 3-faces in 3-polytopes without adjacent triangles
- Group colorings and DP-colorings of multigraphs using edge-disjoint decompositions
- Symmetric set coloring of signed graphs
- On-line DP-coloring of graphs
- An algebraic approach for counting DP-3-colorings of sparse graphs
- Light 3-paths in 3-polytopes without adjacent triangles
- Sparse critical graphs for defective DP-colorings
- DP-colorings of uniform hypergraphs and splittings of Boolean hypercube into faces
- The harmonic index of a graph and its DP-chromatic number
- An analogue of DP-coloring for variable degeneracy and its applications
- A refinement of choosability of graphs
- Generalized DP-colorings of graphs
- Defective and clustered choosability of sparse graphs
- A \((2, 1)\)-decomposition of planar graphs without intersecting 3-cycles and adjacent \(4^-\)-cycles
- Colouring graphs with sparse neighbourhoods: bounds and applications
- The DP color function of joins and vertex-gluings of graphs
- Weak degeneracy of planar graphs without 4- and 6-cycles
- Variable degeneracy of planar graphs without chorded 6-cycles
- On colorings and orientations of signed graphs
- Cooperative colorings of forests
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)
