scientific article
From MaRDI portal
Publication:3922703
zbMath0469.05032MaRDI QIDQ3922703
Herbert Taylor, Arthur L. Rubin, Paul Erdős
Publication date: 1980
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
INTERVAL VERTEX-COLORINGS OF CACTUS GRAPHS WITH RESTRICTIONS ON VERTICES ⋮ Independent transversals in bipartite correspondence-covers ⋮ The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs ⋮ Maximum average degree of list-edge-critical graphs and Vizing's conjecture ⋮ Edge (m,k)-choosability of graphs ⋮ Digraphs and Variable Degeneracy ⋮ Fractional DP-chromatic number of planar graphs of large girth ⋮ Sum-list-colouring of θ-hypergraphs ⋮ Unique list colorability of the graph Кn2 + Kr ⋮ Equitable list vertex colourability and arboricity of grids ⋮ Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph ⋮ INTERVAL EDGE-COLORINGS OF TREES WITH RESTRICTIONS ON THE EDGES ⋮ An improved lower bound of \(P(G,L)-P(G,k)\) for \(k\)-assignments \(L\) ⋮ Extremal decompositions for Nordhaus-Gaddum theorems ⋮ Flexible list colorings in graphs with special degeneracy conditions ⋮ Weak degeneracy of graphs ⋮ DP color functions versus chromatic polynomials (II) ⋮ Every planar graph with Δ ${\rm{\Delta }}$ ⩾ 8 is totally (Δ+2) $({\rm{\Delta }}+2)$‐choosable ⋮ ZDP(n) ${Z}_{DP}(n)$ is bounded above by n2−(n+3)∕2 ${n}^{2}-(n+3)\unicode{x02215}2$ ⋮ Single‐conflict colouring ⋮ Chromatic λ‐choosable and λ‐paintable graphs ⋮ Coloring bipartite graphs with semi-small list size ⋮ DP‐coloring Cartesian products of graphs ⋮ Girth and λ $\lambda $‐choosability of graphs ⋮ Colorings, transversals, and local sparsity ⋮ A sufficient condition for planar graphs to be DP-4-colorable ⋮ Comparing list-color functions of uniform hypergraphs with their chromatic polynomials. II ⋮ Asymptotically good edge correspondence colourings ⋮ Bad list assignments for non‐k $k$‐choosable k $k$‐chromatic graphs with 2k+2 $2k+2$‐vertices ⋮ Sudoku number of graphs ⋮ Kempe equivalent list edge-colorings of planar graphs ⋮ A short proof that the list packing number of any graph is well defined ⋮ Generalized DP-colorings of graphs ⋮ The strong fractional choice number of 3‐choice‐critical graphs ⋮ Weakening total coloring conjecture and Hadwiger's conjecture on total graphs ⋮ Weak dynamic coloring of planar graphs ⋮ 5-list coloring toroidal 6-regular triangulations in linear time ⋮ Multiple list coloring of 3‐choice critical graphs ⋮ The list-coloring function of signed graphs ⋮ Dirac's theorem on chordal graphs implies Brooks' theorem ⋮ Brooks' theorem with forbidden colors ⋮ On the list color function threshold ⋮ Slow coloring of \(3k\)-connected graphs ⋮ Bounding the list color function threshold from above ⋮ List homomorphism: beyond the known boundaries ⋮ The Alon-Tarsi number of two kinds of planar graphs ⋮ Extremal problems in hypergraph colourings ⋮ Refined List Version of Hadwiger’s Conjecture ⋮ The Alon-Tarsi number of a toroidal grid ⋮ On triangle-free list assignments ⋮ Packing list‐colorings ⋮ Edge-colouring graphs with local list sizes ⋮ Paintability of complete bipartite graphs ⋮ A strengthening and an efficient implementation of Alon-Tarsi list coloring method ⋮ An algebraic approach for counting DP-3-colorings of sparse graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Flexible List Colorings in Graphs with Special Degeneracy Conditions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A note on list improper coloring planar graphs ⋮ Amenable colorings ⋮ On connected list colorings of graphs ⋮ Approximately coloring graphs without long induced paths ⋮ A local epsilon version of Reed's conjecture ⋮ Neighbour sum distinguishing total colourings via the combinatorial nullstellensatz ⋮ Unnamed Item ⋮ List colorings of multipartite hypergraphs ⋮ Unnamed Item ⋮ Separation Choosability and Dense Bipartite Induced Subgraphs ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Unnamed Item ⋮ A note on adjacent vertex distinguishing colorings of graphs ⋮ Ohba's conjecture is true for graphs \(K_{t+2,3,2\ast(k-t-2),1\ast t}\) ⋮ Asymmetric list sizes in bipartite graphs ⋮ \((3, 1)^*\)-choosability of graphs of nonnegative characteristic without intersecting short cycles ⋮ List vertex-arboricity of toroidal graphs without 4-cycles adjacent to 3-cycles ⋮ \(\Delta \)-list vertex coloring in linear time ⋮ A better lower bound on average degree of 4-list-critical graphs ⋮ Coloring, sparseness and girth ⋮ The 4-choosability of toroidal graphs without intersecting triangles ⋮ A \((3,1)^\ast\)-choosable theorem on planar graphs ⋮ Online containers for hypergraphs, with applications to linear equations ⋮ Coloring immersion-free graphs ⋮ Some relations among term rank, clique number and list chromatic number of a graph ⋮ When does the list-coloring function of a graph equal its chromatic polynomial ⋮ Multiple list colouring of planar graphs ⋮ Towards a solution of the Dinitz problem? ⋮ A new upper bound for the list chromatic number ⋮ Claw-free graphs. VI: Colouring ⋮ The complexity of planar graph choosability ⋮ List homomorphisms to reflexive graphs ⋮ Dynamic list coloring of bipartite graphs ⋮ Distance constraints in graph color extensions ⋮ Graphs with maximum degree \(\varDelta\geq 17\) and maximum average degree less than 3 are list 2-distance \((\varDelta +2)\)-colorable ⋮ On 1-improper 2-coloring of sparse graphs ⋮ Partial list colouring of certain graphs ⋮ Choosability in signed planar graphs ⋮ Application of polynomial method to on-line list colouring of graphs ⋮ Families of online sum-choice-greedy graphs ⋮ 3-list-coloring planar graphs of girth 4 ⋮ On the complexity of some colorful problems parameterized by treewidth ⋮ Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable ⋮ Dense uniform hypergraphs have high list chromatic number ⋮ Two problems on independent sets in graphs ⋮ Randomly colouring graphs (a combinatorial view) ⋮ On two generalizations of the Alon-Tarsi polynomial method ⋮ Extending Hall's theorem into list colorings: a partial history ⋮ Coloring graphs from random lists of size 2 ⋮ Some structural properties of planar graphs and their applications to 3-choosability ⋮ Linear choosability of graphs ⋮ Another proof of the 5-choosability of \(K_5\)-minor-free graphs ⋮ \(\ell\)-facial edge colorings of graphs ⋮ \(T\)-colorings of graphs: recent results and open problems ⋮ Orientations of graphs with prescribed weighted out-degrees ⋮ On-line choice number of complete multipartite graphs: an algorithmic approach ⋮ Chromatic-choosability of hypergraphs with high chromatic number ⋮ Some results concerning the complexity of restricted colorings of graphs ⋮ Sum-paintability of generalized theta-graphs ⋮ A weaker version of a conjecture on list vertex arboricity of graphs ⋮ On improperly chromatic-choosable graphs ⋮ On the choosability of claw-free perfect graphs ⋮ The list distinguishing number equals the distinguishing number for interval graphs ⋮ An introduction to the discharging method via graph coloring ⋮ The coloring game on matroids ⋮ List coloring of planar graphs with forbidden cycles ⋮ Degree choosable signed graphs ⋮ Choice number and energy of graphs ⋮ List edge chromatic number of graphs with large girth ⋮ On-line list coloring of matroids ⋮ Upper bounds for the achromatic and coloring numbers of a graph ⋮ List colourings of planar graphs ⋮ Hall number for list colorings of graphs: Extremal results ⋮ On 3-choosability of planar graphs without certain cycles ⋮ Ohba's conjecture for graphs with independence number five ⋮ List precoloring extension in planar graphs ⋮ Vertex coloring complete multipartite graphs from random lists of size 2 ⋮ Coloring face hypergraphs on surfaces ⋮ Complexity of clique coloring and related problems ⋮ A smaller planar graph without 4-, 5-cycles and intersecting triangles that is not 3-choosable ⋮ Edge-choosability of planar graphs without non-induced 5-cycles ⋮ Planar graphs are 1-relaxed, 4-choosable ⋮ Injective colorings of sparse graphs ⋮ Contractibility and the Hadwiger conjecture ⋮ Brooks' theorem via the Alon-Tarsi theorem ⋮ Critically paintable, choosable or colorable graphs ⋮ List total arboricity of 2-degenerate graphs ⋮ Chip games and paintability ⋮ Every graph \(G\) is Hall \(\Delta(G)\)-extendible ⋮ The minimum number of vertices for a triangle-free graph with \(\chi _l(G)=4\) is \(11\) ⋮ Choice number of complete multipartite graphs \(K_{3*3,2*(k - 5),1*2}\) and \(K_{4,3*2,2*(k - 6),1*3}\) ⋮ Planar graphs without 4-cycles adjacent to triangles are 4-choosable ⋮ On the choice number of complete multipartite graphs with part size four ⋮ Randić index and coloring number of a graph ⋮ On \((3, 1)^\ast\)-choosability of planar graphs without adjacent short cycles ⋮ Sufficient sparseness conditions for \(G^2\) to be \((\Delta + 1)\)-choosable, when \(\Delta \geq 5\) ⋮ List-coloring claw-free graphs with small clique number ⋮ List coloring of graphs having cycles of length divisible by a given number ⋮ Ohba's conjecture is true for graphs with independence number at most three ⋮ Entire choosability of near-outerplane graphs ⋮ Sum choice numbers of some graphs ⋮ Some results on \((a:b)\)-choosability ⋮ On 3-choosable planar graphs of girth at least 4 ⋮ The harmonic index of a graph and its DP-chromatic number ⋮ On \((d,1)\)-total numbers of graphs ⋮ Precoloring extension for 2-connected graphs with maximum degree three ⋮ On list critical graphs ⋮ Injective colorings of planar graphs with few colors ⋮ Planar graphs without 3-, 7-, and 8-cycles are 3-choosable ⋮ Polychromatic colorings of arbitrary rectangular partitions ⋮ Planar graphs without cycles of length 4, 5, 8, or 9 are 3-choosable ⋮ Group coloring is \(\Pi_2^{\text{P}}\)-complete ⋮ On DP-coloring of graphs and multigraphs ⋮ A subexponential algorithm for the coloured tree partition problem ⋮ The asymptotic behavior of the correspondence chromatic number ⋮ Plane graphs with maximum degree 9 are entirely 11-choosable ⋮ Facial list colourings of plane graphs ⋮ Painting squares in \(\Delta^2-1\) shades ⋮ On group choosability of total graphs ⋮ An analysis of the parameterized complexity of periodic timetabling ⋮ A note on 3-choosability of planar graphs ⋮ The Dinitz problem solved for rectangles ⋮ Every triangle-free induced subgraph of the triangular lattice is \((5m,2m)\)-choosable ⋮ Disproof of a conjecture by Woodall on the choosability of \(K_{s,t}\)-minor-free graphs ⋮ Some new bounds on \(T_{r}\)-choosability ⋮ Improper choosability of graphs of nonnegative characteristic ⋮ A deletion-contraction relation for the DP color function ⋮ Hyperbolic families and coloring graphs on surfaces ⋮ Edge-group choosability of outerplanar and near-outerplanar graphs ⋮ Planar graphs without intersecting 5-cycles are 4-choosable ⋮ Bounds on partial online list colouring ⋮ The DP color function of joins and vertex-gluings of graphs ⋮ Choosability with union separation of planar graphs without cycles of length 4 ⋮ Proportional choosability of complete bipartite graphs ⋮ Beyond degree choosability ⋮ Sum choice number of generalized \(\theta\)-graphs ⋮ Facially-constrained colorings of plane graphs: a survey ⋮ Partial DP-coloring of graphs ⋮ Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques ⋮ Chain method for panchromatic colorings of hypergraphs ⋮ On Equitable List Arboricity of Graphs ⋮ A simple characterization of proportionally 2-choosable graphs ⋮ On restricted colorings of (d, s)-edge colorable graphs ⋮ Strengthening \((a,b)\)-choosability results to \((a,b)\)-paintability ⋮ Bounds for the sum choice number ⋮ Vertex colourings of multigraphs with forbiddances on edges ⋮ Algorithmic Applications of Tree-Cut Width ⋮ List-distinguishing Cartesian products of cliques ⋮ A generalization of some results on list coloring and DP-coloring ⋮ The list-chromatic number of complete multipartite hypergraphs and multiple covers by independent sets ⋮ 4-choosability of planar graphs with 4-cycles far apart via the Combinatorial Nullstellensatz ⋮ Coloring squares of planar graphs with girth six ⋮ 不含带弦6-圈和项链图的平面图是DP-4-可染的 ⋮ 3-facial edge-coloring of plane graphs ⋮ A note on 3-choosability of plane graphs under distance restrictions ⋮ 3-choosability of planar graphs with \((\leqslant 4)\)-cycles far apart ⋮ 3-colouring \(P_t\)-free graphs without short odd cycles ⋮ Relation between the correspondence chromatic number and the Alon-Tarsi number ⋮ Non-chromatic-adherence of the DP color function via generalized theta graphs ⋮ List backbone colouring of graphs ⋮ Towards an on-line version of Ohba's conjecture ⋮ Generalized hypergraph coloring ⋮ Linear colorings of subcubic graphs ⋮ A note on total colorings of 1-planar graphs ⋮ Better 3-coloring algorithms: excluding a triangle and a seven vertex path ⋮ Brooks' theorem on powers of graphs ⋮ On the chromatic polynomial and counting DP-colorings of graphs ⋮ 3-list-coloring graphs of girth at least five on surfaces ⋮ Concepts of signed graph coloring ⋮ Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem ⋮ An infinite family of sum-paint critical graphs ⋮ Choosability of graphs with infinite sets of forbidden differences ⋮ On choosability of some complete multipartite graphs and Ohba's conjecture ⋮ Coloring temporal graphs ⋮ Acyclic sum-list-colouring of cylinders ⋮ Closing complexity gaps for coloring problems on \(H\)-free graphs ⋮ Five-list-coloring graphs on surfaces. I. Two lists of size two in planar graphs ⋮ Extension of a list coloring problem ⋮ Bordeaux 3-color conjecture and 3-choosability ⋮ A relation between choosability and uniquely list colorability ⋮ List colourings of planar graphs. (Reprint) ⋮ Linear choosability of sparse graphs ⋮ List coloring of Cartesian products of graphs ⋮ Hard coloring problems in low degree planar bipartite graphs ⋮ Improved lower bounds on the number of edges in list critical and online list critical graphs ⋮ A refinement of choosability of graphs ⋮ List coloring and diagonal coloring for plane graphs of diameter two ⋮ List coloring a Cartesian product with a complete bipartite factor ⋮ Colorings of partial Steiner systems and their applications ⋮ Vertex partition of hypergraphs and maximum degenerate subhypergraphs ⋮ Completing partial proper colorings using Hall's condition ⋮ The strong fractional choice number of series-parallel graphs ⋮ DP-4-colorability of planar graphs without adjacent cycles of given length ⋮ Lower bounds on coloring numbers from hardness hypotheses in pcf theory ⋮ Multiple list colouring triangle free planar graphs ⋮ Incidence choosability of graphs ⋮ Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable ⋮ Proportional choosability: a new list analogue of equitable coloring ⋮ Measurable versions of the Lovász local lemma and measurable graph colorings ⋮ Improper sum-list colouring of 2-trees ⋮ Every planar graph without adjacent cycles of length at most 8 is 3-choosable ⋮ Planar graphs without cycles of length 4 or 5 are \((11 : 3)\)-colorable ⋮ DP-4-colorability of two classes of planar graphs ⋮ Acyclic choosability of planar graphs: a Steinberg like approach ⋮ DP-degree colorable hypergraphs ⋮ Distributed coloring in sparse graphs with fewer colors ⋮ DP-coloring on planar graphs without given adjacent short cycles ⋮ Equitable colourings of Borel graphs ⋮ Extending partial 5-colorings and 6-colorings in planar graphs ⋮ Characterization of \((2m,m)\)-paintable graphs ⋮ An algebraic criterion for the choosability of graphs ⋮ List coloring of matroids and base exchange properties ⋮ Algorithmic complexity of list colorings ⋮ The choice number versus the chromatic number for graphs embeddable on orientable surfaces ⋮ DP-3-coloring of some planar graphs ⋮ Two sufficient conditions for a planar graph to be list vertex-2-arborable ⋮ A new approach on locally checkable problems ⋮ Three-coloring Klein bottle graphs of girth five ⋮ The edge-face choosability of plane graphs ⋮ Colouring powers of cycles from random lists ⋮ Colouring graphs with sparse neighbourhoods: bounds and applications ⋮ Path choosability of planar graphs ⋮ Hajós' theorem for list coloring ⋮ On a list variant of the multiplicative 1-2-3 conjecture ⋮ On the subspace choosability in graphs ⋮ Complexity of list coloring problems with a fixed total number of colors ⋮ The colour theorems of Brooks and Gallai extended ⋮ Choosability and fractional chromatic numbers ⋮ Choice number of 3-colorable elementary graphs ⋮ On the Dinitz conjecture and related conjectures ⋮ Choice numbers of multi-bridge graphs ⋮ An exchange property of matroids ⋮ On the number of even and odd Latin squares of order \(p+1\) ⋮ Solving graph coloring problems with the Douglas-Rachford algorithm ⋮ Generalized coloring for tree-like graphs ⋮ List edge and list total colourings of multigraphs ⋮ Extension from precoloured sets of edges ⋮ A new sufficient condition for a toroidal graph to be 4-choosable ⋮ Color-critical graphs on a fixed surface ⋮ Choosability of planar graphs ⋮ A Hajós-like theorem for list coloring ⋮ Some results on list \(T\)-colourings ⋮ \(T\)-choosability in graphs ⋮ Dynamic coloring parameters for graphs with given genus ⋮ Choosability with union separation ⋮ A note on panchromatic colorings ⋮ The list chromatic index of simple graphs whose odd cycles intersect in at most one edge ⋮ List colouring of graphs and generalized Dyck paths ⋮ On a list-coloring problem ⋮ Improper choosability of graphs embedded on the surface of genus \(r\) ⋮ A new lower bound on the number of edges in colour-critical graphs and hypergraphs ⋮ Online sum-paintability: the slow-coloring game ⋮ List-edge-coloring of planar graphs without 6-cycles with three chords ⋮ Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable ⋮ On a conjecture of Mohar concerning Kempe equivalence of regular graphs ⋮ Improved distributed \(\Delta\)-coloring ⋮ The 4-choosability of planar graphs and cycle adjacency ⋮ Corrigendum to: ``A local epsilon version of Reed's conjecture ⋮ Every planar graph without pairwise adjacent 3-, 4-, and 5-cycle is DP-4-colorable ⋮ On \((k, k n - k^2 - 2 k - 1)\)-choosability of \(n\)-vertex graphs ⋮ Planar graphs without chordal 6-cycles are 4-choosable ⋮ A better lower bound on average degree of online \(k\)-list-critical graphs ⋮ Total equitable list coloring ⋮ 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 ⋮ Combinatorial Nullstellensatz and DP-coloring of graphs ⋮ Acyclic improper choosability of subcubic graphs ⋮ Generalized list \(T\)-colorings of cycles ⋮ A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model ⋮ DP-3-coloring of planar graphs without certain cycles ⋮ The 3-choosability of plane graphs of girth 4 ⋮ A note on the DP-chromatic number of complete bipartite graphs ⋮ Nonrepetitive list colorings of the integers ⋮ Injective edge-coloring of graphs with given maximum degree ⋮ A note on the list vertex arboricity of toroidal graphs ⋮ A note on the equitable choosability of complete bipartite graphs ⋮ On list equitable total colorings of the generalized theta graph ⋮ List injective edge-coloring of subcubic graphs ⋮ The trouble with the second quantifier ⋮ On list \(k\)-coloring convex bipartite graphs ⋮ You can't paint yourself into a corner ⋮ Planar graphs without cycles of length from 4 to 7 and intersecting triangles are DP-3-colorable ⋮ Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs ⋮ Interval vertex-coloring of a graph with forbidden colors ⋮ DP color functions versus chromatic polynomials ⋮ Proportional 2-choosability with a bounded palette ⋮ Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum ⋮ Vertex-arboricity of toroidal graphs without \(K_5^-\) and \(6\)-cycles ⋮ Cover and variable degeneracy ⋮ The list chromatic numbers of some planar graphs ⋮ Planar graphs without pairwise adjacent 3-, 4-, 5-, and 6-cycle are 4-choosable ⋮ The Hall number, the Hall index, and the total Hall number of a graph ⋮ The choice number of random bipartite graphs ⋮ On the equitable choosability of the disjoint union of stars ⋮ Choosability, edge choosability and total choosability of outerplane graphs ⋮ On the complexity of a restricted list-coloring problem ⋮ On list edge-colorings of subcubic graphs ⋮ Choosability of \(K_5\)-minor-free graphs ⋮ Complexity of choosing subsets from color sets ⋮ Edge-choosability in line-perfect multigraphs ⋮ On structure of some plane graphs with application to choosability ⋮ Graph imperfection. I ⋮ Coloring face-hypergraphs of graphs on surfaces ⋮ The 4-choosability of plane graphs without 4-cycles ⋮ Local mending ⋮ List \(T\)-colorings of graphs ⋮ Edge dominating set and colorings on graphs with fixed clique-width ⋮ Relaxed DP-coloring and another generalization of DP-coloring on planar graphs without 4-cycles and 7-cycles ⋮ Simultaneous coloring of edges and faces of plane graphs ⋮ All subgraphs of a wheel are 5-coupled-choosable ⋮ On sufficient conditions for planar graphs to be 5-flexible ⋮ On \((3, r)\)-choosability of some planar graphs
This page was built for publication:
