Chordal multipartite graphs and chordal colorings

DOI10.1016/J.DISC.2006.11.003MaRDI QIDQ2643326zbMATH OpenOpenAlexFDO

Authors Terry A. McKee

Publication date 23 August 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.11.003

zbMATH Keywords

chordal bipartite graphchordal graphcoloringvertex separator

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

Review text

A graph is defined to be chordal colorable if it admits a proper vertex-coloring such that each minimal separator induces a subgraph in which two vertices are adjacent if and only if they are differently colored. All chordal graphs and all chordal bipartite graphs are chordal colorable. All chordal colorable graphs are weakly chordal. The class of chordal colorable graphs is characterised, amongst others, by minimal forbidden subgraphs.

Recommendations

• A k-partite generalization of chordal bipartite graphs
• Join colourings of chordal graphs
• Requiring that minimal separators induce complete multipartite subgraphs
• scientific article; zbMATH DE number 52166
• List matrix partitions of chordal graphs

Cites work

• Algorithmic graph theory and perfect graphs
• Graph Classes: A Survey
• scientific article; zbMATH DE number 1194938 (Why is no real title available?)
• On the coloring of signed graphs
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Requiring chords in cycles
• Topics in Intersection Graph Theory
• Weakly triangulated graphs

Cited in

(5)

• Recolouring weakly chordal graphs and the complement of triangle-free graphs
• 3-colouring for dually chordal graphs and generalisations
• A new proof of a characterization of (k,l)-colourable chordal graphs
• A k-partite generalization of chordal bipartite graphs
• On 2-Subcolourings of Chordal Graphs

This page was built for publication: Chordal multipartite graphs and chordal colorings

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