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.001zbMath1379.05034arXiv1508.03437OpenAlexW2963609862MaRDI QIDQ684119
Publication date: 9 February 2018
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1508.03437
Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)
Related Items
On triangle-free list assignments ⋮ Packing list‐colorings ⋮ 5‐Coloring reconfiguration of planar graphs with no short odd cycles ⋮ 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 ⋮ On DP-coloring of graphs and multigraphs ⋮ DP-3-coloring of some planar graphs ⋮ Colouring graphs with forbidden bipartite subgraphs ⋮ Independent transversals in bipartite correspondence-covers ⋮ Colouring graphs with sparse neighbourhoods: bounds and applications ⋮ An extension of Thomassen's result on choosability ⋮ Upper bound for DP-chromatic number of a graph ⋮ Coloring permutation-gain graphs ⋮ Generalized signed graphs of large girth and large chromatic number ⋮ Planar graphs without normally adjacent short cycles ⋮ Fractional DP-chromatic number of planar graphs of large girth ⋮ 3-Paintability of planar graphs ⋮ A deletion-contraction relation for the DP color function ⋮ Proper distinguishing colorings with few colors for graphs with girth at least 5 ⋮ The DP color function of joins and vertex-gluings of graphs ⋮ Partial DP-coloring of graphs ⋮ Edge DP-coloring in planar graphs ⋮ DP-colorings of uniform hypergraphs and splittings of Boolean hypercube into faces ⋮ Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques ⋮ Correspondence homomorphisms to reflexive graphs ⋮ Planar graphs without \(\{4, 6, 8\}\)-cycles are 3-choosable ⋮ Complexity of correspondence \(H\)-colourings ⋮ Planar graphs without 7-cycles and butterflies are DP-4-colorable ⋮ Counting colorings of triangle-free graphs ⋮ Weak degeneracy of graphs ⋮ DP color functions versus chromatic polynomials (II) ⋮ ZDP(n) ${Z}_{DP}(n)$ is bounded above by n2−(n+3)∕2 ${n}^{2}-(n+3)\unicode{x02215}2$ ⋮ Adaptable and conflict colouring multigraphs with no cycles of length three or four ⋮ Planar graphs without intersecting 5-cycles are signed-4-choosable ⋮ Single‐conflict colouring ⋮ Signed colouring and list colouring of k‐chromatic graphs ⋮ On colorings and orientations of signed graphs ⋮ Notes on the harmonic index of graphs ⋮ DP‐coloring Cartesian products of graphs ⋮ A sufficient condition for planar graphs to be DP-4-colorable ⋮ Asymptotically good edge correspondence colourings ⋮ A \((2, 1)\)-decomposition of planar graphs without intersecting 3-cycles and adjacent \(4^-\)-cycles ⋮ A generalization of some results on list coloring and DP-coloring ⋮ Generalized DP-colorings of graphs ⋮ DP-colorings of hypergraphs ⋮ Decompositions of graphs of nonnegative characteristic with some forbidden subgraphs ⋮ Symmetric set coloring of signed graphs ⋮ Weak degeneracy of planar graphs and locally planar graphs ⋮ Separating the online and offline DP-chromatic numbers ⋮ Cooperative colorings of forests ⋮ 4-choosability of planar graphs with 4-cycles far apart via the Combinatorial Nullstellensatz ⋮ Variable degeneracy on toroidal graphs ⋮ On the list color function threshold ⋮ Weak degeneracy of planar graphs without 4- and 6-cycles ⋮ Concepts on coloring of cluster hypergraphs with application ⋮ On-line DP-coloring of graphs ⋮ A weak DP-partitioning of planar graphs without 4-cycles and 6-cycles ⋮ 不含带弦6-圈和项链图的平面图是DP-4-可染的 ⋮ A weak DP-coloring of planar graphs without 4- and 9-cycles ⋮ Decomposition of planar graphs with forbidden configurations ⋮ Relation between the correspondence chromatic number and the Alon-Tarsi number ⋮ Non-chromatic-adherence of the DP color function via generalized theta graphs ⋮ Unnamed Item ⋮ Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable ⋮ On the chromatic polynomial and counting DP-colorings of graphs ⋮ On 2-defective DP-colorings of sparse graphs ⋮ Concepts of signed graph coloring ⋮ Colouring of \(S\)-labelled planar graphs ⋮ Defective DP-colorings of sparse multigraphs ⋮ Sufficient conditions for planar graphs without 4-cycles and 5-cycles to be 2-degenerate ⋮ DP-4-coloring of planar graphs with some restrictions on cycles ⋮ Defective DP-colorings of sparse simple graphs ⋮ Every planar graph without pairwise adjacent 3-, 4-, and 5-cycle is DP-4-colorable ⋮ A sufficient condition for DP-4-colorability ⋮ DP-3-coloring of planar graphs without 4, 9-cycles and cycles of two lengths from \(\{6,7,8\}\) ⋮ Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable ⋮ Sufficient conditions on planar graphs to have a relaxed DP-3-coloring ⋮ Combinatorial Nullstellensatz and DP-coloring of graphs ⋮ Coloring squares of graphs with mad constraints ⋮ DP-3-coloring of planar graphs without certain cycles ⋮ A note on the DP-chromatic number of complete bipartite graphs ⋮ Answers to two questions on the DP color function ⋮ A local epsilon version of Reed's conjecture ⋮ Differences between the list-coloring and DP-coloring for planar graphs ⋮ A refinement of choosability of graphs ⋮ Exponentially many \(\mathbb{Z}_5\)-colorings in simple planar graphs ⋮ Planar graphs without specific cycles are 2-degenerate ⋮ Group colorings and DP-colorings of multigraphs using edge-disjoint decompositions ⋮ Defective and clustered choosability of sparse graphs ⋮ An analogue of DP-coloring for variable degeneracy and its applications ⋮ Planar graphs without cycles of length from 4 to 7 and intersecting triangles are DP-3-colorable ⋮ DP color functions versus chromatic polynomials ⋮ Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable ⋮ Cover and variable degeneracy ⋮ DP-\(4\)-colorability of planar graphs without intersecting \(5\)-cycles ⋮ Every planar graph without adjacent cycles of length at most 8 is 3-choosable ⋮ DP-4-colorability of two classes of planar graphs ⋮ Note on 3-choosability of planar graphs with maximum degree 4 ⋮ The harmonic index of a graph and its DP-chromatic number ⋮ Relaxed DP-3-coloring of planar graphs without some cycles ⋮ Multiple DP-coloring of planar graphs without 3-cycles and normally adjacent 4-cycles ⋮ DP-degree colorable hypergraphs ⋮ DP-coloring on planar graphs without given adjacent short cycles ⋮ Relaxed DP-coloring and another generalization of DP-coloring on planar graphs without 4-cycles and 7-cycles
Cites Work
- Unnamed Item
- Unnamed Item
- Steinberg's conjecture is false
- List colourings of planar graphs
- A non-3-choosable planar graph without cycles of length 4 and 5
- Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
- Every planar map is four colorable. I: Discharging
- Every planar graph is 5-choosable
- Planar graphs without cycles of length from 4 to 7 are 3-colorable
- 3-list-coloring planar graphs of girth 5
- A not 3-choosable planar graph without 3-cycles
- Colorings of plane graphs: a survey
- On DP-coloring of graphs and multigraphs
- The asymptotic behavior of the correspondence chromatic number
- Sharp Dirac's theorem for DP‐critical graphs
- Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
This page was built for publication: Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
