On the choosability of claw-free perfect graphs

DOI10.1007/S00373-016-1732-9zbMATH Open1353.05055arXiv1506.02576OpenAlexW2260816206MaRDI QIDQ503632FDOQ503632

Authors: Sylvain Gravier, Frédéric Maffray, Lucas Pastor 

Publication date: 13 January 2017

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: It has been conjectured that for every claw-free graph $G$ the choice number of $G$ is equal to its chromatic number. We focus on the special case of this conjecture where $G$ is perfect. Claw-free perfect graphs can be decomposed via clique-cutset into two special classes called elementary graphs and peculiar graphs. Based on this decomposition we prove that the conjecture holds true for every claw-free perfect graph with maximum clique size at most $4$.

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

Recommendations

• Choice number of 3-colorable elementary graphs
• On a conjecture about uniquely colorable perfect graphs
• Claw-free graphs. VI: Colouring
• List-coloring claw-free graphs with small clique number
• scientific article; zbMATH DE number 1123764

zbMATH Keywords

list coloringchoosabilityclaw-free graphperfect

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Cites Work

• Decomposition by clique separators
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• Some upper bounds on the total and list chromatic numbers of multigraphs
• The strong perfect graph theorem
• Title not available (Why is that?)
• The list chromatic index of a bipartite multigraph
• Colorings and orientations of graphs
• An algorithm for finding clique cut-sets
• Choice number of 3-colorable elementary graphs
• A description of claw-free perfect graphs
• On the choice number of claw-free perfect graphs
• Recognizing claw-free perfect graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs

Cited In (8)

• On claw-free \(t\)-perfect graphs
• Strongly perfect claw‐free graphs—A short proof
• Claw-free graphs. VI: Colouring
• List-coloring claw-free graphs with small clique number
• On the choice number of claw-free perfect graphs
• Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
• Title not available (Why is that?)
• Claw-free graphs, skeletal graphs, and a stronger conjecture on \(\omega\), \(\Delta\), and \(\chi\)

This page was built for publication: On the choosability of claw-free perfect graphs

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