The Hadwiger number, chordal graphs and ab-perfection

DOI10.1016/J.AKCEJ.2017.02.004zbMATH Open1372.05082arXiv1701.08417OpenAlexW2585060781MaRDI QIDQ2409752FDOQ2409752

Authors: Christian Rubio-Montiel 

Publication date: 13 October 2017

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

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.

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

Recommendations

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

zbMATH Keywords

perfect graphscomplete coloringsforbidden graphs characterization

Mathematics Subject Classification ID

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

Cites Work

• Normal hypergraphs and the perfect graph conjecture
• Title not available (Why is that?)
• Some perfect coloring properties of graphs
• Graph colourings and partitions
• On rigid circuit graphs
• The strong perfect graph theorem
• Title not available (Why is that?)
• Chromatic graph theory
• Title not available (Why is that?)
• The achromatic number of Kneser graphs
• Perfect graphs of strong domination and independent strong domination
• Title not available (Why is that?)
• Title not available (Why is that?)
• A new characterization of trivially perfect graphs
• Characterization of \(b\gamma\)-perfect graphs
• Title not available (Why is that?)

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)