A solution to a colouring problem of P. Erdős

DOI10.1016/0012-365X(92)90588-7zbMath0759.05037MaRDI QIDQ1197012

Michael Stiebitz, Herbert Fleischner

Publication date: 16 January 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

independence numberchromatic numberHamiltonian circuit4-regular graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Eulerian and Hamiltonian graphs (05C45)

Related Items

An algorithm for identifying cycle-plus-triangles graphs, Total choosability of multicircuits II, List homomorphisms to reflexive graphs, Independent dominating sets and a second hamiltonian cycle in regular graphs, Chords of longest cycles in cubic graphs, Strong coloring 2‐regular graphs: Cycle restrictions and partial colorings, On finding constrained independent sets in cycles, 5-list coloring toroidal 6-regular triangulations in linear time, Partitioning into common independent sets via relaxing strongly base orderability, A strengthening and an efficient implementation of Alon-Tarsi list coloring method, Fair Representation by Independent Sets, Extended skew partition problem, On two generalizations of the Alon-Tarsi polynomial method, Orientations of graphs with prescribed weighted out-degrees, Independent systems of representatives in weighted graphs, Chords in longest cycles, Combinatorial Nullstellensatz and DP-coloring of graphs, What is on his mind?, Maximum independent sets in 3- and 4-regular Hamiltonian graphs, On the AVDTC of 4-regular graphs, An asymptotic bound for the strong chromatic number, General Parity Result and Cycle‐Plus‐Triangles Graphs, Some results on \((a:b)\)-choosability, Choosability of the square of planar subcubic graphs with large girth, List edge colourings of some 1-factorable multigraphs, Choosability, edge choosability and total choosability of outerplane graphs, The graph polynomial and the number of proper vertex colorings, The intersection of a matroid and a simplicial complex, On 3-stage Clos networks with different nonblocking requirements on two types of calls, The complexity of finding fair independent sets in cycles, Cooperative colorings and independent systems of representatives

Cites Work

• Unnamed Item
• On the Penrose number of cubic diagrams
• Eulerian graphs and related topics. Part 1, Volume 2
• Colorings and orientations of graphs
• The Hamiltonian property of consecutive-\(d\) digraphs
• Transversals of Vertex Partitions in Graphs