A solution to a colouring problem of P. Erdős
The authors prove a conjecture made by Paul Erdős at the Julius Petersen Graph Theory Conference at Hindsgavl in July 1990: Any 4-regular graph on \(3n\) vertices which has a decomposition into a Hamiltonian circuit and \(n\) pairwise vertex-disjoint triangles has chromatic number 3. As a consequences, such a graph has independence number \(n\), as conjectured by D. Z. Du and D. F. Hsu in 1987. It was also noted in \textit{M. R. Fellows} [SIAM J. Discrete Math. 3, No. 2, 206-215 (1990; Zbl 0735.05057)] that Erdős' conjecture is equivalent to an old conjecture of Schur, that for any partition of the integers into triples there is another partition of the integers into 3 parts such that each part contains a member of each triple, but no pair of consecutive integers. Thus did the authors kill three birds with one stone. Hopefully the monetary reward customarily offered by Prof. Erdős will be commensurate with the scope of the result.
- Colorings and orientations of graphs
- Eulerian graphs and related topics. Part 1, Volume 2
- scientific article; zbMATH DE number 3813532 (Why is no real title available?)
- On the Penrose number of cubic diagrams
- The Hamiltonian property of consecutive-\(d\) digraphs
- Transversals of Vertex Partitions in Graphs
- Some results on (a:b)-choosability
- Choosability of the square of planar subcubic graphs with large girth
- List homomorphisms to reflexive graphs
- The graph polynomial and the number of proper vertex colorings
- Independent dominating sets and a second hamiltonian cycle in regular graphs
- Chords of longest cycles in cubic graphs
- Choosability, edge choosability and total choosability of outerplane graphs
- Combinatorial Nullstellensatz and DP-coloring of graphs
- On the AVDTC of 4-regular graphs
- The complexity of finding fair independent sets in cycles
- Cooperative colorings and independent systems of representatives
- An algorithm for identifying cycle-plus-triangles graphs
- Extended skew partition problem
- Independent systems of representatives in weighted graphs
- List edge colourings of some 1-factorable multigraphs
- On 3-stage Clos networks with different nonblocking requirements on two types of calls
- On the problem of Erdős and Hajnal in the case of list colorings
- The intersection of a matroid and a simplicial complex
- scientific article; zbMATH DE number 4145901 (Why is no real title available?)
- The 1-Color Problem and the Brylawski Model
- Total choosability of multicircuits II
- Fair representation by independent sets
- Orientations of graphs with prescribed weighted out-degrees
- General parity result and cycle-plus-triangles graphs
- An asymptotic bound for the strong chromatic number
- A Facility Coloring Problem in 1-D
- 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
- On two generalizations of the Alon-Tarsi polynomial method
- Constructing graphs with no independent transversals
- Colouring solutions of the ice problem
- Chords in longest cycles
- Chords of longest cycles passing through a specified small set
- A reduction of the ``cycles plus \(K_4\)'s problem
- What is on his mind?
- Maximum independent sets in 3- and 4-regular Hamiltonian graphs
- The complexity of finding fair independent sets in cycles
- 5-list coloring toroidal 6-regular triangulations in linear time
- Chords in longest cycles in 3-connected graphs
This page was built for publication: A solution to a colouring problem of P. Erdős
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1197012)
