The Hadwiger number, chordal graphs and ab-perfection

DOI10.1016/J.AKCEJ.2017.02.004MaRDI QIDQ2409752zbMATH OpenOpenAlexFDO

Authors Christian Rubio-Montiel

Publication date 13 October 2017

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

perfect graphscomplete coloringsforbidden graphs characterization

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

Abstract: A graph is chordal if every induced cycle has three vertices. The Hadwiger number is the order of the largest complete minor of a graph. We characterize the chordal graphs in terms of the Hadwiger number and we also characterize the families of graphs such that for each induced subgraph $H$, (1) the Hadwiger number of $H$ is equal to the maximum clique order of $H$, (2) the Hadwiger number of $H$ is equal to the achromatic number of $H$, (3) the $b$-chromatic number is equal to the pseudoachromatic number, (4) the pseudo-$b$-chromatic number is equal to the pseudoachromatic number, (5) the Hadwiger number of $H$ is equal to the Grundy number of $H$, and (6) the $b$-chromatic number is equal to the pseudo-Grundy number.

Recommendations

• On b-perfect chordal graphs
• Complete minors, independent sets, and chordal graphs
• scientific article; zbMATH DE number 4075102

Cites work

• scientific article; zbMATH DE number 3152801 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3515502 (Why is no real title available?)
• scientific article; zbMATH DE number 3298599 (Why is no real title available?)
• scientific article; zbMATH DE number 3334007 (Why is no real title available?)
• A new characterization of trivially perfect graphs
• Characterization of \(b\gamma\)-perfect graphs
• Chromatic graph theory
• Connected pseudoachromatic index of complete graphs
• Graph colourings and partitions
• Normal hypergraphs and the perfect graph conjecture
• On rigid circuit graphs
• Perfect graphs of strong domination and independent strong domination
• Some perfect coloring properties of graphs
• The achromatic number of Kneser graphs
• The strong perfect graph theorem

This page was built for publication: The Hadwiger number, chordal graphs and \(ab\)-perfection

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