The list chromatic index of simple graphs whose odd cycles intersect in at most one edge

DOI10.1016/J.DISC.2017.11.012MaRDI QIDQ1690237zbMATH OpenOpenAlexFDO

Authors Jessica McDonald, Gregory J. Puleo

Publication date 19 January 2018

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.05933

zbMATH Keywords

2-connected graphchromatic indexedge list coloringkernel-perfect orientationline graphodd cycles

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: We study the class of simple graphs $mathcal{G}^{\ast }$ for which every pair of distinct odd cycles intersect in at most one edge. We give a structural characterization of the graphs in $mathcal{G}^{\ast }$ and prove that every $Ginmathcal{G}^{\ast }$ satisfies the list-edge-coloring conjecture. When $Delta(G)geq4$, we in fact prove a stronger result about kernel-perfect orientations in $L(G)$ which implies that $G$ is $(mDelta(G):m)$-edge-choosable and $Delta(G)$-edge-paintable for every $mgeq1$.

Recommendations

• New Bounds on the List-Chromatic Index of the Complete Graph and Other Simple Graphs
• The chromatic index of graphs of even order with many edges
• The list chromatic index of a bipartite multigraph
• Computing the list chromatic index of graphs
• List edge multicoloring in graphs with few cycles
• scientific article; zbMATH DE number 1334629
• The chromatic index of simple hypergraphs
• Chromatic index of graphs with no cycle with a unique chord
• Chromatic index of simple hypergraphs
• List edge and list total coloring of 1-planar graphs

Cites work

• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• Edge-choosability in line-perfect multigraphs
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• Kernels in perfect line-graphs
• Mr. Paint and Mrs. Correct
• On kernel-perfect orientations of line graphs
• On-line list colouring of graphs
• The list chromatic index of a bipartite multigraph

Cited in

(1)

• scientific article; zbMATH DE number 7790331 (Why is no real title available?)

This page was built for publication: The list chromatic index of simple graphs whose odd cycles intersect in at most one edge

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