Partitions and edge colourings of multigraphs

MaRDI QIDQ1010682zbMATH OpenFDO

Authors Michael Stiebitz, Alexandr Kostochka

Publication date 7 April 2009

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/129819, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1n25.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Summary: Erdős and Lovász conjectured in 1968 (see Problem 5.12 in [\textit{T.R.\, Jensen} and \textit{B. Toft}, Graph colouring problems, New York: John Wiley \& Sons (1995; Zbl 0855.05054)]) that for every graph \(G\) with \(\chi(G)>\omega(G)\) and any two integers \(s,t\geq 2\) with \(s+t=\chi(G)+1\), there is a partition \((S,T)\) of the vertex set \(V(G)\) such that \(\chi(G[S])\geq s\) and \(\chi(G[T])\geq t\). Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for line graphs of multigraphs.

Recommendations

• The Erdős-Lovász tihany conjecture for quasi-line graphs
• Enhancing the Erdős‐Lovász Tihany Conjecture for line graphs of multigraphs
• A strengthening of Brooks' Theorem for line graphs
• Hajós' conjecture for line graphs
• Short fans and the 5/6 bound for line graphs

Cited in

(21)

• The Erdős-Lovász tihany conjecture for quasi-line graphs
• Group colorings and DP-colorings of multigraphs using edge-disjoint decompositions
• Partition graphs of independence number \(2\) into two subgraphs with large chromatic numbers
• Some remarks on even-hole-free graphs
• Erdős-Lovász Tihany conjecture for graphs with forbidden holes
• Vertex colouring edge partitions
• Colourings, homomorphisms, and partitions of transitive digraphs
• scientific article; zbMATH DE number 4162925 (Why is no real title available?)
• scientific article; zbMATH DE number 4008444 (Why is no real title available?)
• Edge-partitions of planar graphs and their game coloring numbers
• Characterizing partition functions of the edge-coloring model by rank growth
• Double-critical graph conjecture for claw-free graphs
• A relaxed version of the Erdős-Lovász Tihany conjecture
• Short fans and the 5/6 bound for line graphs
• Note on Cellular Structure of Edge Colored Partition Algebras
• On multigraphs with a given partition
• Enhancing the Erdős‐Lovász Tihany Conjecture for line graphs of multigraphs
• Partition line graphs of multigraphs into two subgraphs with large chromatic numbers
• Some cases of the Erdős-Lovász Tihany conjecture for claw-free graphs
• Hajós' conjecture for line graphs
• Vertex partitions of \(r\)-edge-colored graphs

This page was built for publication: Partitions and edge colourings of multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010682)