On the choosability of claw-free perfect graphs

DOI10.1007/S00373-016-1732-9MaRDI QIDQ503632zbMATH OpenOpenAlexFDO

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

Publication date 13 January 2017

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

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

zbMATH Keywords

list coloringchoosabilityclaw-free graphperfect

Mathematics Subject Classification ID

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

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$.

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

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 1123764 (Why is no real title available?)
• A description of claw-free perfect graphs
• An algorithm for finding clique cut-sets
• Choice number of 3-colorable elementary graphs
• Colorings and orientations of graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Decomposition by clique separators
• On the choice number of claw-free perfect graphs
• Recognizing claw-free perfect graphs
• Some upper bounds on the total and list chromatic numbers of multigraphs
• The list chromatic index of a bipartite multigraph
• The strong perfect graph theorem
• 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
• scientific article; zbMATH DE number 1952889 (Why is no real title available?)
• 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)